Time: Wednesday May 23, 19:00-22:00

Material:

If you use the first edition:

• Section 2.2, Section 2.4.3,
• Chapter 3 (excluding 3.1.3, 3.2.3, 3.2.4, 3.4.3, 3.5),
• Chapter 4,
• Chapter 5 (excluding 5.3.4, 5.5),
• Chapter 6 (excluding 6.3.4, 6.4),
• Chapter 7 (excluding 7.5.3, 7.6.2, 7.7),
• Chapter 9 (excluding pages 369-371 of 9.3.1, 9.4)
• all the pseudocode and proofs posted on the course webpage.

If you use the second edition:

• Section 3.2, Section 3.4.3,
• Chapter 4 (excluding 4.1.3, 4.2.3, 4.2.4, 4.4.4, 4.5),
• Chapter 5 (excluding 5.1.3, 5.1.4),
• Chapter 6 (excluding 6.3.5),
• Chapter 7 (excluding part on Implementing Heap-Sort In-Place of 7.3.4, 7.3.5, 7.4),
• Chapter 8 (excluding 8.6.3, 8.7),
• Chapter 9 (excluding 9.3-9.6),
• Chapter 12 (excluding parts on The Decorator Pattern, A Generic DFS Implemetation in Java and Using the Template Method Pattern for DFS of 12.3.1, 12.4-12.7),
• all the pseudocode and proofs posted on the course webpage.

You will be provided with a list of interfaces and their methods.

The exam is a closed book test. No aids are permitted. Manage your time carefully.

You may either use pseudocode or Java code. Do not worry about specifying exceptions in any of your answers. When you write pseudocode, remember that it must be detailed enough. Roughly speaking, every pseudocode statement should be implementable in constant time, otherwise break it into additional statements. When you write Java code, you may call any of the methods of the interfaces in the list. If you wish to call any other method, then you must write it yourself.