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
Related Readings
9/2/19 Sorting
    Heap review
Mini 1 (due Fri. 9/13 in class)
HW 1: Sorting and Asymptotic Analysis (due Fri. 9/20 in class) (tex file in case you want a template)
KT 2.5
9/9/19 Asymptotic analysis and recurrences
    Suggestions for time management for long HW assignments (not handed out in class)
    Practice with Asympotic Analysis   Fri:
    Practice problems with induction (not handed out in class)
Mini 2 (due Fri. 9/20 in class)
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)
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)

HW 2: Divide-and-Conquer (due Fri. 10/11 in class) (tex file in case you want a template)
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)
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)
CLRS 23 (see 23.2 for Prim and Kruskal pseudocode and examples)
KT 4.5
10/14/19 Review, MIDTERM (Fri. 10/18)
    Midterm 1 study guide
    Some sample problems
    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)
HW 3: Greedy and Dynamic Programming (due Fri. 11/8 in class)
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
    Bellman-Ford example
Mini 8 (due Fri. 11/8 in class) KT 6.8 (Bellman-Ford discussion)
11/4/19 Network Flow
    Ford-Fulkerson pseudocode
Mini 9 (due Fri. 11/15 in class)
HW 4: Algorithmic Paradigms and Network Flow (due Weds. 11/20 in class)
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)
Problem reductions
    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)
12/2/19 More on NP-completeness
Mini 10 (due Weds. 12/11 in class)
12/9/19 Approximation algorithms
    Final exam study guide (not handed out in class)
    Sample final (not handed out in class)