Course Objectives

This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their running times. After a brief review of prerequisite material (asymptotics, recurrences, sorting), we will discuss efficient algorithms for basic graph problems (minimum spanning trees, shortest paths, connectivity problem, network flows), solving optimization problems through greedy algorithms and dynamic programming, computational geometry, proofs of intractability and NP-completeness, and approximation algorithms.

Text

Required:
Algorithm Design by Jon Kleinberg and Éva Tardos, 2005, Addison-Wesley, ISBN: 0321295358.
Recommended Reference:
Introduction to Algorithms (2nd Edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGraw Hill, 2002.

Prerequisites

CMSC 351. Each student is expected to have basic programming skills (programming with loops, pointers, structures, recursion), discrete mathematics (proof by induction, sets, permutations, combinations, and probability), understanding of basic data structures (lists, stacks, queues, trees, graphs, and heaps), knowledge of sorting algorithms (MergeSort, QuickSort, HeapSort) and basic graph algorithms (DFS and BFS), and basic calculus (manipulation of logarithms, differentiation, integration). If there is any material that seems unfamiliar, please see me or the teaching assistant as soon as possible to head off any problems.

Course Work

Course work will consist of (around 5-6) homework assignments (about one every week and a half) and 2 exams (a midterm and a comprehensive final). Tentative weights: Homeworks 25%, midterm 30%, final exam 45%. (Note that these weights are subject to change.) The midterm is tentatively scheduled for Tue, Apr 29, and the final exam will be Friday, May 16, 8:00-10:00 am.

Homeworks are to be turned by the start of class on the due date. No late homeworks will be accepted, but the lowest homework grade will be dropped. (In other words, turn in what you have by the start of class. If your schedule is too busy, just drop the homework. But, try your best to save the dropped homework for the latter half of the semester, when you might really need it.) In exceptional circumstances (illness, university business, religious observances) extensions may be granted. However, all extensions must be approved by me BEFORE the due date.

Homeworks must either be neatly written or typeset. Poorly written work will not be graded. You are encouraged to use LaTeX for typesetting your homeworks. (It is the best system for typesetting mathematics, it is freely available, and knowledge of LaTeX is often expected of students going to graduate school.) We will provide a basic guide on using Latex on the course website, and the course staff will be happy to answer questions about LaTex.

When writing algorithms be sure not only that your solution is correct, but also that it is easy for the grader to understand why your solution is correct. Part of your grade will be based not only on correctness, but also on the clarity, simplicity, and elegance of your solution.

Some homeworks will have a special challenge problem. Points from the challenge problems are extra credit. This means that I do not consider these points until after the final course cutoffs have been set. Each semester extra credit points usually account for at least few students getting one higher letter grade (e.g., from a B+ to A-).

Working in Groups

Some people learn better in a group setting and others learn better individually. This semester we will experiment with a group homeworks. For each homework assignment, you are allowed to work either individually or in groups of two or three people. You pick your own group members, and may use different groups for different homeworks. Each group shall hand in one homework with the names of all the members of the group. All the members of the group will share the same grade. Grading standards will be the same, irrespective of whether the assignment is done individually or in a group, but I will expect group homeworks to be neatly written and well organized (because there is one document to be prepared for the entire group).

It may seem at first that groups will have an obvious advantage over people working individually. However, this is not true for a couple of reasons. First, when working in a group it is important the final document reflect a common vision of the group, resolving any differences among the group members. Second, the exams (which are worth much more than the homeworks) require a deep understanding of the methods used in solving homework problems. Group members that only have a superficial understanding of the material will pay a heavy price on the exams. In-depth knowledge only comes by struggling (often for hours) with different approaches and solution strategies.

Academic Dishonesty

You may discuss homework problems and general solution strategies with classmates (whether inside or outside your group), but when it comes to formulating and writing solutions you must work alone or only with your fellow group members. If you make use of other sources in coming up with your answers you must cite these sources clearly. (This includes papers or books in the literature, friends or classmates, and information downloaded from the web.) Instances of academic dishonesty will be dealt with harshly, and usually result in a hearing in front of a student honor council, and a grade of XF.

Topics

The topics and order listed below are tentative and subject to change.

Review of algorithm analysis and sorting:
Review of asymptotics, summations, recurrences, sorting algorithms, selection, and lower bounds for sorting.
Graph Algorithms:
Basic definitions, connectivity and traversals (BFS and DFS), directed acyclic graphs and topological ordering.
Greedy Algorithms:
Shortest paths in a graph, minimum spanning trees, clustering.
Divide and Conquer:
Closest pair, integer multiplication.
Dynamic Programming:
Weighted interval scheduling, subset sums and knapsacks, shortest paths in a graph.
NP and Computational Intractability:
Polynomial-time reductions, the definition of NP, NP-complete problems.
Approximation Algorithms:
Greedy algorithms and bounds on the optimum. Examples of approximation algorithms.
Randomized Algorithms:
Random variables and their expectations. Examples of randomized algorithms.