Problem Detail: I’ve asked a similar question on cstheory.SE. According to this answer on Stackoverflow there is an algorithm that on a non-lazy pure functional programming language has an $Omega(n log n)$ complexity, while the same algorithm in imperative programming is Read More …
Blog
[Solved]: Size of Maximum Matching in Bipartite Graph
Problem Detail: Am I correct in my observation that the cardinality of the maximum matching $M$ of a bipartite graph $G(U, V, E)$ is always equal to $min(|U|, |V|)$? Asked By : ultrajohn Answered By : Nicholas Mancuso Given a bipartite graph $G Read More …
[Solved]: Is there a binary search tree datastructure which can avoid becoming badly weight-balanced?
Problem Detail: This is a follow-up question of “Not all Red-Black trees are balanced?” and “AVL trees are not weight-balanced?“.$defle{leqslant}defge{geqslant}$ Definition: For a rooted tree $T$ and a vertex $v in V(T)$, let $L_T(v)$ be the number of nodes in the Read More …
[Solved]: Big O Notation of $n^{0.999999}log(n)$
Problem Detail: I’m taking the MIT Open Courseware for Introduction to Algorithms and I’m having trouble understanding the first homework problem/solution. We are supposed to compare the asymptotic complexity (big-O) for different functions: $f_1(n) = n^{0.999999}log(n)$ $f_2(n) = 10000000n$ $f_2(n)$ is Read More …
[Solved]: Formal construction of PDA intersecting a DFA
Problem Detail: Given the PDA $P = (Q_P,Sigma,Gamma_P,delta_P,F_P)$ and the DFA $D = (Q_D, Sigma, delta_D,q_D,F_D)$ What is the 6-tuple definition of the PDA such that: $L(P’) = L(P) cap L(D)$ I don’t understand what the intersection of these two FAs Read More …
[Solved]: Supporting data structures for SAT local search
Problem Detail: WalkSAT and GSAT are well-known and simple local search algorithms for solving the Boolean satisfiability problem. The pseudocode for the GSAT algorithm is copied from the question Implementing the GSAT algorithm – How to select which literal to flip? Read More …
[Solved]: What does normalizing with hidden bit really mean?
Problem Detail: I have a question related to representing numbers in base 2 with floating point. For example, if I have such a number $$0.000011 cdot 2^3$$ then is its normalized form this? $$1.1cdot 2^{-2}$$ Generally speaking about normalizing, normalizing with Read More …
[Solved]: Maximum number of matched vertexes in a one-to-many bipartite graph
Problem Detail: I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who are Read More …
[Solved]: Can POSIX BRE express all regular languages?
Problem Detail: It appears that “Basic Regular Expressions” as defined by POSIX.1-2008 do not support alternation, a|b (although some grep implementations recognize the escaped version, |). Since the regular languages are closed under union by definition, does this mean that POSIX Read More …
[Solved]: What is the meaning of this pseudo-code function?
Problem Detail: While reading the paper Holistic twig joins: optimal XML pattern matching I came across the pseudo code for liststack algorithm. (available through google scholar) A function in the algorithm confused me, since I can understand what it is supposed Read More …
