All Questions
-2
votes
0answers
4 views
What is famous hotels in Shanghai?
I was in Shanghai the other day at the inauguration of a new hotel by the river called 'Grand Melia' I was THOROUGHLY impressed by the lavish interior decoration, the intricately decorated rooms, ...
-2
votes
0answers
5 views
About Shanghai apartment rentals?
Next month, I'll go to Shanghai, China and stay there for 2 months. I want a furnished apartment for short-term rental. What should I do to find it?
-3
votes
0answers
6 views
Where online can I buy a cheap football team shirt?
I want to buy a women's long sleeve shirt or hoodie for denver broncos games. I can't afford a $100 shirt so I would like to find something under $50 if possible
-4
votes
0answers
4 views
What are the manufacturers of artificial grass?
What are artificial grass manufacturers in China?Which is better in producing artificial turf? Can you recommend some manufactures?Thank you.
2
votes
2answers
23 views
Type theory and type systems
I recently realized that there is some sort of relation between Russellian type theory and type systems, as found e.g. in Haskell. Actually, some of the notation for types in Haskell seems to have ...
0
votes
2answers
13 views
When does the nearest neighbor heuristic fail for the Traveling Salesperson?
Can you provide an example of NN algorithm failure on the Euclidean traveling salesman problem?
I was trying to construct a specific example of this for my friends and was failing.
1
vote
0answers
18 views
eopl environment interface: data structure representation vs procedural representation [on hold]
Can anyone point out what is the difference between the two environment interface representations - data structure and procedural as explained in EOPL, third ed. Since I am new to Scheme, I am not ...
0
votes
0answers
34 views
Realizing a full subtractor using 4 to 1 MUX and an inverter [on hold]
I can't wrap my head around it. Any tips?
I need to draw a circuit diagram of a Full Subtractor using 4-to-1 Multiplexers and an Inverter.
Thanks in advance, any help is welcome.
0
votes
1answer
21 views
Representing grammar for list/dictionary with optional end separator as LL(1)
Considering a grammar that includes a dictionary or list with an optional terminal separator - e.g.:
$$
\begin{align}
obj \to & dict \\
&\mid OTHER \\
dict \to & ...
0
votes
2answers
56 views
Data structure for maintaining large space-efficient filtered array
How does one implement a space efficient data structure that satisfies the requirements below?
You have a large array
You have a filter which tells you which elements in that large array are to be ...
0
votes
0answers
19 views
Does the 'Internet of Things' fall under Computer Networking? [on hold]
I'm currently a MSc Computer Networking student and I recently became acquainted with the internet of things. I've fallen completely in love with this new area and I would love to base my dissertation ...
2
votes
2answers
56 views
Chaitin's elegant programs
I need help to understand Chaitin's elegant program proof. An elegant program is the shortest program that produces a given output.
Here is the proof:
Construct a program $B$ that takes as input ...
-3
votes
0answers
48 views
Two software engieer interview quizz [on hold]
Question1:There's on missing card from the a standard deck of poker. How to find the missing card.
Question2:A Rubik's cube, after rotating 4 times, what's the maximum number of colour on the ...
2
votes
0answers
65 views
Find a sequence of integer powers faster than the naive algorithm
Let $k\in \mathbb{N}$ be fixed. The naive way to compute a sequence of values $a_1^k,\ldots,a_n^k$ where $a_i\in \mathbb{N}$ for all $1\leq i\leq n$ is compute $a_i^k$ individually with the ...
1
vote
0answers
27 views
Inversion of BDD
How can I write an algorithm which inverts a 2-level BDD? It should take as input a 2L-level quasi-reduced BDD rooted at $r$ encoding a relation $R : B^L → 2^{B^L}$ and returns the 2L-level ...
1
vote
0answers
20 views
Can xor and xnor for quasi-reduced BDDs be implemented just like union? [duplicate]
Below is an algorithm for union of two quasi reduced BDDs p and q resulting in r.
...
4
votes
0answers
30 views
Understanding Dinic's algorithm using dynamic trees
I have here a directed graph that I used to perform Dinic's algorithm to find maximum flow. I need to adjust this graph and this algorithm to work with dynamic trees (i.e. the Sleator-Tarjan ...
3
votes
1answer
56 views
lambda calculus as a type theory
From the Introduction section of Homotopy Type Theory book:
Type theory was originally invented by Bertrand Russell ... It was later developed as a rigorous formal system in its own right(under ...
0
votes
1answer
38 views
Determine if two grammars for the same language are ambiguous
I'm reading the book: Formal Syntax and Semantics of Programming Languages. I don't understand this exercise:
Consider the following two grammars, each of which generates strings of correctly ...
0
votes
1answer
88 views
Little's law and average time on a system with a switch
We have a switch with $2$ lines of input and $2$ output. Each line is $10 Mbps$. The size of packets is fixed and is $1KB$. The $1^{st}$ line of input is active (transferring packets) $40\%$ of the ...
1
vote
1answer
39 views
Understand the time complexity for this LCS (longest common subsequence) solution
I would appreciate an intuitive way to find the time complexity of dynamic programming problems. Can anyone explain me “#subproblems * time/subproblem”? I am not able to grok it.
Code for LCS -
...
2
votes
2answers
79 views
Joining two red-black trees
I have
two red-black trees $T_1$ of black height $H_1$ and $T_2$ of black height $H_2$
such that all the nodes $N$ belonging to $T_1$ are less than (in value) all the nodes $N$ of $T_2$
and a key ...
-1
votes
0answers
29 views
Extra newline character '\n' at end of file [on hold]
I was looking at some .py files of one of the plugins of my Editor and I noticed that they all have an extra \n at the end, ...
0
votes
2answers
65 views
Prove Context Free languages not closed under difference?
Given two context-free languages $L_1$ and $L_2$, the language given by the difference of the two languages, $L_1 - L_2$, is (in general) not context-free. Is it possible to prove this without using ...
4
votes
1answer
65 views
NP-Hardness reduction
I have a problem $\Pi_1$ that I want to show that is NP-hard. I know that I must find an NP-hard problem $\Pi_2$ and a polynomial time reduction $f()$ from instances of $\Pi_2$ to $\Pi_1$ such that ...
2
votes
2answers
88 views
Detecting cycles in undirected graph
I want to detect cycles in an undirected graph such that I get a list of all edges/vertices which form each cycle. For a graph G({a,b,c,d}, {a-b, b-c, c-d, d-a, b-d}) this would be {a, b, c, d}, {a, ...
4
votes
2answers
110 views
Recommended readings for Probability theory applied to algorithms
Currently, I'm delving into Analysis of Algorithms and I've discovered that I would need to improve my knowledge of Probability Theory. Any recommendation? Where do I start?
Thanks in advance!
0
votes
1answer
29 views
Prove that the syntax is equivalent
I don't "see" why the following syntax is equivalent to the second
syntax1:
E -> E + T
E -> T
syntax2:
...
3
votes
2answers
50 views
Constructing Tree (forest) from Ancestor function
Suppose I have a
set of male people, and
a function isAncestor(person1,person2) that checks whether person1 is an ancestor of person2 in O(1) time. Eg, isAncestor(grandfather, grandson) would ...
2
votes
1answer
26 views
Generalizing the linear subset scan algorithm to a wider class of objective functions, maybe by finding a paper
Given a list of pairs $(a_1,b_1),\ldots,(a_n,b_n)$, where all $a_i \geq 0$ and all $b_i > 0$, my general problem is when we can use linear subset scan (described below) to solve the optimization ...
6
votes
1answer
64 views
Why are all problems in FPTAS also in FPT?
According to the Wikipedia article on polynomial-time approximation schemes:
All problems in FPTAS are fixed-parameter tractable.
This result surprises me - these classes seem to be totally ...
2
votes
2answers
104 views
Getting started with Data Mining
This is the first time that I'm looking in depth into the topic, although I've always been curious.
Could someone let me know about online resources (courses, tutorials, etc) and books that cover the ...
1
vote
2answers
86 views
What is the meaning of this pseudo-code function?
While reading the paper Holistic twig joins: optimal XML pattern matching I came across the pseudo code for liststack algorithm. (available through google scholar)
A function in the algorithm ...
5
votes
1answer
48 views
Completeness of formal definition of 'hardness on the average'
While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for ...
9
votes
1answer
155 views
What is the difference between an algorithm, a language and a problem?
It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
2
votes
0answers
58 views
Motion planning using second order Bézier curves
I'm trying to find an algorithm for a motion planning problem. I have $N$ points, $P_1$ to $P_N$, in $k$-dimensional cartesian space, defining $N-1$ segments. The problem is about constructing the ...
4
votes
3answers
85 views
What is the difference between exhaustive search & combinatorial search?
I get used to think exhaustive search and combinatorial search are same, but I got confused by reading a paper!
What is the difference between exhaustive search & combinatorial search ?
4
votes
1answer
125 views
Is the memory-runtime tradeoff an equivalent of Heisenberg's uncertainty principle?
When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, ...
1
vote
1answer
29 views
Recursive definition of sum of two numbers in terms of the successor function
This is a question from the book Data structures using C and C++ by Tenenbaum. Not a homework problem but self-study.
Recursive definition of a+b, where a and b ...
3
votes
2answers
77 views
Polynomial-time algorithm with exponential space is eligible?
I'm curious about two things.
When we define the class called "probabilistic polynomial-time algorithm" in computer science, does it include polynomial-time algorithm with exponential space?
For ...
5
votes
4answers
78 views
Does the time complexity of a problem change with encoding of the problem?
Suppose I have a decision problem $D$ and I encode it to a language $L \subset \{0,1\}^*$. Now, I can also encode it to a different language $L'$.
Is there any theorem relating the time complexity of ...
0
votes
0answers
35 views
are the two bdds equivalent [closed]
The bdd shown in figure is a fully-reduced BDD ( with dotted arrow =0 edge, regular arrow =1 edge). I have some confusions about this BDD while filling the table for the values for f(a,b,c). After ...
2
votes
0answers
58 views
Difference between fully-reduced BDD and quasi-reduced BDD
I am trying to figure out difference between fully- and quasi-reduced BDDs. I have read a lot of material but still it is not very clear. As I am trying to figure out the quasi reduced version for ...
-1
votes
0answers
25 views
weights generation [closed]
I have a problem,
I want to generate a set of weights w1...wn (Where n = height of image).
For me the header and the footer of ...
2
votes
2answers
63 views
Measures and probability in formal language theory
I am looking for references for the following problem:
I have a very special class of regular languages and my aim is to express (and to justify my conjecture) that this class itself is very small in ...
1
vote
1answer
79 views
Getting started with Compiler Design
This is the first time I will be studying compilers in depth. Can someone point me to best online resources (courses, articles, tutorials, video etc ) and books?
My main aim will be to do some ...
0
votes
2answers
112 views
Computer Science or Software Engineering [closed]
i reworded my whole question to make it as objective as possible. The main things i would like to know is about what kinds of jobs you can get with each degree. This is important as one course may ...
5
votes
2answers
113 views
What exactly is polynomial time?
I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not ...
0
votes
0answers
34 views
Is there a one-point combinator which does not apply any of its arguments to an abstraction?
I am trying to come up with a programming language based on combinatory logic using only two symbols: an application operator 0 and a combinator ...
0
votes
0answers
22 views
Can finite automata recognize {ww | w a word}? [duplicate]
The question is whether a finite automaton can recognize
a language like {ww | where w a word in a language}, e.g.
if the language contains the symbols L = {a, b ,c} then it should
recognize the words ...
