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. If you have an unavoidable conflict with the date of an exam, please see me as soon as possible (before the exam date!) to discuss options for rescheduling. Last minute rescheduling/extensions will not be accommodated for something known about in advance.

The exam is closed book:

• The sums and recurrence relations tables and logarithm/exponent rules from class will be provided if needed.
• You may use one page of notes (one side of an 8.5x11" piece of paper), which will be handed in with the exam. This page may be handwritten or typed and can contain whatever you would like, but it must be a hardcopy — on a piece of paper, not a laptop, tablet, phone, or other device — and must be personally prepared by you — you may not copy another student's page or hand out copies of yours to others. Creating your own notes is an essential part of the learning process — deciding what to include requires engagement with the material which reinforces understanding and improves long-term retention of the material, provides an opportunity for review in order to identify gaps in your knowledge in time to ask questions before the exam, increases confidence in what you do know, and encourages taking ownership of your own learning.

The exam will focus on ADTs, data structures, and fundamental algorithms, 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
  • 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
• fundamental tasks: sorting, searching, selection
  • what each task is
  • the main algorithms for each task and the running times of those algorithms

Homeworks 2-4 and part of homework 5 (#3-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.

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.