Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
Abhishek Ghosh's user avatar
Abhishek Ghosh's user avatar
Abhishek Ghosh's user avatar
Abhishek Ghosh
  • Member for 4 years, 1 month
  • Last seen more than a month ago
7 votes
1 answer
1k views

Prove that "If $L$ is a context-free language, is $\overline{L}$ also context-free?" is undecidable

4 votes
1 answer
1k views

Can a non deterministic finite automaton go into infinite loop?

4 votes
1 answer
120 views

Can reading a value of a variable kill the definition of the variable?

4 votes
1 answer
695 views

Logic behind choosing the exponent bias as $2^7 -1$ instead of $2^7$ in $32$ bits IEEE-754 floating point representation

3 votes
1 answer
563 views

Clarification of the proof involving the regularity condition in Master Theorem

3 votes
2 answers
332 views

Difficulty in understanding the proof of the lemma : "Matroids exhibit the optimal-substructure property"

3 votes
1 answer
428 views

Average Case Analysis of Insertion Sort as dealt in Kenneth Rosen's "Discrete Mathemathematics and its Application"

2 votes
1 answer
106 views

Clarifying $\sum_{h=0}^{\lfloor lg(n)\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n)\rfloor}\frac{h}{2^h})$ in BUILD-MAX-HEAP

2 votes
1 answer
119 views

$\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS

2 votes
1 answer
147 views

Recurrence relation for the number of "references" to two mutually recursive function

2 votes
0 answers
91 views

In Universal Hashing- probability of poor performance is small and is the same for any set of keys of the same size

2 votes
0 answers
576 views

Difficulty in understanding the concept of operand forward in pipeling and when to use split phase

2 votes
1 answer
467 views

Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS

2 votes
2 answers
226 views

Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

2 votes
0 answers
968 views

Understanding the proof of "DFS of undirected graph $G$, yields either tree edge or back edge" better with graph for each statement in proof

2 votes
1 answer
163 views

Analysis of a calculation of expected number of collisions in hashing

2 votes
2 answers
156 views

Tigers and elephants can't drink water from a pond simultaneously, while more than one tiger or more than one elephants can drink water simultaneously

1 vote
1 answer
396 views

Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar

1 vote
0 answers
145 views

Understanding the behavior of Conflict Serializability and View Serializability with respect to blind writes

1 vote
1 answer
394 views

Arguing that the inverse of Ackermann function is upper bounded by a logarithmic function (i.e. $\alpha(n) = O(\lg n)$)

1 vote
1 answer
780 views

Difficulty in understanding the proof of "Every context-sensitive language L is recursive" as given in the Peter Linz text

1 vote
1 answer
185 views

Church-Turing Thesis - the mechanical model - the turing machine- its limits and its equivalence with a modern digital computer

1 vote
1 answer
505 views

Difficulty in understanding a portion in the proof of the $\text{"white path"}$ theorem as with in CLRS text

1 vote
1 answer
121 views

In syntax-directed definition, terminals are assumed to have synthesized attributes only, definition doesn't provide any semantic rules for terminals?

1 vote
1 answer
431 views

Tearing down the FSM description of congestion control

1 vote
1 answer
1k views

What is the actual formula for the efficiency in CSMA/CD?

1 vote
0 answers
104 views

What is the intuitive logic behind the working of the Variable Entered K-Map (VEM)?

1 vote
1 answer
143 views

Doubt in understanding the time complexities of algorithms to recognize regular expressions

1 vote
2 answers
106 views

Relation between programming languages requiring declaration of variables before use and using the token class $\text{id}$ while parsing

1 vote
1 answer
240 views

Understanding the concept of "Viable Prefixes"