3. Midterm 2

3.1. Midterm 2 Structure

• Online, Tuesday, November 11

• Accessible (for 75 minutes) from 8am to 10pm

• 125 points

• Format

  • Similar to Midterm 1

  • Some Multiple Choice, True/False, some writing explanations or workng out problems, etc.

• Anything from Chapter 1-7 is fair to ask about, but focus is on chapters 8-10.

3.2. Topics (1)

• Chapter 8: Sorting

  • How each of the algorithms work

  • The Best/Avg/Worst cost for each

  • Key proofs:

    • Lower bound for Exchange Sorts;

    • Worst case analysis for Radix Sort O(n log n)

    • Lower bound for sorting

3.3. Topics (2)

• Chapter 8: Sorting (cont)

  • Insertion Sort

  • Bubble Sort

  • Selection Sort

  • Shellsort

  • Mergesort

  • Quicksort

  • Heapsort

  • Radix Sort

3.4. Topics (3)

• Chapter 9: File Processing

  • Disk vs RAM memory hierarchy and equipment cost vs. access time

  • Main parts of a disk access: Seek, rotational delay, actual read

  • External Sorting Algorithm

    • Replacement Selection

    • Multiway Merge

3.5. Topics (4)

• Chapter 10: Hashing

• Solves exact match queries exceptionally well

• What makes a hash function good or bad

  • Hash functions: Mod, Binning, mid-square, strings

• What makes a collision resolution good or bad

  • linear probing (possibly by steps)

  • pseudo-random probing

  • quadratic probing

  • double hashing

• How full the table ought to be (space vs. time)

• Expected cost analysis for hashing (when properly implemented)