Problem Detail: You are designing an elevator controller for a building with 25 floors. The controller has two inputs: UP and DOWN. It produces an output indicating the floor that the elevator is on. There is no floor 13. What is Read More …
Author: ignougroup
[Solved]: If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?
Problem Detail: I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it will mean that all problems in NP can 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]: 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]: 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]: Do Higher Order Functions provide more power to Functional Programming?
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 …
[Solved]: Adjacent house , dynamic programming problem
Problem Detail: I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it Read More …
[Solved]: How to find specificity of a regex match?
Problem Detail: I’m thinking about a routing system. Imagine I have the two following regexes pathpart1/pathpart2 => specific match that routes to controller1 .* => catch-all that routes to controller2 And I let them match on a URL, e.g. ‘pathpart1/pathpart2’. They Read More …
[Solved]: Efficient compression of unlabeled trees
Problem Detail: Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $T$ and replace all pointers to $T'$ with Read More …
[Solved]: Finding the largest 3-clique-free induced subgraph
Problem Detail: Consider this problem: Given an undirected graph $G = (V, E)$, find $G’ = (V’, E’)$ such that: $G’$ is an induced subgraph of $G$ $G’$ has no 3-cliques $|V’|$ is maximal So the least number of vertices must Read More …
