Problem Detail: Consider a DFA over $a,b$ accepting all strings having number of $a$ ‘s divible by 6 and number of $b$ ‘s divisble by 8. What is the minimum number of states in the resultant DFA ? This problem Read More …
Author: ignougroup
[Solved]: What is a forwarding pointer?
Problem Detail: I heard this terminology used today and haven’t come across it before, could someone please explain? Are there any other terms/names that describe this concept? Asked By : jcm Answered By : babou “Forwarding pointer” is the name of a technique Read More …
[Solved]: Computer science for programmers
Problem Detail: I’m a self-taught programmer and have been coding for 8 years. Due to this experience, I’m already very familiar with the principles of programming (such as if-statements, classes, polymorphism, etc.). However, I never learned “computer science,” only programming. What Read More …
[Solved]: Defining a “repeat until”-construct in Denotational semantics
Problem Detail: My Problem is: to define a “repeat until”-construct in terms of Denotational semantics. I made an attempt and now i need to know if i made it right. The Conditions are: i used the language “While” as specified in Read More …
[Solved]: Does a coin tossing algorithm terminate?
Problem Detail: Suppose we have an algorithm like: n = 0 REPEAT c = randomInt(0,1) n = n + 1 UNTIL (c == 0) RETURN n (Assumuing the random number generator produces “good” random numbers in the mathematical sense.) I understand Read More …
[Solved]: Do fully optimizing compilers for terminating programs exist?
Problem Detail: In Andrew W. Appel’s book, Modern Compiler Implementation in ML, he says under chapter 17 that Computability theory shows that it will always be possible to invent new optimizing transformations and proceeds to prove that a fully optimizing compiler Read More …
[Solved]: Finding Hash of Substring [i, j] in O(1) using O(|S|) pre computation
Problem Detail: Given a string S of length n characters, is it possible to calculate the Hash of its substring [i, j] (From index i to index j. Inclusive) in O(1) using some form of precomputation ? Maybe a modification of Read More …
[Solved]: on “On the cruelty of really teaching computing science”
Problem Detail: Dijkstra, in his essay On the cruelty of really teaching computing science, makes the following proposal for an introductory programming course: On the one hand, we teach what looks like the predicate calculus, but we do it very differently Read More …
[Solved]: Proof for variation of Prim’s and Kruskal’s to find maximum-weight acyclic subgraph
Problem Detail: I have been scratching my head to find good counter examples to the following problem: Suppose we are given a directed graph G=(V,E) in which every edge has a distinct positive edge weight. A directed graph is acyclic if Read More …
[Solved]: Are all DFAs also NFAs?
Problem Detail: Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons? Asked By : user2441151 Answered By : Yuval Filmus That depends on how pedantic you are. Morally and semantically speaking, every DFA is an NFA in which there is a unique Read More …
