Exam 2 Review Information

Exam 2 will be in class. Take care of any necessary business before class so that you do not need to leave the room during the exam.

The exam will focus on ADTs and data structures, though it will also include analysis of algorithms (you will be asked to meet certain running times or give the running time of your implementation). Graphs and graph algorithms will not be on this exam. Specific topics include:

• data structures
  • contiguous vs linked structures (what they are, pros and cons)
  • specific kinds of structures
    • basic data structures (arrays, linked lists, trees + variations like circular arrays, doubly-linked lists, linked lists with tail pointers)
      • what each is
      • carrying out basic operations like traversal, insert, remove
      • running time of those operations
    • more specialized data structures (binary search trees, AVL trees, 2-4 trees, hashtables, heaps)
      • what each is
      • carrying out basic operations like traversal, insert, remove (as well as operations specific to particular data structures, such as heapify)
      • running time of those operations
• categories of ADTs (containers, dictionaries, priority queue) and ADTs (Vector/List/Sequence, Stack, Queue, Map/Dictionary, Set, Priority Queue)
  • the concept
  • typical operations
  • implementations and running times
• rolling your own
  • identifying the needs of a problem
  • considering appropriate standard ADTs/implementations and data structures
  • identifying places for improvement
  • strategies for adapting standard or designing new implementations to "do better", including recognizing what run times come from what kinds of structures

Homeworks 2-4 cover material that may be on the exam. While it is unlikely that there will be questions asking you to simply carry out operations on particular data structures, it is likely that there will be questions that require you to understand how to carry out those operations. You will not be asked to write specific Java code. There are also likely to be design-a-data-structure questions. #2-3 on homework 2, #8 on homework 3, and all of homework 4 are good examples of the kinds of questions to expect.

As with exam 1, you should be able to determine running time from code or a description of an algorithms and should know the major classes of growth rates and their order from slowest-growing to fastest-growing so that you can determine if a specific running time has been achieved. Should they be necessary, the sums and recurrence relation tables and the log/exponent rules sheet will be provided.