COSC-311: Algorithms

Fall 2019


Section 1 (Prof. Gardner)    Section 2 (Prof. McGeoch)    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/2/19 Sorting
  Weds:
    Syllabus
  Fri:
    Heap review
Mini 1 (due Fri. 9/13 in class) (Solutions)
HW 1: Sorting and Asymptotic Analysis (due Fri. 9/20 in class) (tex file in case you want a template) (Solutions)
CLRS 6
KT 2.5
9/9/19 Asymptotic analysis and recurrences
  Tues:
    Suggestions for time management for long HW assignments (not handed out in class)
  Weds/Thurs:
    Practice with Asympotic Analysis
Mini 2 (due Fri. 9/20 in class) (Solutions)
CLRS 2.3, 3.1
KT 2.1-2.2
9/16/19 More sorting and divide-and-conquer
Mini 3 (due Fri. 9/27 in class) (Solutions)
CLRS 4.3-4.4, 7
KT 5.1-5.2, 13.
9/23/18 Master theorem, divide-and-conquer Mini 4 (due Fri. 10/4 in class)
(Solutions)
HW 2: Divide-and-Conquer (due Fri. 10/11 in class) (tex file in case you want a template) (Solutions)
CLRS 4.5, 8.1, 8.3
9/30/19 Greedy algorithms: making change, interval scheduling, Dijkstra
Mini 5 (due Fri. 10/11 in class) (Solutions)
CLRS 16.1-16.2, 24.3
KT 4.1, 4.4
10/7/19 Minimum spanning trees: Prim's algorithm and Kruskal's algorithm Mini 6 (due Mon./Tues. 10/21-22 in class) (Solutions)
CLRS 23 (see 23.2 for Prim and Kruskal pseudocode and examples)
KT 4.5
10/14/19 Review, MIDTERM (Fri. 10/18)
  Sun:
    Midterm 1 study guide
    Some sample problems
  Weds:
    Pictures from review activity: asymptotic 1, asymptotic 2, sorting algorithms, sorting properties, greedy paradigm, divide-and-conquer paradigm, graphs and Dijkstra
10/21/19 Dynamic programming: making change, weighted interval scheduling
Mini 7 (due Fri. 11/1 in class) (Solutions)
HW 3: Greedy and Dynamic Programming (due Fri. 11/8 in class) (Solutions)
CLRS 15.3 (components of DP algorithm) (see also 15.2, 15.4 for more examples of DP algorithms)
KT 6.1 (weighted interval scheduling, with an example of reconstructing solutions), 6.2 (structure of DP algorithms) (see also 6.3-6.7 for more examples of DP algorithms)
10/28/19 More DP: Bellman-Ford
  Fri:
    Bellman-Ford example
Mini 8 (due Fri. 11/8 in class) (Solutions) KT 6.8 (Bellman-Ford discussion)
11/4/19 Network Flow
  Mon:
    Ford-Fulkerson pseudocode
Mini 9 (due Fri. 11/15 in class) (Solutions)
HW 4: Algorithmic Paradigms and Network Flow (due Weds. 11/20 in class) (Solutions)
KT 7.1 (max flow problem and Ford-Fulkerson), 7.2 (max flow = min cut), 7.5 (bipartite matching), 7.12 (baseball elimination) (see also 7.6-7.11 for more examples of problems that can be solved using NF)
11/11/19
Problem reductions
  Thurs:
    Midterm 2 study guide
    Some sample problems
KT 8.1-8.2 (reductions between IS and VC and from 3-SAT to IS, implications of polynomial time reductions)
11/18/19 NP-hardness and NP-completeness, MIDTERM (Fri. 11/22)
11/25/19
THANKSGIVING BREAK
12/2/19 More on NP-completeness
Mini 10 (due Weds. 12/11 in class) (Solutions)
12/9/19 Approximation algorithms
  Mon:
    Final exam study guide (not handed out in class)
    Sample final (not handed out in class)