Description
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.
-
-
Write the pseudo-code of a polynomial time algorithm which decides if a directed acyclic graph contains a Hamiltonian path.
-
-
-
Prove its complexity.
-
-
-
To what complexity class does the Hamiltonian path problem belong?
-
Ex. 2 — Critical thinking
-
Is the function ⌈log n⌉! bounded by a polynomial?
-
Is the function log∗ log n asymptotically larger than log log∗ n?
-
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.
-
-
Does a given graph have a simple path? * 2. Is a given integer composite?
-
-
-
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.
