CSC300 / CSC402: Week 10: Review

(Click here for one slide per page)

The final exam covers chapters 1-2 of the text (except 2.2 and 2.3).

Ideally, you should be comfortable with all of the following:

• arrays
• loops over an array
• resizing arrays
• loop invariants
• recursive functions over an array, forward and backward
• accessors and mutators using a loop over
  • singly linked list
  • doubly linked list
• binary search
• stacks and queues, both array and linked list implementations
• union find: QuickFind, QuickUnion, WeightedQuickUnion
• binary heap, sink and swim, insert, find min/max, delete min/max
• priority queues: unordered and ordered array implementations and binary heap implementation
• adding arithmetic and geometric series
• order of growth
• time complexity of
  • "resizing" arrays
  • insert, find, delete on unsorted array
  • insert, find, delete on sorted array
  • binary search
  • independent nested loops
  • dependent nested loops
  • simple recursive functions
  • selection sort (worst N^2, best N^2)
  • insertion sort (worst N^2, best N)
  • binary heap operations
  • heap sort (worst N*log N)