CPSC 411: Design and Analysis of Algorithms
Fall 2008

[Announcements] [Syllabus] [Homework] [Culture] [Calendar] [Useful Links]


Back to beginning


Instructor: Prof. Jennifer Welch
Office: HRBB 425G
Office Hours: Tuesdays and Thursdays 10:30 AM - 12:00 noon; other times by appointment
Email: welch (at) cs.tamu.edu
Office Phone: 845-5076

Teaching Assistant: Yue Li
Office: HRBB 410D
Office Hours: Wednesdays and Fridays 2:30 - 4:00 PM; other times by appointment
Email: yli (at) cs.tamu.edu
Office Phone: 845-9980

Lecture: Tuesdays and Thursdays 2:20 - 3:35 PM, HRBB 126

Textbook: Introduction to Algorithms, Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, 2002.

Prerequisite: CPSC 221, CPSC 315, and MATH 302 (or equivalent).

Course Goals: At the end of the semester, you should: Course Content and Tentative Schedule: The course will cover the following topics. The relevant chapters of the textbook are indicated.

week of topic chapter
8/26 introduction; sorting lower bound Chs 1 and 3; Ch 8
9/2 divide and conquer algorithms Chs 2 and 4; Ch 7
9/9 greedy algorithms Ch 16
9/16, 9/23 dynamic programming Ch 15
9/30 amortized analysis Chs 17 and 21
10/7, 10/14 graph algorithms Chs 23--25
10/21, 10/28 randomized algorithms Chs 5 and 7
11/4, 11/11 NP-completeness Chs 34 and 35
11/18, 11/25, 12/2 undecidability other sources

Assignments and Grading: All assignments will be announced in class and posted on the course web page calendar. If you cannot turn in an assignment on time, discuss the situation in advance with the instructor.

Your grade will be based on these components:

Course grades will be assigned according to this scale:

% total points 90-100 80-89 70-79 60-69 < 60
letter grade A B or better C or better D or better F or better

Academic Integrity: The Aggie Honor Code states "An Aggie does not lie, cheat or steal or tolerate those who do". More information on academic integrity, plagiarism, etc. is available at the Aggie Honor System Office web site http://www.tamu.edu/aggiehonor, including:

Please review this material.

For the assignments in this class, 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.

Americans with Disabilities Act (ADA) Policy Statement: The Americans with Disabilities Act (ADA) is a federal antidiscrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact the Department of Student Life, Services for Students with Disabilities in Cain Hall, Rm. B118, or call 845-1637.

Back to beginning

Culture Reports

There is a lot more to Computer Science than you will be exposed to through your normal coursework. The purpose of the culture activities is to give you an opportunity to learn about current research trends in computing. Keeping up with trends and learning to evaluate critically what you hear and read are valuable professional skills.

You are to attend five computer science seminars and write a report on each one. Acceptable seminars are listed below. More details and seminars will be added as they become available. If you are interested in receiving credit for a seminar that is not listed, check with the instructor in advance. Acceptable seminars include:

Each report is to be one to two pages long, typed, and must include

Don't forget the cover sheet. DO NOT PLAGIARIZE! You must write up your summary in your own words. See academic integrity policy in the syllabus.

If, due to schedule conflicts, you cannot attend any research seminar for a particular culture report deadline, you may instead find, read and write a short report on a technical paper in a computer science journal. Articles in the following two journals are usually at about the right level:

Both are available through the TAMU library, in both hardcopy and on the web. Each article must have been published after May 2008 and must be at least 5 pages long. The same requirements as for the seminar reports hold regarding content, length, format, plagiarism, and cover sheet; differences are:

Tips for getting full points on your culture reports:

The culture report due dates are posted in the calendar section and summarized here:

Back to beginning


This calendar lists all due dates as they become known for Powerpoint lecture slides (will be updated as they become available):

Follow the links in the calendar to get details on the assignments. Reading assignments refer to the textbook.

Date Topic Assignment(s)
Tue, 8/26 Introduction Read Chs 1-3
Thu, 8/28 Sorting Lower Bound Review Ch 6, Ch 7.1-7.2; read Ch 8
Quiz 1
ABET pretest
Tue, 9/2 Divide & Conquer; Solving Recurrences Read Ch 4, Ch 28.2
Thu, 9/4 HW 1 Solutions; Strassen's Algorithm Read Ch 16.1-16.3, Ch 23
Quiz 2
Homework 1 due
Tue, 9/9 Dr. Klappenecker: Greedy Algorithms Culture Report 1 due
Thu, 9/11 Dr. Klappenecker: More on Greedy Algorithms Quiz 3
Tue, 9/16 Dr. Stroustrup: C++0x (eligible for culture report) Read Ch 15
Thu, 9/18 Dynamic Programming Quiz 4
Tue, 9/23 More Dynamic Programming Homework 2 due
Thu, 9/25 HW 2 Solutions; DP for APSP; Amortized Analysis Read Ch 25.2, Ch 17
Tue, 9/30 Disjoint Sets Quiz 5
Culture Report 2 due
Read Ch 21
Thu, 10/2 More on Disjoint Sets Quiz 6
Tue, 10/7 Breadth-First Search and Depth-First Search Read Ch 22
Thu, 10/9 Strongly Connected Components Homework 3 due
Quiz 7
Tue, 10/14 HW 3 Solutions .
Thu, 10/16 . EXAM 1
Tue, 10/21 More Graph Algorithms Read Chs 23 and 24
Culture Report 3 due
Thu, 10/23 Yet More Graph Algorithms; Randomized Algorithms Read Ch 5 and Appendix C
Homework 4 due
Quiz 8
Tue, 10/28 Randomized Algorithms Read Ch 7
Thu, 10/30 Randomized Algorithms Quiz 9
Tue, 11/4 NP-Completeness Homework 5 due
Read Ch 34
Thu, 11/6 More NP-Completeness Quiz 10
Tue, 11/11 Yet More NP-Completeness Homework 6 due (program)
Read Ch 35
Thu, 11/13 Approximation Algorithms Quiz 11
Culture Report 4 due
Tue, 11/18 HW Solutions; Undecidability Homework 7 due
Thu, 11/20 . EXAM 2
Tue, 11/25 More Undecidability .
Thu, 11/27 HOLIDAY .
Tue, 12/2 HW 8 Solutions; ABET Post-test; Student Evaluations Quiz 12
Homework 8 due
Culture Report 5 due
Wed, 12/10 FINAL EXAM 1:00 - 3:00 PM

Back to beginning

Useful Links

Interesting Algorithms Pages Computing-Related at TAMU

Back to beginning