Institut for Matematik og Datalogi Odense Universitet December 3, 1997

JFB

DM19 – E97 – Exam Questions

1. Information-theoretic lower bounds (lower bounds proven by counting leaves in decision trees), especially the worst case and average case bounds for sorting by comparisons.

2. Adversary arguments – technique, examples.

3. Median finding – upper and lower bounds.

4. Greedy algorithms – basic principles, examples.

5. Matroids – definitions, examples.

6. Bellman-Ford algorithm for shortest paths.

7. All-pairs shortest paths.

8. Flows in networks – definitions, max-flow min-cut theorem.

9. Flows in networks – Ford-Fulkerson and Edmonds-Karp methods.

10. Flows in networks – Preflow-push algorithms.

11. Matching – bipartite and nonbipartite.

12. Proof that SATISFIABILITY is NP-complete.

13. NP-completeness proofs – examples.

14. Approximation algorithms for NP-complete problems.

15. Fully polynomial approximation schemes.

16. RSA public-key cryptosystem and primality testing (Miller-Rabin).

17. Sorting networks.

18. Circuits for addition and multiplication.

19. Parallel algorithms – pointer jumping.

20. Parallel algorithms – CRCW vs. EREW, and Brent’s theorem.

21. Parallel algorithms – deterministic symmetry breaking.

22. Fast Fourier Transform.

23. String matching.

24. Computational geometry – sweep line technique.

25. Computational geometry – convex hull algorithms.

The form of the exam You will draw a topic from the list of topics listed above. You will have 30 minutes to prepare your presentation. During this time you can use the book and your notes. You can make short notes that will help you to organize your presentation, but that will have no other technical content. The exam will take about 30 minutes per person. Prepare you presentation so that it takes about 20 minutes. Make sure you cover the most important ideas from your topic, though this may mean that you need to skip some details. Your presentation may be interupted with questions or cut short to go on to other topics. Towards the end of the 30 minute period, you will typically also be asked short questions not related to the material you talked about. The preferred language of the exam is English. However if you have any problems with that, feel free to speak Danish.