CPSC 311: Analysis of Algorithms
Spring 2004

Announcements

• 5/5: Here are the solutions to HW 8.

• 5/3: Hint for Prob 35-1(a): You may want to use the set-partition problem (cf. Ex. 34.5-5 on p. 1017) instead of subset-sum. You do not need to prove that set-partition is NP-complete.

• 4/30: Final exam review is now available.

• 4/28: For those of you who had a valid University excuse for missing a quiz, the make-up quiz will be held in class on Tue, May 4 (probably at the end).

• 4/26: Homework 8 is now available, due Tue, May 4.

• 4/21: Check out this story about algorithms that changed the world.

• 4/16: Regarding Midterm Exam 1: I may have graded problem 1 (d) too harshly -- if you think you fall into that category, bring your exam back to class and give it to me.

• 4/14: Someone asked to see an old exam 2, so here is one in pdf. It was from an honors section.

• 4/13: Homework 4 solutions are available here in PDF. The average on HW 3 was 63 (out of 85 possible points).

• 4/12: Exam 2 review is now available.

• 4/9: Correction/clarification to programming assignment: for Kruskal's algorithm, implement the disjoint sets data structure using the forest with union by rank and path compression.

• 4/7: I've postponed HW 6 due date to Wed, April 14.

• 4/6: Thanks to Wonryull, here are some sample input files (from graphs in the text book) for the programming assignment: Fig.22-3, Fig.22-7, Fig.23-4, Fig.24-4.

• 4/6: Homework 6 is now available, due Mon, Apr 12 - it is to implement Prim's and Kruskal's algorithms.

• 3/31: As discussed in class on Monday, HW 5 due date is postponed to Monday, April 5.

• 3/26: Homework 5 is now available, due Apr 2. It is a programming assignment.

• 3/23: My office hours today are changed to 4:00 - 5:00 PM.

• 3/11: Information on internship available here (followup to Nick Neumann's presentation in class last week).

• 3/9: Homework 4 is now available, due Mar 26. Hint for Problem 15-7: Assume that the jobs are ordered by increasing deadline, so that d_1 <= d_2 <= ... <= d_n. Verify that, as a result, the largest deadline is the maximum amount of time needed to achieve the maximum profit. Define P[i,j] to be the maximum profit achievable if we can only schedule (a subset of) jobs a_1,...,a_i up to time step j. To get a recursive formula for P[i,j], consider several cases: (1) The current time step j already exceeds a_i's deadline -- then there is no additional profit to be gained by considering job a_i in addition to the previous i-1 jobs. (2) There is not enough time to finish job a_i by the current time j, even if we started back at time 0 -- again, there is no additional profit to be gained by considering job a_i. (3) Time j does not exceed a_i's deadline, and there is enough time to finish job a_i by time j. Now we have two options -- either we don't use job a_i, and we do the best we can with jobs a_1,...,a_(i-1) through time j, or we do use job a_i, having it finish at time j, and do the best we can with jobs a_1,...,a_(i-1) in the time before a_i is started. Take the better of the two options.

• 3/8: Homework 3 solutions are available here in PDF. The average on HW 3 was 52 (out of 70 possible points).

• 3/2: Homework 2 solutions are available here in PDF. The average on HW 2 was 72 (out of 105 possible points).

• 3/2: Sample exam 1 available here in PDF.

• 3/1: Problem 15-7 on HW 3 is postponed to HW 4. Hint will be forthcoming.

• 3/1: My office hours on Tue, Mar 2 are changed to 4:00 - 5:30. I will be out of town Wedneday afternoon through Friday, so my office hours on Fri, Mar 5 are cancelled. Wonryull will proctor the exam on Fri, Mar 5.

• 3/1: Exam 1 review is now available.

• 2/24: Correction to lecture on 2/23: In the analysis of the expected number of probes in an unsuccessful search when using open addressing, the second summation should start at 1, instead of 0. (This is in the middle of page 80 of my lecture notes.)

• 2/23: Hoffmann Distinguished Lecture scheduled for Feb 25 has been cancelled.

• 2/23: My office hours on Tue, Feb 24 are changed from 2-3:30 to 4-5:30.

• 2/18: Homework 3 is now available, due Mar 3.

• 2/16: Homework 1 solutions are available here in PDF. The average on HW 1 was 75.

• 2/13: Exam 1 will be on Friday, March 5.

• 2/13: Undergraduate summer research grants program application deadline is Fri, Feb. 20! This is a great opportunity to spend the summer doing research and getting paid for it.

• 2/8: There is a fourth Department of Computer Science Distinguished Lecturer this month - tomorrow, Mon, Feb 9. The speaker is Prof. Devika Subramanian, Rice University. If you like, you may substitute attendance at her lecture and a report for one of your culture reports. More details here.

• 2/5: My office hours on Fri, 2/6, are cancelled. Please contact me by email if you need to see me on Fri.

• 2/3: Homework 2 is now available, due Feb 18.

• 2/2: Information about scholarships in Information Assurance is available here - meeting on Feb 6, deadline Feb 18.

• 1/30: Clarification for HW 1: You can use the limit definitions if you like for showing big-oh, etc.

• 1/30: Some issues about the partition method used in quicksort came up in class.
  • I said (and my lecture notes say) that quicksort is stable - this is incorrect! Find a counter-example.
  • Why check if A[j] is less than or equal to x (the pivot) instead of just less than, and similarly with A[i] being greater than or equal to x? If you don't have the check for equality, then you need more complicated code to make sure that you don't fall off the end of the array when j is being decremented and i is being incremented.
  • Why do the swap if the values are equal? It takes at least as much time to check if they are equal as to do the swap.
  • What if the pivot is chosen as the last element of the array segment (i.e., A[r]) and it holds the largest key? In this case, quicksort loops forever, because we haven't succeeded in reducing the problem size. It is critical that the first element (i.e., A[p]) be chosen as the pivot. You can of course swap the first and last elements initially.

• 1/30: Be sure to check out the errata web page for the textbook. Pay attention to which printing you have (not the same thing as edition).

• 1/28: Correction to due date for Culture 4: It is due Mon, Apr 12 (not Apr 13).

• 1/26: Due dates for all culture reports are now available - see calendar.

  There are three (!) Department of Computer Science Distinguished Lecturers coming in February. If you like, you may substitute attendance at their lectures and a report for up to three of your culture reports. More details here.

• 1/25: Homework 1 is available, due Wed, Feb 4.

• 1/21: Wonryull's office has changed to 329 Bright (updated from the paper syllabus).

Back to beginning

Syllabus

Teaching Asisstant: Wonryull Koh
Office: 329 H.R. Bright Bldg
Office Hours: Wednesdays and Thursdays 10:00 - 11:30 AM
Email: wkoh@cs.tamu.edu
Office Phone: 862-2326

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

• mathematical solutions to recurrence relations
• mathematical induction
• data structures including linked lists, arrays, stacks, queues, and trees
• knowledge of a high level 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 50% - There will be two exams during the semester, worth 15% each, and one final exam, worth 20%. The exams will be held in class.

• homework 35% - Pencil and paper exercises and some programming assignments (e.g., to compare the performance of two competing algorithms).

• 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 five technical papers in computer science journals. More details are available here.

No late assignments will be accepted. There will be no make-up exams or quizzes. 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:
A for 90% or above of the total points,
B for 80 to 89%,
C for 70 to 79%,
D for 60 to 69%,
and F for less than 60%.

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. More information on academic integrity, plagiarism, etc. is available at the TAMU Plagiarism web site.

University Regulations, Section 42, 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

• readings
• homework
• quizzes
• exams
• culture reports

• details on the assignments
• exam reviews

Back to beginning

Culture Reports

You are to find, read, and write short reports on five technical papers in computer science journals. Articles in the following two journals are usually at about the right level:

• Communications of the ACM
• IEEE Computer

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

• correct bibliographic information for the paper (title of article; names of all authors; name of journal with volume, number, date and page numbers)
• a summary of the paper contents
• at least one comment about the paper or question that it raised in your mind, indicating that you have thought critically about the material.

DO NOT PLAGIARIZE! You must write up your summary in your own words. See collaboration policy in syllabus.

Report due dates are indicated in the calendar and are summarized here:

• Culture Report 1: due 12:40 PM, Mon, Feb 9, 2004
• Culture Report 2: due 12:40 PM, Fri, Feb 27, 2004
• Culture Report 3: due 12:40 PM, Wed, Mar 24, 2004
• Culture Report 4: due 12:40 PM, Mon, Apr 12, 2004
• Culture Report 5: due 12:40 PM, Fri, Apr 30, 2004

On occasion, a culture assignment may be substituted by attendance at and a report on a Distinguished Lecture. These opportunities are:

• Thu, Feb 5, 4:00pm (Rm 302 HRBB), Michi Henning, ZeroC, Inc., "A New Approach to Object-Oriented Middleware"
• Mon, Feb 9, 2:00pm (Rm 302 HRBB), Devika Subramanian, Rice University, "Statistical Machine Learning and its Applications in Science and Engineering"
• Wed, Feb 18, 4:10pm (Rm 124 HRBB), Gene H. Golub, Stanford University, "Shape from Moments"
• *** Hoffmann lecture cancelled ***

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

• name and professional affiliation of the speaker
• a summary of the seminar
• at least one comment about the seminar or question that it raised in your mind, indicating that you have thought critically about the material.

Back to beginning

Useful Links

• Texas A&M Computing Society (TACS) -- student organization for those interested in computing. Affiliated with the two main professional organizations, ACM and IEEE Computer Society.

• Computer Science Department, TAMU

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

• Schedule of short courses offered by the CIS Computer Help and Training Group.

Careers and Mentoring

• Office of Honors Programs and Academic Scholarships

• CS Dept. Student Research Information

• TAMU Co-operative Education

• Computing Research Association Distributed Mentor Project for Undergraduate Females in Computer Science and Engineering: If you think you might be interested in graduate school in CS or CE, this could be a great opportunity for you when you are a sophomore or junior. Be thinking ahead!

Back to beginning