DR. MUGIZI ROBERT RWEBANGIRA -INSTRUCTOR

Alfred	Ayo	Christian	Damina	Demetrius
Howard	Keesha	Rotimi	Shamir

Attendance

Grades

Syllabus

Date	Day	Lec #	Topic	Materials
8/24	M	1	What is an algorithm? Important properties of algorithms?	Chapter1, HW0,HW0SOL
8/26	W	2	Proof by Induction, other proof strategies.	HW1, HW1SOL
8/28	F	3	Big-OH notation, Sequential Search, Multiplying two n-digit numbers	Chapter 3
8/31	M	4	Running Time, Binary Search, Selection Sort, Bubble Sort, Insertion Sort	Ch. 4(pt1,pt2)
9/2	W	5	Merge Sort, Recurrence Relations	Chapter 2
9/4	F	6	Better Proofs by Induction	HW2, HW2SOL
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	Divide-and-Conquer, Karatsuba’s algorithm	Solving Recurrences
9/16	W	10	More Analysis of Merge Sort, Karatsuba’s algorithm
9/18	F	11	Karatsuba’s algorithm, Lower Bounds for Sorting	HW3, HW3SOL
9/21	M	12	Lower Bounds for Sorting
9/23	W	13	Lower Bounds for sorting, NP Complete Problems, Intro to Graph Coloring	Ch. 10 (pt1, pt2)
9/25	F	14	Brute Forcing Graph Coloring, Greedy Coloring, Heuristics, Approx algorithms
9/28	M	15	Travelling Salesman Problem, Nearest Neighbor Heuristic, 2-approximation	Ch. 11 (pt1, pt2)
9/30	W	16	Travelling Salesman Problem examples	Mid-term ques.
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, Subset-Sum	HW4A, HW4ASOL
10/9	F	20	Subset-Sum, Partition
10/12	M		COLUMBUS DAY
10/14	W	21	REVIEW	HW4B, HW4BSOL
10/16	F	22	!!MID-TERM!!	MIDTERM, MIDTERMSOL
10/19	M	23	REVIEW	HW4C, HW4CSOL
10/21	W	24	Cryptography, Public Key Cryptography, RSA	HW4D, HW4DSOL
10/23	F	25	RSA
10/26	M	26	Modular Exponentiation, Repeated Squaring Algorithm	HW5A, HW5ASOL
10/28	W	27	Primality Testing, Fermat Primality Test
10/30	F	28	!!TEST 2!!	TEST2, TEST2SOL
11/2	M	29	Dynamic Programming: Fibonacci numbers
11/4	W	30	Dynamic Programming: Fibonacci numbers
11/6	F	31	Dynamic Programming: Fibonacci numbers	HW5B, HW5BSOL
11/9	M	32	Dynamic Programming: Binomial Coefficients	Sample Test3, Sample Test3SOL
11/11	W		VETERAN’S DAY
11/13	F	33	!!TEST 3!!	Test3, Test3SOL
11/16	M	34	Dynamic Programming: Binomial Coefficients	HW5C, HW5CSOL
11/18	W	35	Dynamic Programming: Binomial Coefficients	Solving Lin. Hom. Recurr
11/20	F	36	Solving Linear homogenous recurrences	HW5D, HW5DSOL
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!!	Test4, Test4SOL
12/2	W	40	FINAL EXAM REVIEW
12/4	F		!!!!FINAL!!!!	final, finalsol

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%