Exam 2 Review Information

Exam 2 will be a take-home exam. You may use the textbook, your own notes and problem solutions, the materials posted on the course website, and external websites directly linked from the course website. You may not use other resources, including web resources linked from things the course website links to. You may not get notes or other materials from or share notes or other materials with other students once the exam has been handed out, even if those notes/materials aren't directly related to the exam.

The only person you may discuss the exam with is me - I will answer clarification questions, but the exam is meant to be a demonstration of what you can do so I will not provide help on how to solve the problems.

The exam will focus on ADTs and data structures, though earlier material on analysis of algorithms is unavoidable (you will be asked to meet certain running times or give the running time of your implementation). Graphs 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 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"

Homeworks 3-10 cover material that may be on the exam. There are not likely to be questions asking you to carry out operations on particular data structures, but there may be questions which require you to understand how to carry out those operations. There are also likely to be design-a-data-structure questions similar to homeworks 8 and 10.