CPSC 629: Analysis of Algorithms
Fall 2003

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

Announcements

Back to beginning

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.)

Course URL: https://people.engr.tamu.edu/j-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 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:

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.

Your grade will be based on five components:

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.

Back to beginning

Calendar

This calendar lists all due dates as they become known for Follow the links to get
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

Back to beginning

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:
  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.

Back to beginning

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

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