Problem Detail: Please consider the following Divide-And-Conquer Problem: You’re consulting for a small computation-intensive investment company, and they have the following type of problem that they want to solve over and over. A typical instance of the problem is the following. Read More …
Category: Uncategorized
[Solved]: Performance impact due to time required for shuffling in Quicksort
Problem Detail: As a programmer with non CS background, I am learning algorithms. When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the time/space needed for shuffling. Read More …
[Solved]: What is postorder traversal on this simple tree?
Problem Detail: Given the following tree: Which traversal method would give as result the following output: CDBEA? The answer in my study guide is Postorder, but I think postorder would output: DEBCA. Am I wrong? Asked By : Jorge Zapata Answered By Read More …
[Solved]: Complexity of keeping track of $K$ smallest integers in a stream
Problem Detail: I need to analyze the time complexity of an online algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers. The algorithm is Suppose the $i$th number in the stream is $S_i$. Keep a max Read More …
[Solved]: What is the exact meaning of a Predicate, decidability and computability?
Problem Detail: In the Computability, Complexity and Languages book written by Davis in page 5 he defines a predicate as: By a predicate or a Boolean-valued function on a set $S$ we mean a total function $P$ on $S$ such that Read More …
[Solved]: Hardware interrupts from keystrokes
Problem Detail: If there is an interrupt from every keypress (or one for keydown, one for keyup, one for keypress?) how does the OS handle so many interrupts at the same time. A person typing at 120WPM would be sending more Read More …
[Solved]: Are there any open source SAT solvers with UNSAT core extraction algorithm built in?
Problem Detail: Just like the title says. I need to use a SAT solver on a series of CNF formulas but not only do I need an answer of the type satisfiable/unsatisfiable but also some subset of clauses whose conjunction is Read More …
[Solved]: If the universe were predetermined, would non-deterministic automata still make sense?
Problem Detail: If the universe were governed by predeterminism (i.e. some deity decided in advance how everything, ever, would play out), would the notion of non-deterministic automata make sense? Or would it not, but we wouldn’t know it? Asked By : JesseTG Read More …
[Solved]: minimizing the summed cardinality of set unions
Problem Detail: this optimization problem, I am working on, is kind of making me crazy. 😉 Given is a list o of sets (with finite cardinality) of strictly positive integer values (Z>0), e.g.: o_without_sizes = [ {1, 2, 3, 4} , Read More …
[Solved]: Dynamic Programming Travel Planning Problem
Problem Detail: You want to visit n cities: $0 → 1 → 2 → · · · → n$. For traveling between city $i$ and $i + 1$ $(0 ≤ i < n) $ you need to choose between two modes Read More …
