mrk
  • Member for 9 years, 5 months
  • Last seen more than a month ago
How to show that a "reversed" regular language is regular
34 votes

You have to show that you can always construct a finite automaton that accepts strings in $L^R$ given a finite automaton that accepts strings in $L$. Here is a procedure to do that. Reverse all the ...

View answer
What does "non-pathological data" mean?
11 votes

Pathological data is data that will make the algorithm perform bad. For hash tables, pathological data is data that causes collisions. That of course depends on the hash function being used. For ...

View answer
Star operation in CS theory
8 votes

The $^*$ is an operator that takes a language (not only regular languages) $L$ and produces a new language $L^*$ called the Kleene closure of $L$. A language is a set of strings over a finite alphabet ...

View answer
A vector-like data structure with allocation table; O(1) indexing time required
7 votes

The indexing time is always O(1) for an array whether you reallocate or not! Reallocating is not a bad idea if the table size doubles each time the array overflows, insertion takes constant time ...

View answer
How to find whether a grammar's language is finite or infinite?
6 votes

The only way a finite system (grammar) can generate an infinite set of words is by repeating stuff: you start at $S$ and keep expanding until you hit a non-terminal that you've already expanded. So ...

View answer
What is tail recursion?
6 votes

Tail-recursion is a form of recursion in which the recursive calls are the last instructions in the function (that's where the tail part comes from). Moreover, the recursive call must not be composed ...

View answer
Don't understand the merge part of the mergesort
Accepted answer
5 votes

The merge subroutine takes two sorted arrays and creates one sorted array out of these two arrays. It does so in linear time. Say the sorted arrays are A = [1 2 3] and B = [2 3 4]. Since these two ...

View answer
How is a nondeterminisitic automaton running on an input?
5 votes

The computation of a non-deterministic automaton can be modeled by a tree. The input is accepted if there is a root-to-leaf path that eats the input and terminates in an accepting state. When the ...

View answer
Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }
5 votes

Hint: find a PDA for the language $\{a^kb^k:k\ge 0\}$ and apply it twice. The other approach is to find a grammar for the language and convert it to an equivalent PDA. Here is the grammar version: $...

View answer
Can we say DFA is more efficient than NFA?
5 votes

In terms of power, they are equivalent as you said and there is an algorithm (subset construction) for converting an NFA to an equivalent DFA. As you might tell from the algorithm's name, it ...

View answer
Explaining why a grammar is not LL(1)
5 votes

If the grammar is ambiguous (at least one sentence has more than one parse tree), then the grammar is not in LL(1). In general, you compute the LL(1) parse table and use it to answer the question. ...

View answer
Reconstruct directed graph from list of ancestors for each node
4 votes

Such a list can yield more than one graph. Consider 4: 1 2 3, 3: 2 1, 2: 1. One graph is $1\to 2, 2\to3, 3\to4$. A second graph is $1\to 2, 2\to3, 3\to4 , 2\to4$.

View answer
Average between n numbers
4 votes

I'll assume that you are computing the average of the elements of an array of fixed size and that you can change the value at some position at any moment. You want a data structure that supports the ...

View answer
How to implement graph search to solve Sudoku puzzle
4 votes

A graph is defined abstractly as a set of vertices together with a set of edges connecting those vertices. You have to give the vertices/edges meaning to make sense of the problem. For Sudoku, a ...

View answer
Giving a regular grammar for the language
4 votes

That's fairly easy. Just take a non-terminal X and add the rule $X\to aY$ where $a$ is the label on the arrow from $X$ to $Y$ if $X$ is not final; if it's final add a rule like: $X\to \epsilon$ as ...

View answer
Context free grammar for $1^k0^{2k}$
4 votes

Based on the comments: $$S \to 1S00 \mid 100$$

View answer
How can $ww = www$ hold for any word $w$?
4 votes

A string of length $2$ cannot be equal to a string of length $3$. But a string constructed by concatenation of $2$ strings may be equal to a string constructed by concatenating $3$ strings. The empty ...

View answer
Is $O$ contained in $\Theta$?
4 votes

Think about it this way: every function that does "no worse than n" and "no better than n" is also a function that does "no worse than n". The "no better than n" part is just an additional constraint. ...

View answer
If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?
3 votes

If all edge costs are equal, then any spanning tree is also a minimum spanning tree. In this case, any algorithm that solves REACHABILITY solves MST as well. Let S = {v0} be a set of nodes initially ...

View answer
What is an Efficient Algorithm?
3 votes

In theory, an algorithm is said to be efficient if its worst-case running time is bounded by a polynomial in it's input length. The reasoning being that polynomials have nice closure properties. ...

View answer
Is there a single valid definition for a Turing Machine, or is it mutable?
3 votes

There are several valid definition of a Turing machine but they (the TM's) are all equivalent in power (they all compute the same functions). You could use the original definition (coined by Alan ...

View answer
Proof of equivalence of parse-trees and derivations
Accepted answer
3 votes

Theorem. Let $G = (V, T, P, S)$ be a Context-free Grammar. Then $\forall A \in V, A \rightarrow^* \alpha \Leftrightarrow \exists$ a parse-tree $T'$ rooted at node $A$ with yield $\alpha \in (V \cup T)^...

View answer
The order of growth analysis for simple loop
3 votes

The first loop runs $\log_2N$ times but in nested loops we are interested in the running time of the inner loop (thanks to Tsuyoshi Ito for the clarification). The second loop depends on the value of $...

View answer
What if a formal grammar cannot be terminated?
3 votes

You can apply any rule in the set of productions P. The result is called a sentential form. A sentential form belongs to the language recognized by the grammar if it consists of terminal symbols only. ...

View answer
What is the Big Theta of $(\log n)^2-9\log n+7$?
2 votes

Hint: what is the answer for $n^2-9n+7$ ?

View answer
Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle?
2 votes

In a tree, there is exactly one path between any pair of vertices. When you add edge e1 you close that unique path to form a unique cycle.

View answer
Algorithm: Dimension increase in 1D representation of Square Matrix
2 votes

You can use two linked lists. The first one holds the matrix entries and the second one points to the entries that are endpoints of rows. To add a new dimension, scan the second list and insert the ...

View answer
What is the difference between maximal flow and maximum flow?
2 votes

Boils down to knowing the difference between maximal and maximum. maximal is relative whereas maximum is absolute. I guess, maximal flow means maximum flow in a sub-network but I'm not sure.

View answer
number of edges in a graph
2 votes

Method 1 This is one kind of problem you can write a program to solve instantly. We are counting the number pairs satisfying the conditions you state. First generate the vertices (I'm using Python). ...

View answer
Do sparse graphs have to be large?
2 votes

A graph is dense if the number of edges is closer to the maximum number of edges there could be. Formally, a graph is dense if $e=\cal \Omega(v^2)$ where $v,e$ are the number of vertices and edges. A ...

View answer