Spring 2004
[ Lectures, Part 1] [ Lectures, Part 2] [Homework] [Quizzes]
This course has two parts.
The first part is an introduction to the Theory of Algorithms and covers the basic paradigms of the design of efficient algorithms.
The second part is an introduction to the Theory of Computation and covers basic computational machine models and their computational power.
Lectures: Tue-Thu 4:35-5:55, ES&T L1205.
Review Sessions: Wed 5:05-5:55, ES&T L1205.Notes will be handed out at the beginning of each lecture, and wil be also posted on the Web.
Pete Manolios
Assistant Professor
Office phone: 404-894-9219
Office hours: Tue 3:00-4:00, Thu 10:00-11:00 217 CCB, or by appointment.
All email concerning this course should have a subject entitled CS3500.
manolios[AT]cc.gatech.edu
Deeparnab Chakrabarty, Office Hours Fri 3-4 (deepc[AT]cc.gatech.edu)
Ryan Johnston, Office Hours Tue 1:30-2:30 (ryanrino[AT]cc.gatech.edu)
The TA office hours will be held at the CoC 1st floor common area.
Introduction to Algorithms, 2nd Edition, by Thosmas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Introduction to the Theory of Computation, by Michael Sipser
Weekly or biweekly homeworks: 30%.
You may collaborate in solving the problems, but please indicate your collaboration group. You MUST write your answers by yourselves, without any collaboration.
Academic conduct is subject to the Georgia Tech Honor Code.
The TAs may do spot grading, but complete solutions will be always posted on the Web.
Late homework policy: minus 20% for 1 day late, minus 50% for 2 days late, after that no credit.
Four-five quizzes: for total of 40%.
Final: 30%.
In order to make homework submission as convenient as possible for you, we will allow you to submit your homework via email. Email submissions are subject to the same deadline as other submissions. In addition, your submissions must be valid pdf or postscript files. Please send homework submissions to Deeparnab Chakrabarty whose email address is deepc[AT]cc.gatech.edu.. The subject of the message should be "CS3500 submission".
Please staple your answer sheets if you are turning in more than one page. Please do not send scanned files by email. Submit such solutions outside CoC 217. Email submissions should be PS/PDF files generated from Latex.
You are responsible for reading these announcements every few days.
- Apr 14: A reminder that your quiz grade for the course will be the average of your three best quizzes.
- Apr 14: The solutions to hw7 have been posted.
- Apr 14: Please check that the grade you got for Quiz 3 is right. That is, add up all the points you got for the individual questions and see that the sum is the grade we gave you. It seems that a small number of you have found mistakes and we want to make sure that no problems remain. Ryan will show up at the end of class on Tuesday, April 20th, to resolve any issues.
- Apr 13: Please fill out the online course evaluations. They are used by the department to evaluate our teaching and I would really appreciate it if you all take the time to fill them out. You can access the surveys here. In fact, if you fill out the course evaluations and send me an email confirmation, I will give you 25 extra points on HW8.
- Apr 8: Quiz 4 will be on April 15th. It will cover the pumping lemma for regular languages, all the material on context free languages and everything we cover up to (and including) the 13th of April, which I am estimating will consist of most of chapters 3 and 4.
- Apr 7: Here is the plan for the rest of the semester.
- Within 1 week, we will send you a spreadsheet containing your grades. Please check it carefully, as you are responsible for making sure that our records agree with your records.
- Quiz 4 will be on April 15th. It will cover the pumping lemma for regular languages, all the material on context free languages, and the material on Turing Machines we cover up to April 13th.
- Homework 8, the last homework, will be due on April 20th.
- The final is scheduled for Monday, April 26th from 8:00-10:50AM in ES&T L1205.
- Apr 7: Homework 7 is due on the 13th.
- Mar 26: A practice quiz3 is available here. Solutions will be available next week.
- Mar 25: Reminder! Quiz 3 will take place on April 1st.
- Mar 20: On Wednesday April 21, class will be held in ES&T L1175 (just down the hall from our regular room).
- Mar 20: Do you want an extra 20 points on your next homework assignment? If so, consider participating in the following psychology experiment, where you will be asked to watch a series of animated examples of operations on a data structure and to then answer questions.
- Mar 18: Homework 6 is out and due on March 25.
- Mar 8: As we have mentioned on numerous occasions, the two sections Section A and Section B have split. The webpage for Section A is here. This is the Web page for section B. Also, the newsgroup for Section B is git.cc.class.cs3500b.
Finally, homeworks should be submitted before the start of class, either in the box near Pete Manolios' office (CoC 217) or in class.
- Mar 4: You should have gotten an email from Ryan containing a spreadsheet with a list of your grades. You are responsible for checking the list for accuracy. Contact Ryan if there are any problems.
- Mar 2: Homework 5 is out and due right after spring break.
- Feb 24: Here's the key to Quiz 2, Section A . Please go through it carefully. We will refer to parts of it in Thursday's Lecture.
- Feb 23: Manolios moved offices. He is now in CCB 217.
- Feb 5: Homework 4 is out and due Tue Feb 17.
A course in constructing proofs, a second course on programming, and a course in discrete mathematics.
For example, CS1050, CS1322, and MATH3012. If you do not have this background you should get permission of the instructor.
Class Web-site http://www.cc.gatech.edu/classes/AY2004/cs3500b_spring/, class newsgroup git.cc.class.cs3500b
This site is maintained by Pete Manolios, please report problems to manolios[AT]cc.gatech.edu.