Problem Detail: The knapsack problem is $O(c,n)$ where $c$ is the capacity of knapsack and $n$ is the number of items. Yet it’s exponential because the size of the input is $log(c)$. However, why don’t we emphasize length of input in Read More …
Blog
[Solved]: Is it more effective to vote for a woman?
Problem Detail: A certain political party wants to encourage women to participate in their primary elections, so they decide, that the 4th position is reserved for a woman. That is, if there is no woman in the top 4 positions, then Read More …
[Solved]: How many possible assignments does a CNF sentence have?
Problem Detail: I’m having some trouble understanding the following: When we look at satisfiability problems in conjunctive normal form, an underconstrained problem is one with relatively few clauses constraining the variables. For eg. here is a randomly generated 3-CNF sentence with Read More …
[Solved]: Why is $sum_{j=0}^{lfloorlog (n-1)rfloor}2^j$ in $Theta (n)$?
Problem Detail: I am trying to understand summation for amortization analysis of a hash-table from a MIT lecture video (at time 16:09). Although you guys don’t have to go and look at the video, I feel that the summation he does Read More …
[Solved]: Is it theoretically exist a computer that never affected by computer virus?
Problem Detail: Is it theoretically exist a computer that never affected by computer virus? just wonder if there could be a revolution on the computer? Asked By : Victor Answered By : babou Do you mean “that cannot be affected” or “that was Read More …
[Solved]: Are there some real-world optimization problems with very cheap objective functions?
Problem Detail: Many real world optimization tasks (especially black box optimization) have objective functions, which are quite expensive to evaluate. For example to find the optimal shape of an airplane wing, a computer model of the wing needs to be constructed Read More …
[Solved]: Simple Pushdown Automaton
Problem Detail: I’m currently learning about PDAs and their power when constructing them from Context-Free Grammars, however I’m still unsure of how to properly construct a CFG, and then a PDA from that CFG. In the book, Formal Languages, Automata, and Read More …
[Solved]: Family of types in type theory
Problem Detail: Can anyone simplify the meaning of families of types index by a type. It looks i get it but quite not understood it. What do you mean by a “family” ? I understand index by a value (n length Read More …
[Solved]: Facts about internal and external path lengths of binary tree
Problem Detail: While learning binary tree’s properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search. My book specifies some facts about these as follows: $S_n=1+frac{U_0+U_1+…+U_{n-1}}{n}$ For large $n$, $S_n=2 log_en$ Read More …
[Solved]: Check if adding an edge to a DAG results in a cycle
Problem Detail: On the begining: It is a programming contest problem, but not from on-going one. Unfortunatelly, I can’t provide any link to this task, because it is not publically available. It was from one of the Polish local programming contest Read More …
