Questions preceded by a * are optional. Although they can be skipped without any deduction, it is important to know and understand the results they contain.
Ex. 1 — Hamiltonian path
• 1. Explain and present Depth-First Search (DFS).
• 2. Explain and present topological sorting.
3. Write the pseudo-code of a polynomial time algorithm which decides if a directed acyclic graph contains a Hamiltonian path.
4. Prove its complexity.
5. To what complexity class does the Hamiltonian path problem belong?
Ex. 2 — Critical thinking
1. Is the function ⌈log n⌉! bounded by a polynomial?
2. Is the function log∗ log n asymptotically larger than log log∗ n?
3. Given eight balls of similar size but where one is lighter, detect which one it is, while minimizing the number of weighting. Provide the pseudocode.
Ex. 3 — Rubik’s Cube
In about half a page explain the game and at least two algorithms to solve it. Provide references.
Ex. 4 — The N P classe
Prove that the following problems are in N P.
1. Does a given graph have a simple path? * 2. Is a given integer composite?
3. Does a given graph have a vertex cover of size k, for some integer k?
Ex. 5 — PRIMES is in P
The PRIMES problem consists in deciding if a given integer n is prime. A simple algorithm to solve PRIMES is trial division which runs in time O(n). Is it sufficient to prove that PRIMES is in P? Explain.
Hint: use the Prime Number Theorem.
