CS5114 Theory of Algorithms
Calendar and Coursenotes: Spring 2014

This page will show what we cover each day, including the course notes covered in class.

Reading assignments are also posted for each week. The intention is that you will have finished the reading for that week by the end of the week (that is, typically you would be expected to read material after the associated lecture). However, some folks like to read it before the lecture, so I will try to get it up by the beginning of the week if I can.

• Week 1: Course Introduction, Induction, algorithm analysis
  • Tuesday, January 21: Course introduction, Induction
    Reading Assignment: Manber Chapters 1 and 2, Shaffer material on induction
    Read this paper on Pair Programming, the introducation and Mechansim 1 appear the most relevent to your ability to do the homework in this class.
    Sign up for Piazza
    Today's coursenotes
  • Thursday, January 23: Induction, Algorthm Analysis
    Reading Assignment: Manber Sections 3.1-3.3, Shaffer material on algorithm analysis
    Today's coursenotes
• Week 2: Summationas and Recurrences; Algorithm Design with Induction
  • Tuesday, January 28: Summations and Recurrences
    Reading Assignment: Manber Sections 3.4-2.7. Review Chapter 4, read those sections covering topics that you are not familiar with.
    You can also see another presentation of material on summations and recurrences here, with more advanced material here
    A lot of background on standard data structures is here.
    Today's coursenotes
  • Thursday, January 30: Algorithm Design with Induction
    Today's coursenotes
    Reading Assignment: Manber Sections 5.1-5.5
    Homework Assignment 1 due by 11:00pm.
• Week 3: Algorithm Design with Induction
  • Tuesday, February 4: Dynamic Programming
    Today's coursenotes
    Reading Assignment: Manber Sections 5.6-5.12
    Additional material on dynamic programming can be found here
    
  • Thursday, February 6: Dynamic Programming; Sorting
    Today's coursenotes
    OpenDSA material on Sorting
    Homework Assignment 2 due by 11:00pm.
• Week 4: Sorting;
  • Tuesday, February 11: Sorting
    Today's coursenotes
    Reading Assignment: Manber Section 6.4
    Additional material on sorting can be found here, and material on heaps and heapbuild is here.
  • Thursday, February 13: Class canceled due to snow -- so work on homework!
    Homework Assignment 3 due by 11:00pm.
• Week 5: Lower Bounds Proofs
  • Tuesday, February 18: Lower bounds on search
    Today's coursenotes
    Reading assignment: Manber Sections 6.2 and 6.3, OpenDSA Chapter 7
  • Thursday, February 20: Order Statistics
    Today's coursenotes
    Reading assignment: Manber Section 6.5, OpenDSA Chapter 8
    Homework Assignment 4 due by 11:00pm.
• Week 6:
  • Tuesday, February 25: Midterm
  • Thursday, February 27: String matching, Randomized algorithms
    Today's coursenotes
    Reading assignment: Manber Section 6.7, OpenDSA modules 13.2, 13.3
    Homework Assignment 5 due by 11:00pm.
• Week 7:
  • Tuesday, March 4: Randomized algorithms, random numbers, graphs
    Today's coursenotes
    Reading assignment: Manber Sections 6.9, 7.1-7.3, OpenDSA module 13.4
    
  • Thursday, March 6: Class CANCELLED
    
• SPRING BREAK
  • Thursday, March 13: Homework Assignment 6 due by 11:00pm.
• Week 8:
  • Tuesday, March 18: Graphs: Breadth-first search, topological sort, shortest paths
    Today's coursenotes
    Reading assignment: Manber Sections 7.4-7.6, OpenDSA Chapter 11
    
  • Thursday, March 20: All-pairs shortest paths, Kruskal's algorithm, matching
    Today's coursenotes
    Reading assignment: Manber Sections 7.7, 7.10, OpenDSA Module 10.1
    Homework Assignment 7 due by 11:00pm.
    
• Week 9: Network flow, computational geometry
  • Tuesday, March 25: Network flow
    Today's coursenotes
    Reading assignment: Manber Sections 7.11, 8.1-8.3.
    
  • Thursday, March 27: Computational Geometry
    Today's coursenotes
    Reading assignment: Manber Section 8.4.
    Homework Assignment 8 due by 11:00pm.
    
• Week 10: Computational geometry, Reductions
  • Tuesday, April 1: Closest pairs, intersections, reductions
    Today's coursenotes
    Reading assignment: Manber Section 10.1, OpenDSA Module 14.2
    
  • Thursday, April 3: Codebreaker movie: 2-4pm, Squires 341
    Homework Assignment 9 due by 11:00pm.
    
• Week 11: Reductions, NP-completeness
  • Tuesday, April 8: Reductions, Intro to "hard" problems
    Today's coursenotes
    Reading Assignment: Manber Chapter 10.
  • Thursday, April 10
    Today's coursenotes
    Reading Assignment: Manber Chapter 11.1-11.3, OpenDSA Module 14.3
    Homework Assignment 10 due by 11:00pm.
    
• Week 12: NP-completeness proofs, Coping with NP-Complet Problems
  • Tuesday, April 15: NP Completeness Proofs
    Today's coursenotes
    Reading Assignment: Manber Chapter 11.4
    
  • Thursday, April 17: Coping with NP-Complete Problems
    Today's coursenotes
    Reading Assignment: Manber Chapter 11.5
    Homework Assignment 11 due by 11:00pm.
    
• Week 13: Numeric Problems
  • Tuesday, April 22: Polynomial and Matrix Multiplication
    Today's coursenotes
    Reading Assignment: Manber Sections 9.1-9.5
    
  • Thursday, April 24: Fast Fourier Transform
    Today's coursenotes
    FFT Slideshow
    Reading Assignment: Manber Section 9.6
    Homework Assignment 12 due by 11:00pm.
    
• Week 13: Parallel Algorithms
  • Tuesday, April 29: Parallel concepts, architectures, Brent's Lemma
    Reading Assignment: Manber Sections 12.1-12.3
    Today's coursenotes
    
  • Thursday, May 1: Parallel algorithms
    Reading Assignment: Manber Sections 12.4-12.6
    Today's coursenotes
    Homework Assignment 13 due by 11:00pm.
    
• Week 14: Wrap up
  • Tuesday, May 8: Pipeline processing example; discuss final
    
  • Thursday, May 10:
    Homework Assignment 14 due by 11:00pm.
    Coursenotes for the semester
    
• Final Exam: Wednesday, May 14 @ 1:05-3:05 in the regular classroom