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 Mini 6 (due Mon./Tues. 10/21-22 in class) CLRS 23
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
10/28/19 Network flow
11/4/19 Applications of network flow
11/11/19 Problem 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
12/9/19 Approximation algorithms