Old Schedule

Lecture Notes

The course textbook is Data Structures & Algorithms, 2nd edition, by Goodrich, Tamassia, and Mount.

• For a review of C++, see chapter 1 of the textbook (we will not use much from chapter 2). In particular, focus on classes and pointers.
• Chapter 3 (Arrays, Linked Lists, Recursion) of the textbook:
  • Arrays, singly-linked lists, doubly-linked lists, circular lists, and recursion.
  • Point struct, and Intvec dynamic array code
  • Using a header file: Intvec.h and Intvec.cpp
  • Sample code for a singly-linked list (not object-oriented); Sample code for a singly-linked list (object- oriented)
  • Sample recursion code
• Chapter 4 (Analysis Tools) of the textbook:
  • The 7 basic functions used in the book.
  • Basic ideas of algorithm analysis, e.g. counting primitive operations.
  • Definition of big-O for big-O notation. Use this definition to prove basic facts about big-O notation (e.g. examples 4.10 - 4.14 on p. 169).
• Chapter 5 (Stacks, Queues, and Deques) of the textbook:
  • Abstract data type: see definition on p. 68 of the textbook
  • stacks, queues, and deques
  • You do not need to know about the details of how the textbook uses templates and exceptions in it implementations (although you may want to read that on your own since it is interesting and useful!). Please stick to the simpler style used in the lectures and course notes on this page.

The midterm covers everything before this point.

• We’ll skip chapter 6 of the textbook. It discusses lists and iterator ADTs, which you may want to look at for more examples of using ADTs. But you don’t need to know any specific details.
• An example of how to test functions. Questions about testing techniques will not be on exams for this course. They are included here as help with your assignments.
• Chapter 7 (Trees) and Chapter 10 (search trees) of the textbook
  • Definition and terminology for general trees.
  • Tree traversal algorithms.
  • Binary trees.
  • Binary search trees (BSTs): search, (leaf) insert, basic delete. Sections 10.1 and 10.2.
  • Balanced binary search trees (e.g. AVL trees)
    • Know how to do AVL tree search (same as BST search) and insertion (single and double rotations) by hand. You don’t need to know how to do AVL deletion.
    • Know that AVL trees are not the only kind of balanced tree. There are also red-black trees and splay trees (see textbook). You don’t need to know any details about these other trees.
    • Here are some animations of AVL trees that might be helpful when practicing insertions. The site also links to many other nice algorithm animations.
• Chapter 8 of the textbook (Heaps and priority queues)
  • Know the priority queue ADT, and why it is useful (e.g. sorting).
  • Know the heap property, and be able to implement the heap insert and remove algorithms.
  • Be able to explain why the performance of heaps is so good.
  • Implement a priority queue as an unordered vector, an ordered vector, or a min-heap, and also understand their performance characteristics (e.g. using O-notation).
  • Notes on templated functions using a priority queue sort function as the example.
• Chapter 9 of the textbook (Hash Tables, Maps, and Skip Lists)
  • Know the basic map ADT
  • Section 9.2: bucket arrays, hash functions/codes, compression functions, collision-handling, load factors, rehashing
  • Section 9.3: binary search on an ordered table
  • Skip lists won’t be covered in this course — skip them!
• Chapter 10 of the textbook (Sorting, Sets, and Selection)
  • mergesort and quicksort are the two main sorting algorithms
  • binary search is also important: it’s covered on pages 395-398 of the textbook
  • some animations of basic sorting algorithms:
    • bubble sort, insertion sort, selection sort, quicksort, mergesort
    • Sorting Out Sorting is a classic sorting animation video. It’s a bit long, but does a good job covering all the basic sorts.
    • this page shows various sorting routines competing against each other (on small amounts of data)
    • many other sorting algorithm animations can be found on YouTube and the web, e.g. quicksort as a Hungarian dance
  • p. 526-527 of the textbook: know how to prove the lower-bound complexity of comparison-based sorting, i.e. that no comparison-based sorting algorithm can do better then O(n log n) comparisons in the worst case; my notes on lower bounds for sorting
  • know bucket sort and radix sort; here’s a good animation of radix sort that clearly shows how it works
  • know what stable sorting is, and why it is useful; some notes on stable sorting

The final covers everything before this point (and nothing after).

• Chapter 13 of the textbook (Graph Algorithms): basic defintions, basic facts, adjacency lists, adjacency matrices, depth-first search, breadth- first search, Dijsktra’a algorithm