Topics for the final

December 15th, 9:45-11:45, 107 EPB

Below I have listed 5 topics that you will be tested on. I have also listed what you should read for each topic. There will be 5 problems on the final exam, one problem for each topic, each problem worth 50 points for a total of 250 points. The exam is worth 25% of your overall grade. Each problem will have 3 or 4 parts and I expect you to spend about 20 minutes on each problem.

Each topic listed below corresponds to an important data structure that we have studied. For each data structure you need to know:

  1. What operations are typically supported by the data structure
  2. Algorithms for implementing these operations
  3. Running times of these algorithms
  4. Some details of Bailey's implementations of these data structures
  5. One or two major applications of these data structures (for example, application of queues to BFS)

I expect that all your answers will be fairly short. Any java code fragment or function you write will be no longer than 10 lines of code. Some possibilities for a typical question on the exam are: (i) add a small new function to Bailey's implementation of a data structure or (ii) how might you implement a small variant of one of the data structures listed below or (iii) analyze the running time of one of Bailey's implementations.

  1. Linked lists
  2. Queues
  3. Stacks
  4. Binary heaps
  5. Binary trees and binary search trees