Terence Hang
  • Member for 6 years, 5 months
  • Last seen more than 1 year ago
Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$
Accepted answer
11 votes

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages. Suppose $L$ is context-free. The pumping lemma says there exists some integer ...

View answer
Is an irregular language concatenated with a language with which it has no common symbols irregular?
Accepted answer
8 votes

First, your $L1L2$ is wrong. $$L1L2 = \{a^ib^ic^j\ | \ i>0, j>0\}$$ Your conclusion is right, $L1L2$ is irregular(as long as $L2\neq\phi$, otherwise $L1L2=\phi$ is clearly regular). This can be ...

View answer
Raptor Algorithm: Differences between trip and route
5 votes

Trip represents a sequence of stops plus associated arrival and departure times on each stop. Group all trips by their sequence of stops, ignoring the time information, then each group of trips ...

View answer
BIT: range updates, point queries; true meaning of tree[x]
Accepted answer
3 votes

For BIT and its variants, I recommend this article: http://coutcode.com/blog/binaryindexedtree/ The core of BIT is point update - range query, ie. for array $A[1 \dotsc n]$, BIT supports following ...

View answer
Cormen. Red-black trees. Why do we need to rotate the tree after fixing its properties?
Accepted answer
3 votes

After recoloring in (b), the following rule is still violated: children of a red node are black. Recoloring while preserving black height in step (b) introduces new double red nodes 2 and 7, which ...

View answer
Help with understanding Hopcroft's algorithm
Accepted answer
3 votes

Hopcroft's algorithm works well on complete DFA. (ie. for $M=\{Q,\Sigma,\delta,q_0,F\}$, the transition function $\delta:Q\times\Sigma\to Q$ is a total function). For incomplete DFA with partial ...

View answer
Recursive definition of a language given the regular expression
3 votes

Just replace Kleene stars with $\epsilon$ to find the basis and position, then extend to both direction. $B=\{\epsilon\}$ $\mathcal{F}=\{X\to0X|10X|X1\}$ $L_1 = \langle B \rangle_{\mathcal{F}}$

View answer
Algorithm for constructing BST from post-order traversal
Accepted answer
3 votes

You are in the right track. But the algorithm is incomplete. You missed the case inserting element on the left sub tree and back. Here is the modified algorithm: (Changes marked in bold) Let $n$ ...

View answer
Alternative Method for Computing Two's Complement Binary -> Decimal
Accepted answer
2 votes

No error. in fact, if you add the binary representation of (-38) and 38 as unsigned 7-bit integer without overflowing, you'll get $10000000_2$, then due to overflow the lowest 7 bits is preserved, ...

View answer
How to construct a grammar that generates language L?
Accepted answer
2 votes

One possible grammar is: $G = (N, \Sigma, P, S)$, where $N = \{S,U,V\}$ $\Sigma = \{a,b,c\}$ $P = \{ S \to baUV, U \to ab|bUc, V \to a|aV \}$ The key observation here is breaking $bab^nabc^...

View answer
Maximum bipartite matching when some nodes must be matched
2 votes

Assume the maximum matching problem is $U-V$ matching, and $S\subset U$. Find maximum $S-V$ matching. If the result equals $|S|$, then it is a feasible matching in original $U-V$ matching problem. ...

View answer
augmenting bst - is there exist pair (a,b) of numbers such that |b-a| = d?
2 votes

By "in linear time I can find that pair" I assume you are using two-pointer technique, that using 2 pointers to traversal the array, trying to reduce the gap to the target by advancing one of the ...

View answer
Improve minimum spanning tree with new edge, with better running time than O(|V|)?
Accepted answer
2 votes

Using Heavy path decomposition. The key idea is to partition all edges into heavy edges and light edges. Consider tree edge from parent node X to child node Y: heavy edge: size of sub tree Y is at ...

View answer
count number of different DFS tree of specific graph - ladder
1 votes

You are close. Also remember the order of non-tree edges does not matter. There are actually 2 cases for node 1: $$1 \to 2 \to 4 \to \dotsb$$ Start from node 4, it's just a DFS traversal of ladder ...

View answer
Construct Pushdown Automaton that accepts language $x\in\{a,b\}^*, a=2b$
1 votes

GPDA$\to$PDA Approach See you have got a solution from chat. But the first thing popped my mind is a Generalized_pushdown_automaton(GPDA), which can be constructed pretty straight forward. GPDA ...

View answer
NUMBER OF WAYS TO GET XOR OF n NUMBERS TO BE 0
1 votes

Hints: each bit of xor result depends on all bits on that position only. So each bit can be processed independently, while ignoring the unchanged constraint. process bits from MSB to LSB, the higher ...

View answer
Finding median weights in all paths of an AVL tree with weighted nodes
1 votes

Maintaining one AVL tree for the whole process is enough, and more efficient. Setup another AVL tree T, initially empty. Perform DFS on original AVL tree Insert node to T on entering the node, ...

View answer
Fixing a grammar
0 votes

It is just Left Recursion Removal. The algorithms removing recursion for direct and indirect case are presented on the wiki page. The case in your notes are direct recursion, in general form. $A\to A\...

View answer
Create a grammer for
0 votes

Hint 1. try build some automaton (Turing machine, etc.) that accept strings of given pattern, then encode both states and transitions in the grammar. Hint 2. try some scanning process to generate $\{...

View answer
BIT: Unable to understand update operation in Binary index Tree
0 votes

In BIT query, the trick is removing the last 1 bit. In BIT update is adding the last 1 bit. Write out node n in binary. Set the counter to 0. Repeat the following while n <= N (the largest value ...

View answer
counting binary, with moving position (turing machine)
Accepted answer
0 votes

Noting that every increment starts from the lowest significant bit (LSB). Consider each increment operation this way: starting from LSB, move towards MSB, flipping 1's to 0's until a 0 is encountered. ...

View answer
Understanding Log(n) Loop Invariant
0 votes

Assume input $x \ge 1$, and $x$ is an integer. Loop invariant: $j*2^i \le x < (j+1)*2^i$, or $[x/2^i]=j$ Proof: Initial: $i=0, j=x, x=j*2^i$ Inducing: Suppose after $k_{th}$ loop, we have $j*2^i ...

View answer