# CPSC 629: Analysis of Algorithms Fall 2003

[Announcements] [Syllabus] [Calendar] [Project] [Culture Activities]

## Announcements

• 12/16: Correction to HW 5 solution, problem 8 (Prob. 34-1): In the construction of G(v-bar), in addition to removing \$v\$, also remove all of its neighbors before making the recursive call.

• 12/16: Project reports and HW 6 are graded. You can pick them up from me today (before 12 or between 1:30 and 3:00) or tomorrow at the final.

• 12/15: Homework 5 solutions are available here in pdf, including "Comments on common errors".

• 12/14: Homework 6 solutions are available here in pdf.

• 12/9: Review sheet for the final is now available - click on the link. You may bring two 8.5x11 inch sheets of paper to the exam with your own notes on them.

• 12/9: Don't forget final exam Wed, 12/17, 1:00 - 3:00 PM! My office hours for the rest of the semester:
Wed, Dec 10, 3:00 - 4:30 PM
Fri, Dec 12, 2:00 - 3:00 PM
Mon, Dec 15, 2:00 - 3:00 PM
Tue, Dec 16, 2:00 - 3:00 PM
Other times by appointment.

• 12/2: Corrections to today's lecture (and lecture notes): The 0-th Fibonacci number, F_0, is 0, not 1. The approximate bound for F_k is (1/sqrt(5))(1+sqrt(5))/2.

• 12/2: Course evaluations will be this Thursday, Dec 4. Bring a #2 pencil to class.

• 12/1: Homework 6 is now available, due Tue, Dec 9.

• 12/1: About Problem 34-1 on HW 5: The reference to Section 26-3 might be misleading. A better hint would be to refer to Problem 26-3. Don't think about maximum matchings.

• 12/1: Pages 194-213 of my lecture notes (the last of them!) are available in the WERC copy center.

• 12/1: Pages 171-193 of my lecture notes are now available in the WERC copy center.

• 11/18: Homework 4 solutions are available here in pdf. Please pay attention to the "comments on common errors".

• 11/17: Pages 149-170 of my lecture notes are now available in the WERC copy center.

• 11/17: I got a memo asking me to advertise the TAMU Diversity Symposium, 7:00 PM, Thu, Nov 20, Rudder Theater.

• 11/13: Homework 5 is now available, due Tue, Dec 2. Don't wait until Thanksgiving vacation to start it!!

• 11/11: Culture report 5 info is now available, due Thu, Dec 4. The seminar is by Prof. P. R. Kumar, Department of Electrical and Computer Engineering, University of Illinois, and the title is "From Wireless and Sensor Networks to Convergence: Protocols and Architecture". The talk is a combined CPSC 681 and Department of Electrical Engineering Distinguished Speaker Seminar. The seminar is this Friday, Nov 14, 4:10 PM in Bright 124.

• 11/6: Regarding grading of the midterm exam: in problem 2(c), column by column from left to right will also work. If I counted off on your exam for that, return your exam to me for correction.

• 11/4: Pages 126-148 of my lecture notes are now available in the WERC copy center.

• 10/31: Culture reports 3-4 info is now available, due Thu, Nov 13.

• 10/31: Homework 4 is now available, due Tue, Nov 11.

• 10/28: Pages 102-125 of my lecture notes are now available in the WERC copy center.

• 10/27: Corrected and updated Homework 3 solutions are available here in postscript and pdf. Please pay attention to the new sections on "comments on common errors".

• 10/23: Corrected Homework 2 solutions are available here in pdf. The correction is to part (e) of Problem 17-3.

• 10/21: Homework 3 solutions are available here in postscript and pdf.

• 10/16: You may bring one 8.5x11 inch sheet of paper to the exam with your own notes on it.

• 10/16: My office hours next week (before the exam): Tuesday, 10/21, 8:30 - 10:00 AM (instead of Friday), and Wednesday, 10/22, 3:00 - 4:30 PM (as usual).

• 10/16: Review sheet for the midterm is now available - click on the link.

• 10/14: Culture report #2 due date (Stroustrup) is postponed to Tue, Oct 28.

• 10/14: My office hours this week: Wed, 10/15, 3:00 - 4:00 (instead of 4:30, because of Stroustrup's seminar). Fri, 10/17, 3:30 - 5:00 (instead of 1:30 - 3:00).

• 10/14: The rest of Homework 3 is now available, due Oct 21.

• 10/7: I'm sorry for the late notice, but I have a meeting most of the day tomorrow so my office hours are moved to 4:00 - 5:00. Email me if you need to make an appointment for another time.

• 10/7: Pages 60-74 of my lecture notes are now available in the WERC copy center.

• 10/7: The midterm exam will be Thursday, Oct 23. A review sheet will be available later.

• 10/7: Homework 3 (first installment) is now available, due Oct 21.

• 9/29: Project proposals will be passed back in class on 9/30. Please take note of my comments. You must include your proposal (the copy with my comments) with your final report, so don't lose it. A few people have to resubmit (by Oct 9). You can talk to Ge in the meantime about it until I get back. Also, HW 3 will not be assigned until next week - you can use the time to work on your projects.

• 9/25: Pages 49-59 of my lecture notes are now available in the WERC copy center.

• 9/23: workshop on getting money for graduate school: how to prepare competitive applications for NSF and other national fellowships. Mon, Oct 6, 6:00 PM, Zachry 127B (refreshments at 5:45 PM). For seniors and graduate students.

• 9/22: Here is an update on the culture assignments. Most of them will be CPSC 681 speakers. (If you are taking CPSC 681, you can rework your 681 report for your 629 report.) Here are two already scheduled. There should be another distinguished lecture this fall, but it is not yet scheduled. I will flesh out the other three as more information about seminar speakers becomes available to me.

For culture assignment #1, please attend the Distinguished Lecture by Prof. David Patterson, University of California, Berkeley, Fri, Oct 10, 4:10 PM, 124 Bright.

For culture assignment #2, please attend the CPSC 681 seminar by Prof. Bjarne Stroustrup of our department, Wed, Oct 15, 4:10 PM, 124 Bright.

• 9/18: Homework 2 is now available, due Oct 2.

• 9/12: Dr. Welch's upcoming travel:
• Sep 18-19: Dr. Klappenecker will substitute on Sep 18; office hours on Sep 19 cancelled.
• Sep 26 (tentative): office hours rescheduled, TBA.
• Sep 29-Oct 6: Dr. Chen will substitute on Sep 30 and Oct 2; office hours on Oct 1 and Oct 3 cancelled.

• 9/9: Student Engineers' Council engineering career fair is Sep 15-17.

• 9/7: Homework 1 is now available, due Sep 18.

• 9/3: Quiz over prerequisite material will be Thu, Sep 4. Review sheet is available here.

## Syllabus

Instructor: Prof. Jennifer Welch
Office: 415 H.R. Bright Bldg
Office Hours: Wednesdays 3:00 - 4:30 PM and Fridays 1:30 - 3:00 PM; other times by appointment
Email: welch@cs.tamu.edu
Office Phone: 845-5076
Home Phone: 774-0680 (please don't call after 9:00 PM)

Teaching Assistant: Ge (Frank) Xia
Office: 419B H.R. Bright Bldg
Office Hours: Tuesdays and Thursdays 12:40 - 2:10 PM; other times by appointment
Email: gexia@cs.tamu.edu
Office Phone: 862-6611

Lecture: Tuesdays and Thursdays, 2:20 - 3:35 PM, ZACH 105B.

Textbooks:

1. Introduction to Algorithms, Second Edition, Cormen, Leiserson, Rivest and Stein, MIT Press / McGraw-Hill, 2001. [CLRS]
2. A wonderful reference book on NP-completeness is: Computers and Intractability, Garey and Johnson, W.H. Freeman, 1979. The book is out of print, but if you can find a copy, get it and keep it for future reference! (It is not required for this course.)

Prerequisite: CPSC 311, the undergraduate analysis of algorithms course, (or equivalent) is a prerequisite for this course. You are expected to be familiar with the material in Chapters 1-4, 6-12, and 22-25 and Appendices A-C of [CLRS], excluding Sections 4.4, 11.5, 12.4, 22.5, 24.4, 24.5, and 25.3. These topics are basic mathematical analysis techniques, sorting, simple search structures, and basic graph algorithms.

Course Overview: This course is designed to teach you, at the graduate level, algorithm design and analysis paradigms, advanced data structures and their use in efficient algorithms, graph algorithms, the theory of NP-completeness, and some advanced topics. At the end of the semester you should:
• be familiar with the algorithms and algorithmic techniques covered,
• be able to argue correctness and analyze the running time of a given algorithm,
• be able to design new algorithms for new situations, using as building blocks the algorithms and techniques learned,
• be able to prove a problem is NP-complete using reduction.

Tentative Schedule: The course will cover the following topics.

 week of topic [CLRS] 9/1 dynamic programming Ch 15 9/8 greedy algorithms Ch 16 9/15 amortized analysis Ch 17 9/22 B-trees Ch 18 9/29 binomial heaps Ch 19 10/6 Fibonacci heaps Ch 20 10/13 union-find Ch 21 10/20 strongly connected components Ch 22, Sec 5 10/27 shortest paths Chs 24-25 11/3 max flow Ch 26 11/10 NP-completeness Ch 34 11/17 approximation algorithms Ch 35 11/24 string matching Ch 32 12/1, 12/8 number theoretic algorithms (if time) Ch 31

Assignments and Grading: All assignments will be announced in class and posted on the web page calendar. If you miss class for any reason, it is your responsibility to find out what assignments you missed.

• midterm exam 25% - in class
• final exam 25% - in class, Wednesday, Dec 17, 1:00 - 3:00 PM
• homework 20% - homework will be due every 1 or 2 weeks. More information available here.
• project 20% - choose two algorithms for the same problem, describe the algorithms and their theoretical complexity analyses, implement the two algorithms, and compare their actual performance to each other and to the theoretical analyses. More information available here.
• culture 10% - several short reports on seminar speakers. More information available here.

No late assignments will be accepted. There will be no make-up exams. Discuss unusual circumstances in advance with the instructor. All excused absences must also be cleared with the instructor.

Course grades will be assigned according to this scale:

 percent of total points 90 - 100 80 - 89 70 - 79 60 - 69 < 60 letter grade A B C D F

Collaboration: Discussion of concepts with others is encouraged, but all assignments must be done on your own, unless otherwise instructed. If you use any source other than the text, reference it/him/her, whether it be a person, a book, a solution set, a web page or whatever. You MUST write up the solutions in your own words. Copying is strictly forbidden. Every assignment must be turned in with this cover sheet, which lists all sources you used.

University Regulations define scholastic dishonesty to include acquiring answers from any unauthorized source, working with another person when not specifically permitted, observing the work of other students during any exam, providing answers when not specifically authorized to do so, informing any person of the contents of an exam prior to the exam, and failing to credit sources used. Disciplinary actions range from grade penalty to expulsion.

## Calendar

This calendar lists all due dates as they become known for
• exams
• project and homeworks
• culture activities
• details on the assignments
• exam reviews
 Monday Tuesday Wednesday Thursday Friday 9/1 9/2 Introduction; Dynamic Programming Read Ch 15 9/3 9/4 More Dynamic Programming Prerequisite Quiz 9/5 9/8 9/9 Greedy Algorithms Read Ch 16 9/10 9/11 Greedy Algorithms 9/12 9/15 9/16 Amortized Analysis Read Ch 17 9/17 9/18 Amortized Analysis HW 1 due 9/19 9/22 9/23 Amorized Analysis; B-Trees Read Ch 18 9/24 9/25 B-Trees project proposal due 9/26

 Monday Tuesday Wednesday Thursday Friday 9/29 9/30 Binomial Heaps (Dr. Chen substitutes) Read Ch 19 10/1 10/2 Fibonacci Heaps (Dr. Keyser substitutes) Read Ch 20 HW 2 due 10/3 10/6 10/7 More on Heaps 10/8 10/9 More on Fibonacci Heaps 10/10 Culture #1 seminar: Patterson 10/13 10/14 Disjoint Sets Read Ch 21 10/15 Culture #2 seminar: Stroustrup 10/16 Disjoint Sets Culture #1 report due 10/17 10/20 10/21 Strongly Connected Components Read Ch 22 HW 3 due 10/22 10/23 MIDTERM EXAM 10/24

 Monday Tuesday Wednesday Thursday Friday 10/27 10/28 Shortest Path Algorithms Read Chs 23-25 Culture #2 report due 10/29 10/30 More Shortest Path Algorithms 10/31 11/3 11/4 Max Flow Read Ch 26, Sec 1-3 11/5 11/6 More Max Flow 11/7 11/10 11/11 NP-Completeness Read Ch 34 (skip circuit-sat material) HW 4 due 11/12 11/13 More NP-Completeness (3SAT, VC) Culture #3-4 report due 11/14 Culture #5 seminar: Kumar, 4:10 PM, Bright 124 11/17 11/18 Read Ch 35 (skip Sec 3-4) Approximation Algorithms 11/19 11/20 More Approximation Algorithms 11/21

 Monday Tuesday Wednesday Thursday Friday 11/24 11/25 Read Ch 32, Sec 1-2 String Matching project report due 11/26 11/27 HOLIDAY 11/28 HOLIDAY 12/1 12/2 Euclid's algorithm and public key cryptosystems Read Ch 31 HW 5 due 12/3 12/4 RSA and modular arithmetic Culture #5 report due 12/5 12/8 Attend Fri classes 12/9 Attend Thu classes; last day of classes Finding primes and factoring HW 6 due 12/10 READING DAY 12/11 READING DAY 12/12 12/15 12/16 12/17 FINAL EXAM 1:00 - 3:00 PM 12/18 12/19

## Project

The first part of your project is to find a real-world application of an algorithm that solves one of the problems studied in the course. The algorithm might be one of the ones studied in the course, or it might be a different one.

Ways to find an appropriate topic:

1. Use real-world experience of yourself or people you know.
2. Look in some books. For example:
• Our textbook mentions Internet routing, Internet search engines, electronic commerce, resource allocation, studying the human genome (see Ch 1).
• The Algorithm Design Manual, by Steven S. Skiena, Springer-Verlag, 1998.
3. Search the web. For instance: (drawn from the Skiena book)
The second part of your project is to compare the performance of two competing algorithms for the problem you chose in the first part. You are to implement both algorithms and measure their running times (or whatever is the relevant cost). The bulk of the work in this part of the project will NOT be the coding, but will be planning the experiments that you will do for the comparison.

The project proposal will consist of

1. brief description of the problem chosen
2. explanation of its real-world application
3. brief description of the two competing algorithms
4. statement as to what cost measure will be compared
The proposal must be typed; it will be graded for form and English as well as content.

You should confer with me about your choices before turning in the project proposal to make sure that what you pick is appropriate. (I will not approve topics that are too trivial or that are too far removed from the study of algorithms.)

The project final report will consist of

1. fleshed out version of project proposal
2. results of experiments (you should include some graphs here and explain how your empirical results relate to theoretical complexity analyses)
3. the code -- it WILL be graded for style, including design and documentation.
The final report must be typed; it will be graded for form and English as well as content.

## Culture Activities

Schedule, updated 11/11:
1. Seminar #1: Patterson, Fri, Oct 10, 4:10 PM, 124 Bright.
Report #1 due: Thu, Oct 16.
2. Seminar #2: Stroustrup, Wed, Oct 15, 4:10 PM, 124 Bright.
Report #2 due: Tue, Oct 28. (postponed from original due date)
3. Report #3-4 due: Thu, Nov 13. There is no associated seminar. Instead, view the videos, slides, etc. of the 2002 Turing Award acceptance speech by Rivest, Shamir and Adleman, available at http://www.acm.org/awards/turing_citations/rivest-shamir-adleman.html. Write up a report based on that. Be sure to include an explanation of what the Turing Award is. This will count for two reports, since there are 3 people involved.
4. Seminar #5: Kumar, Fri, Nov. 24, 4:10 PM, 124 Bright.
Report #5 due: Thu, Dec. 4.
There is a lot more to Computer Science than you will be exposed to through your normal coursework. The purpose of the CS culture activities is to give you some exposure to other research areas besides algorithms.

We are fortunate to have a distinguished collection of computer scientists coming to visit this semester. For each visitor, you are STRONGLY ENCOURAGED to attend the seminar. If you have a legitimate scheduling conflict for a seminar, then you can substitute attendance by reading a technical paper by the speaker.

For each seminar, you are to submit a short (1 to 2 page) typed report. The report must include

• brief biography of the lecturer
• summary of the lecture (or paper)
• your assessment of the level of contribution of the work described
• three questions raised in your mind by the lecture (or paper)
• citations of five related publications (do a literature search)
• bibliography of your sources for the biography
If you read a paper instead of attending the seminar, be sure to attach a copy of the paper to your report and indicate the full bibliographic citation of the paper.

Reports are due one week after the talk. Check the calendar to see when the talks are scheduled and when the reports are due. There will be no more than five reports required.

DO NOT PLAGIARIZE! You must write up your summary in your own words. See collaboration policy in syllabus.