CPSC 411: Design and Analysis of Algorithms
Fall 2008

Announcements

• 12/8: Here are Exam 1 solutions and Exam 2 solutions for you to study for the exam, if you like.

• 12/3: HW 8 solution is here.

• 12/2: Final Exam review available here.

• 11/25: Homework 8 is available, due Tue, Dec 2. Also on Tue, Dec 2, we will have the course evaluations (bring a #2 pencil) and the post-test.

• 11/18: HW solutions are here: HW 4, HW 5, HW 7,

• 11/17: Exam 2 review available here.

• 11/17: Slide set 11 on NP-completeness has been updated to include material on approximation algorithms.

• 11/11: HW 7 is now available, due Tue, Nov 18.

• 11/4: HW 6 is now available, due Tue, Nov 11.

• 10/28: Typos on slide 48 of set 10 (randomly permuting an array) have been corrected. Schedule is updated (see calendar section).

• 10/28: HW 5 is now available, due Tue, Nov 4.

• 10/21: Late work policy: 10% of the maximum possible points will be deducted for each 24 hours that the assignment is late. Once solutions have been discussed or handed out, the assignment will not be accepted (grade of 0).

• 10/17: HW 4 is now available, due Thu, Oct 23.

• 10/15: Some comments and corrections to the posted HW 3 solutions are here.

• 10/10: Yue's HW solutions are here: HW 1, HW 2, HW 3.

• 10/9: Exam 1 review available here.

• 9/30: HW 3 is now finalized (some additional exercises were added). Due date for HW 3 is now postponed to Thu, 10/9.

• 9/29: Quiz 5 will be tomorrow (9/30) at the beginning of class and Quiz 6 will be Thursday (10/2) at the *end* of class. Exam 1 will be on Thursday, Oct 16.

• 9/23: Homework 3 is available, due Tue, Oct 7.

• 9/23: Dr. Klappenecker's notes on Theory of Greedy Algorithms is available here.

• 9/18: Several announcements: (1) HW 2 due date postponed to Tue, Sep 23. (2) If you are interested in the annual TAMU programming contest hosted by the Texas A&M Computing Society, please email tdm(at)tamu.edu ASAP.

• 9/8: More information about the programming problem on HW 2 is here (a PDF file). Please contact Yue (yli (at) cs.tamu.edu) if you have questions.

• 9/2: If you cannot attend any research seminar for a particular culture report, you may substitute for it a review of a technical paper. Please see the Culture Report section of this web page for more details. Thanks to Dustin for pointing out the seminars in ECE on Friday: see here for more details. I removed the links to stale seminar pages and left links to seminar series that I know will start up at some point this fall.

• 9/1: The Undergraduate Research Scholars Program is a great opportunity for you to get involved in research. If you've completed at least 60 hours, with at least 24 at TAMU, have at least a 3.0 GPR, and are involved in a suitable project, please consider applying. More information is here.

• 9/1: A good option for a culture report is this computer engineering seminar by Dr. Alex Sprintson on network coding, Tue, Sep 2, 3:55 PM, 102 Zachry. It will be tutorial in nature and is about algorithms, so it's very relevant to our class.

• 8/28: HW 1 is available and due Thu, 9/4. Culture report due dates are available.

• 8/26: Honors contracts are available for this class! If you have completed at least 9 credit hours of regular Honors classrom courses, you are eligible. In an Honors contract, we would jointly determine some activities (e.g., a project) that would augment the class experience, you fill out an application (available from the Honors office at 114 Henderson Hall), you execute the activities, and then Honors credit is applied to your transcript after final grades are posted. More information is available here. Applications are due by the 12th class day, so start thinking about it now.

Back to beginning

Syllabus

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

• be familiar with fundamental algorithms and algorithmic techniques;
• given a particular application, be able to decide which algorithm among a set of possible choices is best;
• be able to prove correctness and analyze the running time and space complexity of a given algorithm;
• be able to design efficient algorithms for new situations using the techniques learned;
• be able to prove a problem is NP-complete using reduction and understand the implications;
• understand the notion of undecidability, know that some problems are undecidable and the implications thereof.

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

Your grade will be based on these components:

• weekly quizzes 10% -- Almost every week, there will be a short (about 10 minutes) quiz on the current material. Your top 10 quiz grades will count toward your semester grade.

• homeworks 35% -- Homework will consist of written problems and programming assignments. More information is here.

• exams 45% -- Two in-class midterms and a cumulative final exam will be given; each worth 15%. More information will be provided later.

• culture reports 5% -- This component is to expose you to some of the research being done at TAMU and other places. Attend five seminars and write a short report about each. More information is here.

• class partipication 5% -- Active participation in class by all students will make it a better experience for all of us. Ask questions, make comments and suggestions, correct errors, find good URLs relating to algorithms for me to post, etc..

Course grades will be assigned according to this scale:

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:

• Definitions of academic misconduct, which includes plagiarism
• List of sanctions that can be applied if academic misconduct is found.

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:

• Distinguished Lectures (You are especially encouraged to attend these.)
• Departmental Graduate Seminars (CPSC 681) (Mondays and/or Wednesdays at 4:10pm.)
• Parasol Seminars (usually held Fridays at 4pm in 302 HRBB)

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

• date and title of talk, name and affiliation of speaker;
• summary of the talk;
• at least one comment about the paper or question that it raised in your mind, indicating that you have thought critically about the material presented.

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:

• Communications of the ACM
• IEEE Computer

• instead of the information about the talk and the speaker, give the complete bibliographic information for the paper (title of article; names of all authors; name of journal with volume, number, date and page numbers), and
• include a hardcopy of the paper itself.

Tips for getting full points on your culture reports:

• TURN IT IN ON TIME.
• Include the cover sheet.
• Ideally you should learn something from the seminar/article. If the seminar turns out to be too technical (or not well presented), just do the best you can, and feel free to point out what confused you or what you thought could have been done better. If you are summarizing an article, be sure to choose an appropriate level article. It should have a reasonable level of technical depth (relating to computing) and be of reasonable length. An editorial full of jokes is too easy; a 30 page paper from a highly technical journal full of proofs is probably too hard. You should be able to learn something from the article.
• Don't be too skimpy on your summary.
• Clearly mark your own comments and critical evaluation. Say something at least mildly insightful. "I learned a lot/it made me think" is not enough. What did you like and why? Is there a flaw in the paper? How does it relate to something else you may be aware of? Etc.
• Include the required information about the seminar/paper in your summary.
• For a paper summary, include a copy of the paper itself
• Use a spell-checker and grammar checker.

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

• Culture Report 1 due Tue, 9/9
• Culture Report 2 due Tue, 9/30
• Culture Report 3 due Tue, 10/21
• Culture Report 4 due Thu, 11/13
• Culture Report 5 due Tue, 12/2

Back to beginning

Calendar

• readings
• homework
• quizzes
• exams
• culture reports

• Set 1: Introduction
• Set 2: Sorting Lower Bound
• Set 3: Divide and Conquer
• Set 4: Greedy Algorithms
• Set 5: Dynamic Programming
• Set 6: Amortized Analysis
• Set 7: Disjoint Sets
• Set 8: Graph Algorithms
• Set 9: More Graph Algorithms
• Set 10: Randomized Algorithms
• Set 11: NP-Completeness
• Set 12: Undecidability

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

Date	Topic	Assignment(s)
August
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
September
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
October
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
November
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	.
December
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

• Algorithms in the Real World, a course at CMU. Check out the links.
• The Algorithmist
• Top Coder, online programming competitions, including emphasis on algorithms
• Lecture slides for algorithms course at Princeton: great graphics and lots of real-world applications. Check out files entitled 18UndirectedGraphs.pdf and 20DirectedGraphs.pdf, for instance.

• Computer Science Department, TAMU
• Student Computing and Information Page: central source of information about student computing at TAMU.

Back to beginning