CPSC 629:
Analysis of Algorithms
Fall 2003
[Announcements]
[Syllabus]
[Calendar]
[Project]
[Culture Activities]
 12/16: Correction to HW 5 solution, problem 8 (Prob. 341):
In the construction of G(vbar), 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 0th 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 341 on HW 5: The reference to Section
263 might be misleading. A better hint would be to refer
to Problem 263. Don't think about maximum matchings.
 12/1: Pages 194213 of my lecture notes (the last of them!)
are available in the WERC copy center.
 12/1: Pages 171193 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 149170 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 126148 of my lecture notes are now available
in the WERC copy center.
 10/31: Culture reports 34 info is now
available, due Thu, Nov 13.
 10/31: Homework 4 is now available,
due Tue, Nov 11.
 10/28: Pages 102125 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 173.
 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 6074 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 4959 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 1819: Dr. Klappenecker will substitute on Sep 18;
office hours on Sep 19 cancelled.
 Sep 26 (tentative): office hours rescheduled, TBA.
 Sep 29Oct 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 1517.
 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.
Back to beginning
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: 8455076
Home Phone: 7740680 (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: 8626611
Lecture:
Tuesdays and Thursdays, 2:20  3:35 PM, ZACH 105B.
Textbooks:
 Introduction to Algorithms, Second Edition,
Cormen, Leiserson, Rivest and Stein, MIT Press / McGrawHill, 2001.
[CLRS]
 A wonderful reference book on NPcompleteness 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.)
Course URL:
http://faculty.cs.tamu.edu/welch/teaching/629.f03
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 14, 612, and 2225 and Appendices AC
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 NPcompleteness, 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 NPcomplete 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
 Btrees
 Ch 18

9/29
 binomial heaps
 Ch 19

10/6
 Fibonacci heaps
 Ch 20

10/13
 unionfind
 Ch 21

10/20
 strongly connected components
 Ch 22, Sec 5

10/27
 shortest paths
 Chs 2425

11/3
 max flow
 Ch 26

11/10
 NPcompleteness
 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.
Your grade will be based on five components:
 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 makeup 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.
Back to beginning
This calendar lists all due dates as they become known for
 readings
 exams
 project and homeworks
 culture activities
Follow the links to get
 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; BTrees
Read Ch 18
 9/24
 9/25
BTrees
project proposal due
 9/26

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

10/27
 10/28
Shortest Path Algorithms
Read Chs 2325
Culture #2 report due
 10/29
 10/30
More Shortest Path Algorithms
 10/31

11/3
 11/4
Max Flow
Read Ch 26, Sec 13
 11/5
 11/6
More Max Flow
 11/7

11/10
 11/11
NPCompleteness
Read Ch 34 (skip circuitsat material)
HW 4 due
 11/12
 11/13
More NPCompleteness (3SAT, VC)
Culture #34
report due
 11/14
Culture #5 seminar:
Kumar, 4:10 PM, Bright 124

11/17
 11/18
Read Ch 35 (skip Sec 34)
Approximation Algorithms
 11/19
 11/20
More Approximation Algorithms
 11/21

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

11/24
 11/25
Read Ch 32, Sec 12
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

Back to beginning
The first part of your project is to find a realworld 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:
 Use realworld experience of yourself or people you know.
 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, SpringerVerlag, 1998.
 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
 brief description of the problem chosen
 explanation of its realworld application
 brief description of the two competing algorithms
 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
 fleshed out version of project proposal
 results of experiments (you should include some graphs here and
explain how your empirical results relate to theoretical complexity
analyses)
 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.
Back to beginning
Schedule, updated 11/11:
 Seminar #1: Patterson, Fri, Oct 10, 4:10 PM, 124 Bright.
Report #1 due: Thu, Oct 16.
 Seminar #2: Stroustrup, Wed, Oct 15, 4:10 PM, 124 Bright.
Report #2 due: Tue, Oct 28. (postponed from original due date)
 Report #34 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/rivestshamiradleman.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.
 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.
Back to beginning