CS 140: HMC - Fall 2003

Computer Science 140 and Mathematics 168
Algorithms (at HMC): Tuesdays and Thursdays, 2:45-4 PM, Beckman 126
Fall 2002

Professor:

Belinda Thom ("B" for short)

E-mail:

Belinda_Thom@hmc.edu

Office:

Olin 1241

Phone:

607-9662

My Office Hours:
(1241 Olin)

M 10:15-11:15 PM
Tu 4:30-6 PM
W 4:30-6 PM
Th (no colloq) 4:30-6 PM
Th (colloq) 8-9 PM
F 4-5 PM

Graders:

Mark Nelson
James Darpinian
Victoria Krafft
Brian Merdian

Grader Office Hours:

Sun 9-10 PM (LAC: Baker Room)
W 7:30-9 PM (M. Nelson's suite)

Course Home-page:

www.cs.hmc.edu/courses/2003/fall/cs140

Course Mail Lists:

cs-140-l@hmc.edu, math-168-l@hmc.edu.
Note: to use this list, you must use
your subscriber email address.

Quick Links:

Grading Policy
Collaboration Policy
Detailed Schedule

What Is This Course About?

This course will introduce you to fundamental algorithm design and analysis techniques. In addition to learning about a number of important classical algorithms, you will also gain experience designing new and extending existing algorithms. This experience will include analyzing various algorithms' computational efficiency and applying them to a variety of interesting real-world computational problems.

Is This Course for You?

The short answer is Yes! -- as long as you've met a few basic requirements. Much of our time will be spent carefully analyzing algorithms using mathematical induction, recurrence relations, and summation techniques. Hence, Math 55 is a non-negotiable prerequisite. On some homeworks there will also be short programming assignments, which may be solved in a high-level language of your choice (e.g., C, C++, Java, Pascal, SML). Thus, CS 60 and CS 70 (if registered as CS 140) or Math 131 (if registered as Math 168) are also required.

Text

Introduction to Algorithms, 2nd Edition by T. Cormen, C. Leiserson, R. Rivest, and C. Stein.

Grading Policy

The components of this course that determine your grade are weighted as follows:

Participation:50 course points. Participation is made up of:
- Homework: 40 points.
- Class and/or Office Hour Participation: 10 points.
Tests: There will 3 exams in this course:
- Two Midterm Exams: 30 course points total, each equally weighted.
- A Cumulative Final Exam: 20 course points.

The exact dates and procedures for taking these exams will be announced in class as the semester progresses. The primary purpose of my exams is to assess your grasp of the course material in a calm and unhurried setting; I am leaning towards untimed take-home exams.

Within the A to D range, my grading scheme will be relatively linear. However, if your lack-of-participation lies above the following thresholds, you risk not passing this class:

Attendance: On-time attendance to class is absolutely required. If you are sick or have a special reason for missing class, an excused absence may be obtained by sending me email before the class that you will miss; otherwise your presence is expected. Please make sure to arrive on-time as a courtesy to myself and your classmates. Thresholds: more than two unexcused absences; more than three tardy arrivals.
Homework: There are two assignments each week. On Tuesdays, you will receive a short assignment, typically 2-3 problems, worth approximately 20-35 points. This assignment is due on Thursday at the beginning of class. On Thursdays, you will receive a longer assignment, typically 5-6 problems, worth approximately 65-80 points. This assignment is due on the following Tuesday at the beginning of class. Homeworks are posted on this web-site in the schedule section. A late homework will not be accepted unless you have made a special arrangement with me in advance. Thresholds: more than two missed homeworks; more than one missed long homework.

I understand that, from time to time, emergencies and unforeseen circumstances might arise. In such cases, you must proactively seek me out as soon as possible so that we can determine what course of action is reasonable.

Strategy for Maximizing Your Grade

The main reason for such a steady and consistent workload -- two-homeworks per-week is significant -- is to keep you actively engaged in the material as we cover it. Why? There is a big difference between passively digesting material and actively exploring it. All of my grading policies -- the stress on attendance, homework, and participation -- are designed to foster such active exploration.

The thresholds given above are with respect to passing the class. The best way to improve your grade beyond this minimal level is to aggressively maximize your performance on homeworks. I am very happy to guide you as you work through your solutions, and this is a great reason to come to my Office Hours! In the past, students who have done well have often used this strategy. Another great way to improve your grade is to do extra credit (EC) problems. Note that EC grading will be especially strict. Again, using office hours to maximize the return you get on this effort is a great idea. Another way to get EC credit is to put in a reasonable amount of effort into every homework (i.e. don't miss any), in which case I will drop your two lowest grades when calculating your homework average.

Grading Feedback

I am eager to provide high quality assessment of your work. Should you have an issue with particular grades, please come see me.

Collaboration Policy

Only collaboration with other students in this class is allowed -- in fact, I encourage it! Collaboration includes discussing approaches to solving a problem. Copying written solutions from any source (such as person, a text book, or a web page) is not allowed. On each submitted homework, please indicate the names of all people with whom you discussed your solutions.

There should be no collaboration on any exam. All parties, including off-campus students, are expected to follow the Harvey Mudd Honor code.

There is another section of this class being taught at Pomona college. We will be running separate classes; for this class, use my office hours.

Summary of Topics

Fundamentals of Algorithm Design and Analysis
- Worst-case analysis of algorithms.
- Asymptotics and nonlinear recurrence relations.
- Sorting algorithms.
- Order statistics.
- Divide-and-Conquer paradigm.
- Dynamic programming paradigm.
- Greed paradigm.
- Amortized analysis.
Fundamental Data Structures
- Union-Find structures.
- Red-Black trees.
- B-Trees.
Graph Algorithms
- Data structures for graphs.
- Basic graph operations: depth-first, breadth-first, top-sort.
- Shortest path algorithms.
- Minimum spanning tree algorithms.
- Network flow algorithms.
Linear Programming and the Simplex Algorithm
NP-Completeness and Approximation Algorithms
- Polynomial-time reductions.
- Karp's NP-Complete problems and others.
- Approximation algorithms.

Detailed Schedule

Note that for future dates, this schedule is tentative! As we progress through the class, I will update it so that past dates correspond to what actually happened.

Homework (HW) Notes: As they become available, assignments are posted here. The "H" part of a homework link provides a postscript file, and the "W" part of the link provides a tex file, which will make it easier for you to Latex your solutions. I encourage you to use Latex to writeup solutions -- although you are by no means required to do so -- because it is a very valuable skill. Should you initially need help in this endeavor, contact one of the graders or myself for assistance. You can compile Latex code on turing.

Topics that are itemized after a "HW" number that are displayed in bold italics correspond to tasks that require you to write code. For these parts of HWs, your grade will be almost entirely based upon turning in working code. Be sure to plan ahead in these cases; debugging effort can be hard to predict in advance.

Week	Lec	Tuesday	Homework	Lec	Thursday	Homework
9/1	1	Introduction	H W 1a: Logs, Induction, Extra Credit (EC)	2	Asymptotic Notation	H W 1b: Growth, Rank, Stock Market, (EC)
9/8	3	Recurrence Relations: Sorting	H W 2a: Divide-n-conquer! (EC)	4	More Sorting Analysis, Lower Bounds	H W 2b: Heaps, Various Sort Analyses, Lower Bounds
9/15	5	Linear Sort, Order Stats	H W 3a: Variable Length Sort, Oil of Olay	7	Dynamic Prog. (DP)	H W 3b: Monotonic Subseq, Skiing, (EC)
9/22	7	More on DP	H W 4a: Load Balance	8	Greed	H W 4b: *DP_change*, LCS, Greed (EC)
9/29	9	DP and Greed	H W 5a: Party Fun!	10	Amortization Abstract Data Types (ADTs)	H W 5b: Counters, Arrays, Stacks, Trees
10/6	11	More ADTs: Balanced Trees	Study for MT	12	Midterm Review	MT #1
10/13	13	More Balanced Trees, Graph Data Structures	H W 7a: Amortized Heap, Review	14	Graph Algs: BFS, DFS, TopSort	H W 7b: Cycle Detection, Diams
10/20		no class: fall recess		15	More Graph Algs: Shortest Paths, Floyd-Warshall and Bellman-Ford	H W 8b: FW, Neg. Cost Cycle Detection, Network Reliabilty
10/27	16	More Graph Algs: Dijkstra	H W 9a: Prove Dijk.	17	Johnson	H W 9b: Get-rich, On-board Navig., Johnson
11/3	18	MST: Prim	H W 10a: MST: Divide-n-Conquer	19	MST: Kruskall, Union-Find	H W 10b: Integer Weights, Baruvka
11/10	20	NW-Flow	H W 11a: Network Flow Proofs	21	More NW-Flow	H W 11b: Greed is Good, Unicycle Games, NASA
11/17	22	Linear Programming	MT 2 Review Guide		Review	MT #2
11/24	23	NP-Completeness (NPC)	none	n/a	no class: Thanksgiving
12/1	24	More NPC	H W 12a: Hit Set, Complexity Games	25	And more NPC	H W 12b: Kernel, ILP, Spam, 2-SAT
12/8	26	Approximation Algs.	H W 13a: Network Reliability	27	More on Approximation Algs	None
12/16	no class: finals week Final Study Guide

Last modified August 2003 by Belinda_Thom@hmc.edu

Computer Science 140 and Mathematics 168 Algorithms (at HMC): Tuesdays and Thursdays, 2:45-4 PM, Beckman 126 Fall 2002