CS5800 Algorithms Section 2, FALL 2021

about CS5800      home      schedule    gradescope     piazza    

* Schedule and materials subject to change
s
Week / Module Topic / Lecture Other Reading Assignment
  • 9/8 - 9/15


  • Administrative, Intro (CLRS ch1, ch2)
  • Introduction, Example Problems
  • Fibonacci numbers
  • Orders of Growth (CLRS ch3)

Slides: Fibonacci, Strassen, 2 Lists

Recap. These topics are prerequisites:
Discrete Math (Undergrad Honors)


  • Background/prerequisites:
  • * math
  • * datastructures : arrays, trees, lists
  • * pseudocode/ imperative programming
  • * sorting : mergesort, insertionsort

Order of growth table

Podcast : Strassen Matrix Multiplication (adobe pdf)
Podcast: Fibonacci Matrix Exponentiation(adobe pdf)

 EC: math problems

  • 9/15 - 9/22


  (CLRS ch 4)
  Notes: Recurrences
 Example: Iteration Method
 Notes: Master Theorem
Examples: Master Theorem

 Slides : Recurrences

Wikipedia: Divide and Conquer

Extended Master Theorem

slides: Linear Reccurences


  • 9/22 - 9/29



  • InsertionSort
  • MergeSort
  • HeapSort (CLRS ch6)
  • QuickSort (CLRS ch7)

Slides: Sorting part A

Sorting Animation

QuickSort Analysis Avg Case

podcast: QuickSort

Algorithms Thinking Seesion Notes (optional)

  • 9/29 - 10/6



  • QuickSort, Partition (CLRS ch7)

  • Counting Sort, Radix Sort (CLRS ch8)
  • Sorting bounds

  • Median, order statistics (CLRS ch9)

Slides: Sorting part B



  • 10/6 - 10/13

Greedy Algorithms (ch 16)
Sub-problem Structure for Greedy

Lecture Notes: Greedy
Notes: Greedy Techniques
Wikipedia: Greedy
Slides : Greedy

podcast: Subproblem Optimal Structure

podcast: Fractional Knapsack

podcast: Activity Selection Problem
  • 10/13 - 10/20


Greedy VS Dynamic Programming (ch 15)
Sub-problem Structure for DynProg

Notes: Coin change
Notes: CheckBoard
Notes: Discrete Knapsack

Slides : DP1
podcast: discrete knapsack
podcast: coin change
podcast: check board

  • 10/20 - 10/27

Dynamic Programming (ch 15)

Notes: LCS
Notes: Matrix Chain Multiplication

Slides: DP2
SlidesDP2 + OprimalBST

  • 10/27 - 11/3

SAT 10/30 MIDTERM 10AM-6PM

Dynamic Programming (ch 15)
DP problems as DAG Shortest Paths (Notes)



  • 11/3 - 11/10
Week 9/ Recap Simple DataStructures

  • Simple DataStructures Review (CLRS ch10, 12)
  •  
    • 11/3 - 11/10
    Week 9/ DataStructures
    Trees and Hashes
    Skiplists
    Lecture 9 notes



    • Hash Tables (ch 11)
    • RB trees (ch13)

     Hash, RB Tree Slides
    Skiplists   Note ;   Slides ;   Visualizer

     podcast: hash tables
     
    • 11/10 - 11/17



    • 11/17 - 11/24
    •  
    • Week 11 / Graphs I
    • Graps Intro, BFS, DFS
    • DAGs
    • Strongly Connected Components

    • Lecture 11 notes



    • Graphs Intro (ch 22)
    • Minimum Spanning Trees (ch 23)

     Slides

    Podcast: DFS
    Podcast: SCC
    Podcast: MST
    • 11/24 - 12/1

    • ThanksGiving Break, NO CLASS

    • 12/1 - 12/8



    • SSSP:  Bellman Ford
    • SSSP:  Dijkstra

     ASSP: DP by edges
     ASSP: DP by vertices (Floyd Warshall)

    Slides


    • 12/8 - 12/15

    • Week 13 / Graphs III,
    • Network Flows
    • SAT 12/11 FINAL EXAM, 10AM-6PM
      Shillman 3rd floor



    • SP
    • Network Flow
    • MaxFlow-MinCut Theorem
    • Ford-Fulkerson

    Notes

    Slides

     Podcast: MaxFlow

    • 12/15 - 12/18

    • Week 14 / Linear Programming


  • NetFlow: Push-Relabel
  • RSA Math Notes: Number Theory
    Slides: RSA



    • 12/15 - 12/18

    • Week 15 / Advanced Topics (optional)
    • NP-complete Problems, Approx Algorithms, RSA



    • s