Problem Detail: Let us say we know that problem A is hard, then we reduce A to the unknown problem B to prove B is also hard. As an example: we know 3-coloring is hard. Then we reduce 3-coloring to 4-coloring. Read More …
Category: Uncategorized
[Solved]: Quick union and heuristic by size
Problem Detail: Studying Quick-Find and Quick-Union heuristic I’ve found clear that: with quick find trees and a union based on the size of the trees we can make a union in $T_{am}(n)=O(log(n))$ with quick find trees and a union based on Read More …
[Solved]: Is there a way of objectively measuring the efficiency or quality of software or code design?
Problem Detail: I’ve been thinking about ways of measuring code, and, quite frankly, I can’t think of truly objective, semi-universal ways of evaluating the quality or “strength” of code to say, “Yes, this is better than that based on X, Y, Read More …
[Solved]: Efficiently finding $k$ smallest elements of Cartesian product
Problem Detail: Given lists $A_1, A_2, dots, A_n$ of non-negative numbers, I want to find the $k$ smallest elements of the Cartesian product $A_1 times A_2 times dots times A_n$ ordered by the value $x_1 + x_2 + dots + x_n$, Read More …
[Solved]: Automatic translation between formal languages
Problem Detail: There are parser generators (some of which are limited to certain classes of grammars) which, given a grammar, automatically generate a parser for that grammar. Would it be possible to make a general-purpose translator generator to automatically translate from Read More …
[Solved]: Proving the lower bound of compares in comparison based sorting
Problem Detail: I’m reading Sedgewick and Wayne’s book of Algorithm. When I read the following proof in the attached picture, I don’t understand why it assumed the comparison number is lg(number of leaves). Any help is appreciated! Asked By : addego Answered Read More …
[Solved]: Designing context free grammar for a language with range restriction on repetition of alphabets
Problem Detail: I am having issue with designing contex free grammar for the following language: $L = {0^n 1^m , | , 2n leq m leq 3n }$ I can design for the individual cases i.e. for $m geq 2n$ and Read More …
[Solved]: LR(0) parsing: how can I know sets of items corresponding to states?
Problem Detail: I’m studying LR(0) parser. But I don’t understand how sets of items corresponding to states can be calculated. I think The author would miss some information readers must know. Given the following LR(0) automaton, How the set of items Read More …
[Solved]: Conflict Driven Clause Learning backtracking clarification
Problem Detail: On the wikipedia page here it describes pretty well the CDCL algorithm (and it seems the pictures were taken from slides created by Sharad Malik at Princeton). However when describing how to backtrack all it says is “to the Read More …
[Solved]: PDA for all non-palindromic strings of even length
Problem Detail: I had a homework assignment where I had to build a PDA over the alphabet ${a,b}^*$, accepting $L = {x mid x text{ is even but not a palindrome}}$. I already turned it in, but I know I had Read More …
