Skip to main content
Computer Science

Famous Question

 Famous Question
Question with 10,000 views. This badge can be awarded multiple times.
Awarded 1056 times.
4-color to 3-color polynomial reduction
Awarded Dec 11, 2022 at 23:31
How does the nearest insertion heuristic for TSP work?
Awarded Dec 9, 2022 at 21:46
Maximum depth of a B+ tree
Awarded Dec 5, 2022 at 15:45
Reduction 3SAT and CLIQUE
Awarded Dec 2, 2022 at 2:20
Regular expression without 00 as a substring
Awarded Dec 1, 2022 at 21:26
Is it decidable whether a TM reaches some position on the tape?
Awarded Nov 29, 2022 at 4:21
What is the difference between transition function (delta) and extended transition function (delta hat) in finite automata?
Awarded Nov 26, 2022 at 17:27
(AVL Trees) What is the maximum possible difference between the number of nodes in the root node's subtrees? [duplicate]
Awarded Nov 26, 2022 at 17:12
Determine whether a point lies in a convex hull of points in O(logn)
Awarded Nov 23, 2022 at 2:17
maximum weighted path(s) in a DAG
Awarded Nov 5, 2022 at 10:17
Huffman Coding vs LZW Algorithm
Awarded Nov 3, 2022 at 12:57
What is the complexity of recurrence $T(n) = T(n-1) + 1/n$ [duplicate]
Awarded Nov 3, 2022 at 10:26
Why is the complement of a language that is not regular also not regular?
Awarded Nov 1, 2022 at 0:35
how can i find the Maximum Degree of Concurrency?
Awarded Oct 29, 2022 at 18:30
Can we create recursive functions only by using if-else statements?
Awarded Oct 22, 2022 at 21:50
Solving $T(n)= 3T(n/4)+ n\log n$ without the master method [duplicate]
Awarded Oct 19, 2022 at 18:10
Solving Recurrence Equations containing two Recursion Calls
Awarded Oct 12, 2022 at 1:21
Are depth-first/breadth-first considered special cases of best-first?
Awarded Oct 5, 2022 at 22:41
Show that a language is decidable iff some enumerator enumerates the language in lexicographic order
Awarded Oct 3, 2022 at 17:56
How to find whether a grammar is ambiguous?
Awarded Sep 23, 2022 at 14:17
Kosaraju’s Algorithm - why transpose? [duplicate]
Awarded Sep 20, 2022 at 14:11
Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation
Awarded Sep 20, 2022 at 13:20
Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }
Awarded Sep 5, 2022 at 12:03
Why is every finite language A ⊆ Σ* regular
Awarded Sep 4, 2022 at 20:27
Converting recursive algorithm to DP
Awarded Aug 21, 2022 at 21:42
Would it be possible to use the cloud for RAM?
Awarded Aug 21, 2022 at 4:11
How to solve Tower of Hanoi iteratively?
Awarded Aug 10, 2022 at 1:20
Why is Quicksort described as "in-place" if the sublists take up quite a bit of memory? Surely only something like bubble sort is in-place?
Awarded Aug 7, 2022 at 21:34
What is practical difference between NP and PSPACE-complete?
Awarded Aug 4, 2022 at 9:01
Computational complexity vs Computational cost
Awarded Aug 2, 2022 at 14:57
Is there a O(log n) algorithm for matrix exponentiation?
Awarded Jun 24, 2022 at 13:40
What is the difference between quantum TM and nondetermistic TM?
Awarded Jun 22, 2022 at 17:27
Modifying Dijkstra’s algorithm to favor the path with least amount of edges
Awarded Jun 16, 2022 at 0:11
What determines a hit or a miss for direct mapped cache?
Awarded Jun 13, 2022 at 9:55
What are the advantages of x86 CPUs over ARM?
Awarded May 28, 2022 at 13:41
Do you get DFS if you change the queue to a stack in a BFS implementation?
Awarded May 26, 2022 at 8:31
How to prove {a^(n^2) | n>0} is not context-free?
Awarded May 25, 2022 at 14:57
Difference between multitasking, multithreading and multiprogramming
Awarded May 12, 2022 at 14:27
Decide whether a DFA accepts the empty language
Awarded May 12, 2022 at 8:56
Does a DFA accept an empty string if $q_0$ is the accept state?
Awarded May 3, 2022 at 17:55
Fractional Knapsack in linear time
Awarded Apr 26, 2022 at 0:26
Reduction of 3-SAT to Vertex Cover?
Awarded Apr 25, 2022 at 6:20
When is the AKS primality test actually faster than other tests?
Awarded Apr 17, 2022 at 15:50
How to find max flow in a graph after decrementing an edge capacity?
Awarded Apr 16, 2022 at 21:15
Is it decidable whether a given context free grammar generates an infinite number of strings?
Awarded Apr 11, 2022 at 2:35
What is coinduction?
Awarded Apr 10, 2022 at 9:40
Trying to understand this Quicksort Correctness proof
Awarded Apr 9, 2022 at 19:25
How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]
Awarded Apr 5, 2022 at 23:48
What are the minimum and maximum numbers of elements in a heap of height h?
Awarded Apr 5, 2022 at 19:16
Converting a digraph to an undirected graph in a reversible way
Awarded Mar 30, 2022 at 23:27
Construct a PDA for the complement of $a^nb^nc^n$
Awarded Mar 30, 2022 at 2:48
Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?
Awarded Mar 29, 2022 at 14:27
Does a PDA immediately accept if at final state with empty stack?
Awarded Mar 15, 2022 at 3:48
Language of Turing machines that loop on all inputs, recognizable?
Awarded Mar 12, 2022 at 21:10
How to find a local minimum of a complete binary tree?
Awarded Mar 12, 2022 at 20:31
How to prove P$\neq$NP?
Awarded Mar 9, 2022 at 23:57
reduction from SET-COVER to VERTEX-COVER
Awarded Mar 9, 2022 at 5:05
Is there any uncountable Turing decidable language?
Awarded Mar 8, 2022 at 1:40
How do I construct a doubly connected edge list given a set of line segments?
Awarded Mar 7, 2022 at 0:11
Difference between a TM with an empty language and the one accepting empty string
Awarded Mar 5, 2022 at 18:51
1
…
3 4
5
6 7
…
18