CSCE 311: Analysis of Algorithms
Fall 2009

Announcements

• 11/18: HW 7 is available, due Wed, Nov 25.

• 11/9: Review for Exam 2 (this Friday) is available. You may bring a review sheet to the exam.

• 11/6: Until I get my laptop working again, please refer to this link for slides on NP-completeness.

• 11/2: HW 6 is available, due Mon, Nov 9.

• 10/30: HW 5 due date is postponed to Mon, Nov 2. Culture 3 due date is postponed to Wed, Nov 4.

• 10/23: HW 5 is available, due Fri, Oct 30.

• 10/16: Deadline for HW 4 is postponed to Fri, Oct 23.

• 10/12: Correction for HW 4: You need to add "#include "Comparator.h" to the Sort.h file.

• 10/7: Homework 4, a programming assignment, is due Mon, Oct 19.

• 9/28: Review for Exam 1 (this Friday) is available. You may bring a review sheet to the exam.

• 9/28: Don't forget about Quiz 4 today in class. It will be over the material that Dr. Leyk covered last week (binary search trees, AVL trees, red-black trees, B-trees, and hashing with chaining).

  I just posted a short HW 3, due on Wednesday. It consists of some basic questions about selection and about red-black trees. They will be helpful as a review for Exam I, which will be held this Friday.

  Exam 1 will cover through search trees, but will not cover hashing.

• 9/18 again: Due to popular request, HW 2 due date is postponed to Wed, Sep 23, and culture 2 due date is postponed to Fri, Sep 25.

• 9/18: Dr. Teresa Leyk will substitute during the week of Sep 21. Also, Quiz 4 is postponed until Mon, Sep 28.

• 9/14: Jung-Hwan's office hours are Wednesdays 3-4 and Fridays 3-5, in Reed-McDonald 111J. His email is daeqhh (at) hanmail.net.

• 9/11: HW 2 is available, due Mon, Sep 21. Culture report 1 due date is postponed to Wed, Sep 23.

• 9/2: HW 1 is available, due Wed, Sep 9.

Back to beginning

Syllabus

Teaching Assistant: Jung-Hwan Kim
Office: RDMC (Reed-McDonald, corner of Ross and Ireland Sts.) 111J
Office Hours: Wednesday 3:00-4:00 PM; Friday 3:00-5:00 PM
Email: daeqhh (at) hanmail.net

Prerequisites: CSCE 211 (Data Structures) and MATH 302 (Discrete Math). In particular, you should be familiar with

• solving recurrence relations
• mathematical induction
• data structures including linked lists, arrays, stacks, queues, and trees
• knowledge of a high level programming language such as Java, C, or C++

Textbook: Introduction to Algorithms, Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press / McGraw-Hill, 2001.

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

Your grade will be based on four components:

• exams 45% - There will be two exams during the semester and one final exam, worth 15% each.

• homework 40% - Pencil and paper exercises and some programming assignments (e.g., to compare the performance of two competing algorithms). More details are available here.

• quizzes 10% - There will be 12 short weekly quizzes, consisting of a few simple questions (for example, short answer, true-false, or multiple choice) concerning the reading and/or material recently covered. The purpose of the quiz is to encourage you to do the reading in advance and to stay caught up in the class. Your lowest two quiz grades will be dropped.

• culture reports 5% - This component is to round out your classwork. Find, read, and write short reports on some aspect of computer science and engineering that relates to algorithms. More details are available here.

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). Make-up assignments will only be available for university-excused absences. Please discuss unusual circumstances in advance, if possible, with the instructor.

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, reference it/him/her, whether it be a person, a paper, a book, a solution set, a web page or whatever. You MUST write up the assignments 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 as they relate to algorithms. Keeping up with trends and learning to evaluate critically what you hear and read are valuable professional skills.

Each report is to be one to two pages long, typed, and is to cover some aspect of computer science and engineering that is related to algorithms. Your source of information can be either an article or a seminar. Be sure to clearly explain the connection to algorithms.

Acceptable articles include those published in ACM or IEEE Transactions (for example, ACM Transactions on Algorithms), which are available online from behind the TAMU firewall. Even if you can't follow all the technical details, you should be able to get an idea of what problem is being solved and what is new about the solution.

Acceptable seminars include those in the following series:

• Distinguished Lectures
• Departmental Graduate Seminars (CPSC 681)
• Parasol Seminars

A third option is to research a company whose success is based on algorithms (e.g., Akamai).

Here is what to include in your report:

1. Cover sheet
2. For a paper: complete bibliographic reference (author(s), title, name of journal, volume, number, pages, date) For a seminar: title, name of speaker, date
3. Summary of the paper/talk
4. relation to our class (algorithms
5. your critique: your assessment of the paper/talk, any questions it raised your mind, etc.

Calendar

• readings
• homework
• quizzes
• exams
• culture reports

• details on the assignments
• exam reviews
• powerpoint slides (when available)

Date	Topic	Reading and Assignments Due
Mon, 8/31	Introduction	Read Intro, Chs 1-4
September
Wed, 9/2	Asymptotic Analysis	.
Fri, 9/4	Solving Recurrences	Quiz 1
Mon, 9/7	Heaps and Heapsort	Read pp. 123-126, Chs 6-7
Wed, 9/9	Quicksort	HW 1 due
Fri, 9/11	HW 1 Solutions; More Quicksort	Quiz 2
Mon, 9/14	Randomized Quicksort; Sorting Lower Bound	Read Ch 8
Wed, 9/16	Linear Time Sorting Algorithms	.
Fri, 9/18	Order Statistics	Quiz 3 Read Ch 9
Mon, 9/21	Dr. Leyk: Binary Search Trees	Read pp. 196-199, Ch 12
Wed, 9/23	Dr. Leyk: AVL Trees, Red-Black Trees, B-Trees	HW 2 due Read Ch 13
Fri, 9/25	Dr. Leyk: Hashing	Culture Report 1 Read Ch 11
Mon, 9/28	Hashing	Quiz 4
Wed, 9/30	Review for Exam I	HW 3 due
October
Fri, 10/2	.	EXAM I
Mon, 10/5	Hashing; Dynamic Programming	Read Ch 15
Wed, 10/7	Dynamic Programming	.
Fri, 10/9	Dynamic Programming	Quiz 5
Mon, 10/12	Disjoint Sets	Read Ch 21 Culture Report 2
Wed, 10/14	Disjoint Sets; Intro to Graph Algorithms	.
Fri, 10/16	Breadth-First Search	Quiz 6 Read Chs 22-23
Mon, 10/19	Depth-First Search	.
Wed, 10/21	Minimum Spanning Trees	.
Fri, 10/23	Minimum Spanning Trees	Quiz 7 HW 4 due (programming assignment)
Mon, 10/26	Shortest Paths	Read Ch 24
Wed, 10/28	Shortest Paths	.
Fri, 10/30	Shortest Paths	Quiz 8
November
Mon, 11/2	Shortest Paths	HW 5 due
Wed, 11/4	NP-Completeness	Culture Report 3 Read Ch 34
Fri, 11/6	NP-Completeness	Quiz 9
Mon, 11/9	Review for Exam II	HW 6 due
Wed, 11/11	Review for Exam II	.
Fri, 11/13	.	EXAM II
Mon, 11/16	Exam II Solutions	.
Wed, 11/18	NP-Completeness	.
Fri, 11/20	.	Quiz 10
Mon, 11/23	.	Culture Report 4
Wed, 11/25	.	HW 7 due
Fri, 11/27	THANKSGIVING HOLIDAY	.
Mon, 11/30	.	Quiz 11
December
Wed, 12/2	.	.
Fri, 12/4	.	Culture Report 5
Mon, 12/7 (attend Friday classes)	.	Quiz 12
Thu, 12/16	.	FINAL EXAM 10:30 AM - 12:30 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.

• Department of Computer Science and Engineering, TAMU
• TAMU Computing Services

Back to beginning