
DR. MUGIZI ROBERT RWEBANGIRA INSTRUCTOR 





Alfred

Ayo

Christian

Damina

Demetrius






Howard

Keesha

Rotimi

Shamir


Date 
Day 
Lec # 
Topic 
Materials 
8/24 
M 
1 
What is an algorithm? Important properties of algorithms? 

8/26 
W 
2 
Proof by Induction, other proof strategies. 

8/28 
F 
3 
BigOH notation, Sequential Search, Multiplying two ndigit numbers 

8/31 
M 
4 
Running Time, Binary Search, Selection Sort, Bubble Sort, Insertion Sort 

9/2 
W 
5 
Merge Sort, Recurrence Relations 

9/4 
F 
6 
Better Proofs by Induction 

9/7 
M 

LABOR DAY 

9/9 
W 
7 
Homework 1 Review 

9/11 
F 
8 
Proving Recurrence Relations by Induction 

9/14 
M 
9 
DivideandConquer, Karatsuba’s algorithm 

9/16 
W 
10 
More Analysis of Merge Sort, Karatsuba’s algorithm 

9/18 
F 
11 
Karatsuba’s algorithm, Lower Bounds for Sorting 

9/21 
M 
12 
Lower Bounds for Sorting 

9/23 
W 
13 
Lower Bounds for sorting, NP Complete Problems, Intro to Graph Coloring 

9/25 
F 
14 
Brute Forcing Graph Coloring, Greedy Coloring, Heuristics, Approx algorithms 

9/28 
M 
15 
Travelling Salesman Problem, Nearest Neighbor Heuristic, 2approximation 

9/30 
W 
16 
Travelling Salesman Problem examples 

10/2 
F 
17 
Travelling Salesman Problem Christofides Algorithm 

10/5 
M 
18 
Bin Packing, FF,FFD,NF,BF,BFD 

10/7 
W 
19 
Knapsack Problem, SubsetSum 

10/9 
F 
20 
SubsetSum, Partition 

10/12 
M 

COLUMBUS
DAY 

10/14 
W 
21 
REVIEW 

10/16 
F 
22 
!!MIDTERM!! 

10/19 
M 
23 
REVIEW 

10/21 
W 
24 
Cryptography, Public Key Cryptography, RSA 

10/23 
F 
25 
RSA 

10/26 
M 
26 
Modular Exponentiation, Repeated Squaring Algorithm 

10/28 
W 
27 
Primality Testing, Fermat Primality Test 

10/30 
F 
28 
!!TEST 2!! 

11/2 
M 
29 
Dynamic Programming: Fibonacci numbers 

11/4 
W 
30 
Dynamic Programming: Fibonacci numbers 

11/6 
F 
31 
Dynamic Programming: Fibonacci numbers 

11/9 
M 
32 
Dynamic Programming: Binomial Coefficients 

11/11 
W 

VETERAN’S
DAY 

11/13 
F 
33 
!!TEST 3!! 

11/16 
M 
34 
Dynamic Programming: Binomial Coefficients 

11/18 
W 
35 
Dynamic Programming: Binomial Coefficients 

11/20 
F 
36 
Solving Linear homogenous recurrences 

11/23 
M 
37 
Dynamic Programming: Assembly Line Scheduling 

11/25 
W 
38 
Dynamic Programming: Assembly Line Scheduling 

11/27 
F 

THANKSGIVING 

11/30 
M 
39 
!!TEST 4!! 

12/2 
W 
40 
FINAL EXAM REVIEW 

12/4 
F 
!!!!FINAL!!!! 
Assessment
Assessment Task 
Due Date

Weighting 
Initial
Assessment Exam 
First day of class 
1% 
Homework
Assignment 1 
September 4th 
10% 
Homework
Assignment 2 
September 18th 
10% 
Homework
Assignment 3 
October 2nd 
10% 
Mid Term Exam 
October 16th 
15% 
Homework
Assignment 4 
October 30th 
10% 
Homework
Assignment 5 
November 13th 
10% 
Final Exam 
Examination Period 
20% 