Problem Detail: $L = left { epsilon right }$ Clearly this language is finite so this must be a regular language. Now since every regular language is Context Sensitive, $L$ is a CSL. We can define the grammar for $L$ as Read More …
Category: Uncategorized
[Solved]: Job scheduling with a bottleneck problem
Problem Detail: Given $n$ jobs $J_1,J_2,…,J_n$, each job requires $T_i > 0, T_i in N$ time to complete. Each job must be pre-processed and post-processed by a single machine M that can handle only 1 job at a time and both Read More …
[Solved]: Are there established complexity classes with real numbers?
Problem Detail: A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P’$ that is known to be NP-complete to my problem $P$ (with a poly-time many-one Read More …
[Solved]: Is there any study or theory behind combining binary search and interpolation search?
Problem Detail: I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files by date/time window. Read More …
[Solved]: Undergraduate Computer Science Textbooks
Problem Detail: What books would you recommend for someone starting B.Sc in Computer Science? My Personal Info: I am currently looking at B.Sc in Computer Science (Games), which is computer science, accept for the last year which is tailored more towards Read More …
[Solved]: Show that the Halting problem is reducible to its complement
Problem Detail: HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ halts on input $w$ The complement of HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ doesn’t halt on input $w$ Show that Read More …
[Solved]: Recommended readings for Probability theory applied to algorithms
Problem Detail: Currently, I’m delving into Analysis of Algorithms and I’ve discovered that I would need to improve my knowledge of Probability Theory. Any recommendation? Where do I start? Thanks in advance! Asked By : vicentazo Answered By : Wandering Logic The best Read More …
[Solved]: Question on SAT reduction
Problem Detail: Let Two-Solutions-SAT be the language of Boolean formulas that have exactly two distinct satisfying assignments. Show Two-Solutions-SAT is co-NP-hard. I know how to show that the complement of Two-Solutions-SAT is in NP, it’s relatively easy to create a nondeterministic Read More …
[Solved]: Master Method to solve recurrences is ‘a’ related to ‘b’?
Problem Detail: The master method allows us to solve certain recurrences of the form $$T(n) = aT(n/b)+f(n),,$$ where $age1$ and $b>1$ are constants and $f(n)$ is a positive function with some further restrictions that aren’t important for this question. The above Read More …
[Solved]: Is set cover still NP-complete if you have a given k?
Problem Detail: Set cover is NP-complete given an arbitrary set $U$, a set $S$ of subsets of $U$, and an integer $k$. However, what if $k$ is always a constant 3? Is that problem still NP-complete? Asked By : TheJKFever Answered By Read More …
