Weekly outline

  • General

  • 23 June - 29 June

    Week 1: Describing and Analyzing Algorithms

    Tuesday: Fundamentals

    • Problem Descriptions
    • Algorithm Descriptions: Pseudocode
    • Time and Space Performance
    • Algorithms and Engineering
    • (Short class: Instructor leaves early for talk)

    Thursday: Analysis

    • Abstracting performance
    • Abstractions of big-O analysis
    • The big-O notation
    • Correctness of algorithms
      • Partial correctness
      • Total correctness

    Reading: Textbook Chapter 1

  • 30 June - 6 July

    Week 2: Iteration and Recursion

    Tuesday: Looping Over Arrays

    • Scanning for array elements
    • Organizing array elements
    • Basic sorting: selection

    Tuesday: Looping Over Arrays

    • Basic sorting: insertion
    • Recursive efficient sorting: mergesort
    • Counting sort
    • Radix sort

    Reading: Textbook 2.1, 2.4, 7

    • 7 July - 13 July

      Week 3: Recursion and ADTs

      Tuesday: Recursion On Arrays

      • Binary search
      • Binary search as tail recursion
      • Quicksort

      Reading:

      Thursday: ADTs Reviewed

      • Structure of an ADT

      (short class due to HVAC issues)

    • 14 July - 20 July

      Week 4: More Recursion

      Tuesday: The PQ and The Heap

      • Tree Traversal
      • The PQ ADT
      • Inefficient PQ implementations
      • Binary Heap
      • Heapsort
      • Trees and Graphs: Definition and Representation

      Thursday: Recurrences

      • A proof of the Master Theorem
      • Applying the Master Theorem
      • Solving recurrences without the Master Theorem

      Reading:

    • 21 July - 27 July

      Week 5: Algorithms on Trees and Graphs

      Tuesday: Spanning Trees

      • Depth-First Spanning Trees
      • Prim's Algorithm
      • Kruskal's Algorithm
      • Euclidean Planar Free-Space

      Thursday: Shortest Paths; Quiz

      • Dijkstra's Algorithm
      • Quiz

    • 28 July - 3 August

      Week 6: Selected Topics

      Tuesday: Optimized Shortest-Path

      Thursday: Hashing; Randomness

      • Hashing
        • Hash functions
        • Hash tables
          • Bucket hashing
          • Open hashing
        • Hash table grow / shrink

      • Randomness

        • RNGs and PRNGs
        • Random distributions; shuffling
        • Finding large random pseudoprimes: Miller-Rabin

      • Hash Table

      • Hash Function
      • RNG
      • PRNG

      • 4 August - 10 August

        Week 7: Selected Topics

        Tuesday: Memoization and Dynamic Programming

        • Problem examples
          • All-Pairs Shortest Paths as remembering
          • Fibonacci and Fibonacci-time
          • Let's pack a knapsack!
        • Memoization
          • How it works
          • What it does: complexity
        • Dynamic Programming
          • How it works
          • What it does: complexity
        • Comparing memoization and dynamic programming
        • When this all fails

        Thursday: NP-completeness

        • Polynomial, exponential, undecidable
        • Nondeterministic Computation
        • Two views of NP
          • super-parallel
          • super-guesser
        • Completeness for a class
          • in the class
          • hard for the class
        • NP-hard and NP-complete
          • The reduction method for proving hardness
        • An NP-completeness proof
          • The Tents problem
          • Tents is in NP
          • Tents is NP-hard
          • Reduction from max-clique
        • Why it all matters so much
          • Important existing problems are NPC
          • You need to watch for NPH problems

      • 11 August - 17 August

        Week 8: Review and Exam