Computer Science 282

Design and Analysis of Efficient Algorithms

Fall 2006

Instructor: Daniel Stefankovic (office hours: Tue 1pm-2pm, Thu 1pm-2pm).
Time: T,Th 11:05-12:20.
Location: Computer Studies Building 601.

TA and office hours:

Girts Folkmanis (gfolkman) - Mon 5pm-6pm, Wed 6pm-7pm.

Textbook: Introduction to Algorithms (2nd edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2001.

Other resources/recommended reading:

Algorithm Design, J. Kleinberg and E. Tardos, 2005.
Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani (a draft is available online), 2006.
The Design and Analysis of Algorithms, D. Kozen, 1991.
The Design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher, E. Upfal, 2005.
Randomized Algorithms, R. Motwani, P. Raghavan, 1995.
Approximation Algorithms, V. Vazirani, 2004.

Prerequisites: MTH150 Discrete Mathematics and CSC172 Data Structures.

Schedule

Date	Topic	Reading Due	HW
Sep. 5 Tu	introduction, mergesort	CLRS, Ch. 1,2
Sep. 7 Th	median, recurrences	CLRS, Ch. 3 and Sec. 4.1, 4.2, 4.3, 9.3	HW 1, due 9/14
Sep. 12 Tu	heapsort	CLRS, Ch. 6, 10
Sep. 14 Th	randomness	CLRS, Ch. 5, Appendix C	HW 2, due 9/21
Sep. 19 Tu	randomized median	CLRS, Ch. 9, Sec. 12.1, 12.2, 12.3 (DPV, Ch. 2)
Sep. 21 Th	quicksort	CLRS, Ch. 7	HW 3, due 9/28
Sep. 26 Tu	lower bounds, counting-sort	CLRS, Ch. 8
Sep. 28 Th	greedy algorithms	CLRS, Sec. 16.1, 16.2, 16.3	HW 4, due 10/5
Oct. 3 Tu	dynamic programming I	CLRS, Sec. 15.1, 15.2, 15.3
Oct. 5 Th	dynamic programming II	CLRS, Sec. 15.4, 15.5	HW 5, due 10/12
Oct. 10 Tu	B-trees	CLRS, Ch. 18
Oct. 12 Th	graph algorithms I	CLRS, Ch. 22; (DPV, Ch. 3)	HW 6, due 10/19
Oct. 17 Tu	graph algorithms II (spanning trees)	CLRS, Ch. 23 and Sec. 21.1, 21.2, 21.3; (DPV, Ch. 4)
Oct. 19 Th	graph algorithms III (shortest paths)	CLRS, Ch. 20, 24	HW 7, due 10/26
Oct. 24 Tu	MIDTERM
Oct. 26 Th	graph algorithms IV (matchings)	CLRS, Sec. 26.1, 26.3	HW 8, due 11/2
Oct. 31 Tu	graph algorithms V (flows)	CLRS, Sec. 26.2
Nov. 2 Th	NP-hardness I	CLRS, Sec. 34.1, 34.2, 34.3; (DPV, Ch. 8)	HW 9, due 11/9
Nov. 7 Tu	NP-hardness II	CLRS, Sec. 34.4, 34.5
Nov. 9 Th	Approximation algorithms I	CLRS, Sec. 35.1, 35.2; (DPV, Ch. 9)	HW 10, due 11/16
Nov. 14 Tu	Approximation algorithms II	CLRS, Sec. 35.3, 35.5
Nov. 16 Th	Number Theory, RSA		HW 11, due 11/21
Nov. 21 Tu	linear programming I	CLRS, Ch. 29 and Sec. 35.4	HW 12, due 11/30
Nov. 28 Tu	linear programming II	(no reading due)
Nov. 30 Th	geometric algorithms I	CLRS, Sec. 33.1, 33.2	HW 13, due 12/7
Dec. 5 Tu	geometric algorithms II	CLRS, Sec. 33.3, 33.4
Dec. 7 Th	hashing	CLRS, Sec. 11.1, 11.2, 11.3, 11.4
Dec. 12 Tu	review
Dec. 21 Th	FINAL EXAM (8:30am, CSC 601)

Score statistics

	1st quartile	median	3rd quartile	maximum
HW1	10	14	19	30
HW2	25	27	35	40
HW3	21	25	36	40
HW4	43	46.5	49.75	50
HW5	0	18	24	50
HW6	18	24	32	50
HW7	14	19	20	20
HW8	10.5	16	19.5	30
HW9	6	19	24	30
HW10	8	13	18	30
HW11	10	13	17	20
HW12	22	27	28	30
HW13	14	20	23	30
Q1	14.75	20	20	20
Q2	8	10.5	14	20
Q3	12	14	18	20
Q4	14.5	16	18	20
Q5	13	14	16	20
Q6	7	8.5	13	20
Q7	9	12	17.5	20
Q8	6	6	15	25
Q9	10	28	30	30
Q10	8	11	14	20
Q11	8	8	8	20
Q12	8	10	14	20
Q13	5	8	14	20

Grading

Homework: 25%.
Quizzes: 20%.
Midterm: 25%.
Final: 30%.

Homework Rules

Homework is collected on the due date, before class.
No late homework will be accepted without instructor's permission (a permission must be requested at least 24 hours before the due date).
In the final evaluation everybody's two lowest homework scores will be dropped.
Each problem must be written on a separate letter-size paper.
You may work with one other person on homeworks, but you must each write up your solutions separately (without any written aid). If you work with another person, indicate who you worked with on your solution (thus you should each indicate each other).

Test Rules

All tests are closed book. No text or notes, no scratch paper allowed.
There is one short quiz every week. There will be no make-up quizzes.
In the final evaluation everybody's two lowest quiz scores will be dropped.

This course follows The University Policy on Academic Honesty .