COSC-311: Algorithms

Fall 2018

Home    Schedule and Assignments
***This schedule is meant to give you an idea of the topics covered in this course and their order. It is subject to change and will be updated frequently. I will add assignments and related readings weekly. Please check this page frequently.***
Week of
Topic
Assignment
Related Readings
9/5/18 Sorting
  Weds:
    Syllabus
  Fri:
    Heap review 		Mini 1 (due Weds. 9/12 in class)
HW 1: Sorting and Asymptotic Analysis (due Fri. 9/21 in class) (tex file) 		CLRS 6
KT 2.5
9/10/18 Asymptotic analysis and recurrences
  Fri:
    Practice problems with induction (not handed out in class) 		Mini 2 (due Weds. 9/19 in class)
CLRS 2.3, 3.1, 4.3-4.4
KT 2.1-2.2, 5.1-5.2
9/17/18 More sorting and divide-and-conquer
  Thurs:
    Midterm study guide
    Some sample problems
Mini 3 (due Mon. 9/24 in class)
CLRS 7, 8.1
KT 13.5
9/24/18 Master theorem, MIDTERM (Weds. 9/26) Mini 4 (due Weds. 10/3 in class)
HW 2: Divide-and-Conquer (due Fri. 10/12 in class) 		CLRS 4.5
10/1/18 Divide-and-Conquer and Greedy algorithms
  Mon:
    Correctness of LSS (not handed out in class) 		Mini 5 (due Weds. 10/10 in class)
CLRS 4.1, 16.1-16.2
KT 4.1
10/8/18 More greedy algorithms, graphs Mini 6 (due Weds. 10/17 in class)
HW 3: Greedy and Dynamic Programming (due Fri. 10/26 in class) 		CLRS 24.3
KT 4.4
10/15/18 Greedy algorithms on graphs, Dynamic programming Mini 7 (due Weds. 10/24 in class) CLRS 23
KT 4.5
10/22/18 More dynamic programming
  Sat:
    Midterm study guide
    Some sample problems
Mini 8 (due Weds. 10/31 in class)
HW 4: Algorithmic Paradigms and Network Flow 		CLRS 15.3
KT 6.1-6.2
10/29/18 Wrapping up DP, Network flow
  Mon:
    Bellman-Ford example
    O(nm) Bellman-Ford using adj. matrix
Mini 9 (due Weds. 11/7 in class) KT 7.1-7.2
11/5/18 MIDTERM (Mon. 11/5), Applications of network flow Mini 10 (due Weds. 11/14 in class) KT 7.5, 7.12
11/12/18 Problem reductions
  Fri:
    Graph Coloring 		KT 8.1-8.2, 8.7
11/19/18
THANKSGIVING BREAK
11/26/18 NP-hardness and NP-completeness HW 5: NP-Completeness (due Mon. 12/10 in class)
Mini 11 (due Weds. 12/5 in class) 		CLRS 34.1-34.4
KT 8.3-8.4
12/3/18 More on NP-completeness
  Fri:
    Final exam study guide (not handed out in class)
    Sample final (not handed out in class) (Note: this is last year's exam, which was 50 minutes and NOT cumulative. This year's exam is 3 hours and IS cumulative, so your exam will be longer and contain material from throughout the course.) 		Mini 12 (due Weds. 12/12 in class)
12/10/18 Approximation algorithms