Instructor

      Milena Mihail
      mihail@cc.gatech.edu
      238 College of Computing
      404-385-0617
      Office Hours: Tue 2:00-3:00, or by appointment

Teaching Assistants

      Vivek Kwatra
      kwatra@cc.gatech.edu
      153 College of Computing
      404-894-1155
      Office Hours: By Appointment

      Rehan Ahsan
      rehan@cc.gatech.edu
      Office Hours: By Appointment
      404-206-4024 (This is my home number. Only desperate cases will be heard)

General Description:
This course has two parts.
The first part is an introduction to the Theory of Algorithms and covers the basic paradigms of efficient algorithms.
The second part is an introduction to the Theory of computation and covers basic computational machine models and their computational power.

Textbooks:
Introduction to Algorithms, by Cormen, Leisorson, and Rivest.
Introduction to the Theory of Computation, by Sipser.

Grading:
Weekly or biweekly homeworks: 20%, no collaboration.
Late policy: minus 20% for each day.
Two midterms 25% each.

First midterm is Tuesday, February 8th.
Plan to spend 10-15 hours weekly on this course.
Programming will be neither required nor necessary.

Prerequisites:
A course in constructing proofs, a course in introduction to programming and a course in discrete mathematics. For example, CS1050, CS1302, and MATH3012 (MATH3012 may be taken concurrently). If you do not have this background you should get permission of the instructor.

Newsgroup:
Make use of the newsgroup!
Subscribe to git.cc.class.cs3500b

Homeworks:
Homework 1:  Due-01/19/00 (Solutions)
Homework 2:  Due-01/2/00 (Solutions)
Homework 3:  Due-02/23/00 (Solutions)
Homework 4:  Due-03/22/00 (Solutions) Thanks to Bryan Harden for providing the solutions.
Homework 5:  Due-04/06/00 (Solutions)
Homework 6:  Due-04/18/00

Lectures:

Week 1-2 January 11, 12, 13 January 18, 19, 20	Lecture 1, 2, 3:            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
Week 3 January 25, 26, 27	Lecture 4, 5, 6:            1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Week 4 February 1, 2, 3	Lecture 7:                    1, 2, 3, 4, 5, 6 Lecture 8, 9:                1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Week 5 February 8, 9, 10	Lecture 10:                  1, 2, 3, 4, 5, 6 Lecture 11:                  Review session for midterm. No notes. Lecture 12:                  1, 2, 3, 4
Week 6 February 15, 16, 17	Lecture 13:                  Midterm Exam 1 Lecture 14:                  1, 2, 3, 4 Lecture 15:                  1, 2, 3, 4, 5, 6, 7, 8
Week 7 February 22, 23, 24	Lecture 16:                  (pdf) 1, 2, 3, 4, 5 Lecture 17:                  (pdf) 1, 2 Lecture 18:                  Peter Winkler on Golf with Two Balls.
Week 8 February 28 March 1, 2	Lecture 19:                  (pdf) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 Lecture 20:                  Computational Geometry: Sketch of Convex Hull Lecture 21:                  Cryptography: Sketch of Primality Testing and RSA
Week 9	SPRING  BREAK
Week 10 March 7, 8, 9	Lecture 22:                  (pdf) Lecture 23:                  (pdf) Lecture 24:                  (pdf)
Week 11 March 14, 15, 16	Lecture 25:                  (pdf) Lecture 26: Lecture 27:
Week 12 March 21, 22, 23	Lecture 28: Lecture 29: Lecture 30:
Week 13 March 28, 29, 30	Lecture 31: Lecture 32: Lecture 33:
Week 14 April 4, 5, 6	Lecture 34: Lecture 35: Lecture 36:
Week 15 April 11, 12, 13	Lecture 37: Lecture 38: Lecture 39:
Week 16 April 18, 19, 20	Lecture 40: Lecture 41: Lecture 42:                  Midterm Exam 2
Week 17 April 25, 26, 27	Lecture 43: Lecture 44: Lecture 45:
Week 18 Finals Week	Final Exam