DR. MUGIZI ROBERT RWEBANGIRA -INSTRUCTOR

Carmyn	Jamaal	Kevon	Kristina	Michelle
Qi’Anne	Sharnay	Tacuma	Tonique

Syllabus

Grades

FALL 2009 CLASS

Date	Day	Lec #	Topic	Materials
8/23	M	1	Proof By Induction	wiki, video
8/25	W	2	More Proof By Induction	hw0, hw0sol
8/30	M	3	Yet More Proof By Induction	hw1, hw1sol
9/1	W	4	TEST 1	test1, test1sol
9/6	M		LABOR DAY
9/8	W	5	Recurrence Relations	wiki, video1, video2
9/13	M	6	More recurrence relations and Big-OH notation	hw2, hw2sol, wiki, video
9/15	W	7	More Big-OH notation and Sorting algorithms	wiki, video
9/20	M	8	Analysis of Mergesort	hw3, hw3sol, link1, link2, video
9/22	W	9	TEST 2	test2, test2sol
9/27	M	10	Dynamic Programming: Fibonacci, Binomial Coefficients	wiki, video, notes
9/29	W	11	Dynamic Programming: Longest Common Subsequence	wiki, video
10/4	M	12	Review for Midterm	hw4, hw4sol
10/6	W	13	MIDTERM	mid, midsol
10/11	M		COLUMBUS DAY
10/13	W	14	Dynamic Programming: Knapsack Problem	wiki, video
10/18	M	15	Dynamic Programming: Knapsack Problem
10/20	W	16	Dynamic Programming: Matrix Chain Multiplication	wiki
10/25	M	17	Dynamic Programming: Matrix Chain Multiplication	hw5, hw5sol
10/27	W	18	TEST 3	test3, test3sol
11/1	M	19	Public Key Cryptography: RSA	wiki
11/3	W	20	Public Key Cryptography: RSA
11/8	M	21	NP-Completeness: Bin Packing, FF,FFD	hw6, hw6sol, wiki1, wiki2, link
11/10	W	22	NP-Completeness: Travelling Salesman Problem, Graph Coloring
11/15	M	23	Why Is RSA secure?, Better Modular Exponentiation, Big-OH meaning	hw7, hw7sol
11/17	W	24	TEST 4	test4, test4sol
11/22	M	25	Modular Exponentiation, Linear Homogenous Recurrences	hw8, hw8sol, notes
11/24	W	26	CLASS CANCELLED FOR THANKSGIVING
11/29	M	27	Closed form solution for Fibonacci Sequence using Characteristic Equation Method
12/1	W	28	FINAL	fin, finsol