Problem Detail: If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time? Intuitively this sounds correct, as BFS does not Read More …
Author: ignougroup
Are there inherently ambiguous and deterministic context-free languages?
Problem Detail: Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise. Let us call a context-free language inherently ambiguous if and only if all context-free grammars which Read More …
Can someone show me step-by-step how to calculate the primitive operations of this algorithm?
Problem Detail: See the example algorithm below from my course notes, I don’t follow the operation counting in the inner loop. Can someone walk me through this step-by-step? Here’s the algorithm: Algorithm PrefixAverages1(A, n): Input: An integer array A of size Read More …
Difference between Normative annexes and Informative annexes in ADA 95
Problem Detail: I was reading the ADA 95 reference manual. I came across these two words in annexes Normative and informative . I couldnt find the difference between those. Your help will be much appreciated. Asked By : Proton Boss Answered By Read More …
How to show that given language is unambiguous
Problem Detail: Given following grammar: $$ begin{align} S rightarrow &A1B A rightarrow & 0A mid varepsilon B rightarrow & 0B mid 1B mid varepsilon end{align} $$ How can I show that this grammar is unambiguous? I need to find a grammar Read More …
Algorithm to test whether a binary tree is a search tree and count complete branches
Problem Detail: I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) with Read More …
Algorithm to write a dictionary using thousands of words to find all anagrams for a given string with O(1) complexity
Problem Detail: Problem Statement: Suppose we have a thousands of words and we need to maintain these words in a data structure in such a way that we should be able to find all anagrams for a given string. I tried Read More …
Why won’t a Turing machine halt?
Problem Detail: I am reading Sipsers. The book introduces halting problem and proves that is a turing recognisable language but not a turing decidable language. Thus giving a Turing machine which does not halt on some inputs. The language to be Read More …
Best solutions to 6 degrees of separation
Problem Detail: From purely my knowledge of computer science a simple breadth first search from root A in search of node B, while keeping track of the depth of the tree, would be the most effective way to check whether A Read More …
How many minimal spanning trees are there when all edge costs are distinct?
Problem Detail: Suppose all costs on edges are distinct. How many minimal spanning trees are possible? I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because Kruskal’s, and Read More …
