Problem Detail: $G=<V,E>$ is a directed graph. I need to write an efficient algorithm that finds a $v in V$ such that there exists a path $forall w in V$ $v rightarrow w$ ($v$ has a path to every other vertex), Read More …
Category: Uncategorized
[Solved]: Computing FOLLOW sets for LL(1) grammar. Stuck on question
Problem Detail: Calculate the FOLLOW sets for all the non terminals: $S rightarrow bEx mid Db mid b mid F$ $D rightarrow EDc mid Y$ $E rightarrow dED mid dDY$ $Y rightarrow ab mid aDx mid varepsilon$ So I know Read More …
[Solved]: Why not to take the unary representation of numbers in numeric algorithms?
Problem Detail: A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits). For example testing whether a number $n$ is prime or not, requires a loop Read More …
[Solved]: Set cover problem and the existence of such cover
Problem Detail: In the set cover problem we want to find in the $mathbb{S} subset 2^mathbb{U}$ the subset ${s_i}_{1..k}$, such that $cup s_i = mathbb{U}$ for given $K$, where $k le K$. But how to reduce the set cover problem to Read More …
[Solved]: Why is T not a minimum spanning tree of G?
Problem Detail: The Problem: Let T be a tree constructed by Dijkstra’s algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G. a. True of false: T is a spanning tree of G? Read More …
[Solved]: Is $A$ regular if $A^{2}$ is regular?
Problem Detail: If $A^2$ is regular, does it follow that $A$ is regular? My attempt on a proof: Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A cdot A$. Since concatenation of two non-regular language is not Read More …
[Solved]: How to calculate the size of a page in a two level paging CPU?
Problem Detail: I am having difficulties with understanding the concept of paging. As a result I’ve got no idea how I can solve the following exercise – I’m lacking one more equation to solve it. I’ve read a lot about paging Read More …
[Solved]: The language of machines that accepts all palindromes is not Turing recognizable
Problem Detail: I have this question: $L = {langle M rangle | M$ is TM that accepts every palindrome over its alphabet $}$ Proof that $L$ is not Turing-recognizable by showing reduction from other non Turing-recognizable language. What I have tried Read More …
[Solved]: Linear time labeling algorithm for a tree?
Problem Detail: I have an undirected tree whose vertices I want to label. The leaf nodes should be labeled one. Then, assume the leaves were removed. In the tree that remains, the leaves should be labeled two. This process continues in Read More …
[Solved]: Does a context-free grammar with multiple variables have a “starting” point?
Problem Detail: So lets consider the following grammar $$ begin{align*} S &to 0 mid 0A A &to 1 end{align*} $$ would the string “1” be accepted by the language or must the language start with $S$? Asked By : Moddah Answered By Read More …
