All Questions
46,355
questions
52
votes
1
answer
22k
views
Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?
Anyway, here'...
- 20.1k
19
votes
3
answers
2k
views
ML function of type 'a -> 'b
Our professor asked us to think of a function in OCaml that has the type
'a -> 'b
i.e. a function of one argument that could be anything, and that can return ...
84
votes
8
answers
59k
views
Graph searching: Breadth-first vs. depth-first
When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).
Now, are ...
- 965
20
votes
4
answers
548
views
Strategies for becoming unstuck in understanding TCS
I am a graduate student taking a course in theory of computation and I have serious trouble producing content once I'm asked to. I'm able to follow the textbook (Introduction to the Theory of ...
- 511
3
votes
3
answers
2k
views
Understanding $\text{handle}$ in parsing problem
Originally https://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there
The BNF is defined as followed:
...
- 3,028
21
votes
2
answers
7k
views
Universality of the Toffoli gate
Regarding the quantum Toffoli gate:
is it classicaly universal, and if so, why?
is it quantumly universal, and why?
- 20.5k
10
votes
2
answers
2k
views
How is the loop invariant obtained in this square root bound finding algorithm?
Originally on math.SE but unanswered there.
Consider the following algorithm.
...
- 3,028
13
votes
1
answer
360
views
Proving the security of Nisan-Wigderson pseudo-random number generator
Let $\cal{S}=\{S_i\}_{1\leq i\leq n}$ be a partial $(m,k)$-design and $f: \{0,1\}^m \to \{0,1\}$ be a Boolean function. The Nisan-Wigderson generator $G_f: \{0,1\}^l \to \{0,1\}^n$ is defined as ...
- 21.9k
9
votes
2
answers
3k
views
Decidability of prefix language
At the midterm there was a variant of the following question:
For a decidable $L$ define $$\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}$$
Show that $\text{Pref}(L)$ is not ...
- 20.5k
17
votes
3
answers
3k
views
Decidable non-context-sensitive languages
It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even ...
14
votes
3
answers
287
views
Is there an abstract machine that can capture power consumption?
When reporting algorithmic complexity of an algorithm, one assumes the underlying computations are performed on some abstract machine (e.g. RAM) that approximates a modern CPU. Such models allow us to ...
user20
38
votes
2
answers
27k
views
Hash tables versus binary trees
When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL ...
- 8,986
56
votes
11
answers
33k
views
Why would anyone want CISC?
In our computer systems lecture we were introduced to the MIPS processor. It was (re)developed over the course of the term and has in fact been quite easy to understand. It uses a RISC design, that is ...
- 71.6k
30
votes
2
answers
5k
views
Why are the total functions not enumerable?
We learned about the concept of enumerations of functions. In practice, they correspond to programming languages.
In a passing remark, the professor mentioned that the class of all total functions (i....
- 71.6k
99
votes
5
answers
98k
views
How to prove that a language is not context-free?
We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
- 71.6k
29
votes
4
answers
5k
views
How to determine likely connections in a social network?
I am curious in determining an approach to tackling a "suggested friends" algorithm.
Facebook has a feature in which it will recommended individuals to you which it thinks you may be acquainted with. ...
- 621
18
votes
5
answers
1k
views
Is it possible to solve the halting problem if you have a constrained or a predictable input?
The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case?
For ...
- 3,028
22
votes
2
answers
5k
views
How is a JIT compiler different from an ordinary compiler?
There's been a lot of hype about JIT compilers for languages like Java, Ruby, and Python. How are JIT compilers different from C/C++ compilers, and why are the compilers written for Java, Ruby or ...
- 3,028
21
votes
3
answers
1k
views
Are today's massive parallel processing units able to run cellular automata efficiently?
I wonder whether the massively parallel computation units provided in graphic cards nowadays (one that is programmable in OpenCL, for example) are good enough to simulate 1D cellular automata (or ...
- 1,460
73
votes
4
answers
33k
views
(When) is hash table lookup O(1)?
It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item ...
13
votes
1
answer
2k
views
Analyzing a modified version of the card-game "War"
A simple game usually played by children, the game of War is played by two people using a standard deck of 52 playing cards. Initially, the deck is shuffled and all cards are dealt two the two players,...
- 12.7k
6
votes
1
answer
340
views
Reflection on Concurrency
Reflection is a common mechanism for accessing and changing the structure of a program at run-time, found in many dynamic programming languages such as Smalltalk, Ruby and Python, and in impoverished ...
- 20.1k
9
votes
1
answer
194
views
Influence of the dimension of cellular automata on complexity classes
Let's take as an example the 3d → 2d reduction: What's the cost of simulating a 3d cellular automaton by a 2d cellular automaton?
Here is a bunch of more specific questions:
What kind of algorithms ...
- 1,460
20
votes
3
answers
1k
views
Parsing arbitrary context-free grammars, mostly short snippets
I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, ...
19
votes
3
answers
1k
views
Problems Implementing Closures in Non-functional Settings
In programming languages, closures are a popular and often desired feature. Wikipedia says (emphasis mine):
In computer science, a closure (...) is a function together with a referencing ...
- 71.6k
12
votes
4
answers
336
views
Why store self and parent links (. and ..) in a directory entry?
Consider an filesystem targeted at some embedded devices that does little more than store files in a hierarchical directory structure. This filesystem lacks many of the operations you may be used to ...
9
votes
2
answers
1k
views
Round-robin scheduling: allow listing a process multiple times?
In a round-robin scheduler, adding a process multiple times to the process list is a cheap way to give it higher priority.
I wonder how practical an approach this might be. What benefit does it have ...
10
votes
1
answer
1k
views
Are two-level schedulers only useful to manage swapping?
Two-level scheduling is useful when a system is running more processes than fit in RAM: a lower-level scheduler switches between resident processes, and a higher-level scheduler swaps groups of ...
10
votes
1
answer
224
views
Stability for couples in the Stable Matching Problem
In the Stable Matching Problem, it is stated that there can exist cases where the $m$ list of men can be content with their decisions, yet the list of $f$ cannot when the algorithm is run with men's ...
- 621
21
votes
1
answer
11k
views
Easy reduction from 3SAT to Hamiltonian path problem
There is a reduction in Sipser's book "Introduction to the theory of computation" on page 286 from 3SAT to Hamiltonian path problem.
Is there a simpler reduction?
By simpler I mean a reduction ...
- 21.9k
13
votes
2
answers
880
views
Identifying events related to dates in a paragraph
Is there an algorithmic approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph?
Example, consider the following paragraph:
In June 1970, the ...
- 530
20
votes
1
answer
3k
views
Implementing the GSAT algorithm - How to select which literal to flip?
The GSAT algorithm is, for the most part, straight forward: You get a formula in conjunctive normal form and flip the literals of the clauses until you find a solution that satisfies the formula or ...
- 303
55
votes
4
answers
8k
views
Why polynomial time is called "efficient"?
Why in computer science any complexity which is at most polynomial is considered efficient?
For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms ...
- 20.5k
12
votes
1
answer
4k
views
Is an infinite union of context-free languages always context-free?
Let $L_1$, $L_2$, $L_3$, $\dots$ be an infinite sequence of context-free languages, each of
which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $;
i....
- 2,163
8
votes
1
answer
325
views
The essential difference between spiking neural networks and earlier generation ANN's
I have been studying Spiking Neural Networks online from various papers, mainly Maass (1997). I am not entirely sure I understand what makes SNN's pulse-code in contrast to earlier ANNs which are ...
Amir
20
votes
5
answers
2k
views
A Case Distinction on Dynamic Programming: Example Needed!
I have been working on dynamic programming for some time. The canonical way to evaluate a dynamic programming recursion is by creating a table of all necessary values and filling it row by row. See ...
- 71.6k
28
votes
4
answers
41k
views
The time complexity of finding the diameter of a graph
What is the time complexity of finding the diameter of a graph
$G=(V,E)$?
${O}(|V|^2)$
${O}(|V|^2+|V| \cdot |E|)$
${O}(|V|^2\cdot |E|)$
${O}(|V|\cdot |E|^2)$
The diameter of a ...
- 2,163
40
votes
5
answers
119k
views
How to come up with the runtime of algorithms? [duplicate]
I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site.
I've seen in many sites and books, the big-O notations like $O(n)$ which tell the ...
- 523
23
votes
2
answers
1k
views
Is there a "natural" undecidable language?
Is there any "natural" language which is undecidable?
by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the ...
- 20.5k
20
votes
5
answers
609
views
Efficient compression of unlabeled trees
Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $...
- 71.6k
16
votes
3
answers
1k
views
Efficient encoding of sudoku puzzles
Specifying any arbitrary 9x9 grid requires giving the position and value of each square. A naïve encoding for this might give 81 (x, y, value) triplets, requiring 4 bits for each x, y, and value (1-9 =...
- 1,052
16
votes
3
answers
3k
views
What are the possible sets of word lengths in a regular language?
Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$:
$$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$
Which sets of integers can be the length set of a regular language?...
11
votes
3
answers
8k
views
Minimum number of clues to fully specify any sudoku?
We know from this paper that there does not exist a puzzle that can be solved starting with 16 or fewer clues, but it implies that there does exist a puzzle that can be solved from 17 clues. Can all ...
- 1,052
12
votes
5
answers
3k
views
A sufficient and necessary condition about regularity of a language
Which of the following statements is correct?
sufficient and necessary conditions about regularity of a language exist but not discovered yet.
There's no sufficient and necessary ...
- 2,163
21
votes
1
answer
552
views
Ratio of decidable problems
Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested ...
23
votes
1
answer
1k
views
Is there an equivalent of van Emde Boas trees for ropes?
Someone I know is planning on implementing a text editor in the near future, which prompted me to think about what kind of data structures are fast for a text editor. The most used structures are ...
- 8,986
4
votes
1
answer
595
views
How to determine if a database schema violates one of the less known normal forms?
In database normalization, 1NF (no multivalued attributes), 2NF (all non-PK attributes depending only on PK attributes) and 3NF (all non-PK attributes depending on all of the PK attributes) are widely ...
10
votes
1
answer
286
views
Analysis of and references for Koch-snowflake-like (and other exotic) network topologies
In computer networking and high-performance cluster computer design, network topology refers to the design of the way in which nodes are connected by links to form a communication network. Common ...
- 12.7k
20
votes
2
answers
4k
views
Type-checking algorithms
I am starting a personal bibliographic research on type-checking algorithms and want some tips. What are the most commonly used type-checking algorithms, strategies and general techniques?
I am ...
20
votes
1
answer
458
views
Equivalence of Kolmogorov-Complexity definitions
There are many ways to define the Kolmogorov-Complexity, and usually, all these definitions they are equivalent up to an additive constant. That is if $K_1$ and $K_2$ are kolmogorov complexity ...
- 20.5k