Course Objectives
This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their running times. We will discuss a number of topics, including greedy algorithms, divideandconquer algorithms, dynamic programming, networkflow algorithms, NP completeness and computational intractability, approximation algorithms, and randomized algorithms.
Text
 Required: None
 Recommended references:
 Algorithm Design, by Jon Kleinberg and Eva Tardos, AddisonWesley, 2005.
 Introduction to Algorithms, (3rd Edition), by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGrawHill, 2009.
 Algorithms, by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGrawHill, 2006.
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 (minimum spanning trees and Dijkstra's algorithm), 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.
The Other Section of 451?
There are two sections of CMSC 451 taught this semester (the other by Prof. Aravind Srinivasan). This was a fairly late arrangement, due to the large number of students enrolled. It was decided that the two sections will be run entirely independently of each other. While there will certainly be considerable overlap in the topics covered, the depth of coverage, exact choice and order of topics, number of and timings of homeworks and exams, etc. will be completely different between the two sections.
Course Work
Course work will consist of periodic homework assignments and two exams (a midterm and a comprehensive final). Tentative weights: Homeworks: 25%, Midterm: 30%, Final: 45%. (Note that these weights are subject to change.)
The Midterm will be held in class, but the exact date is yet to be determined (probably in mid to late October), and the Final Exam will be Tuesday, December 19, 10:30am12:30pm.
I plan to switch to online homework submissions this semester. Information on how to do this will be forthcoming, but will involve you either preparing your homework solutions using a word processor or writing them and scanning/photographing them. Late homeworks will be subject to a penalty of 25% of the total for each 24 hours after the deadline. 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. 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. There is no official scale to extra credit points, but each semester extra credit points usually account for at least few students getting one higher letter grade (e.g., from a B+ to A).
Academic Dishonesty
All class work is to be done independently. It is best to try to solve problems on your own, since problem solving is an important component of the course, and exam problems are often based on modifications of homework problems. You are allowed to discuss class material, homework problems, and general solution strategies with your classmates. But, when it comes to formulating or writing solutions you must work alone. You may use free and publicly available sources, such as books, journal and conference publications, and web pages, as research material for your answers. (You will not lose points for using external sources, provided that you cite your sources.)
You must clearly and explicitly cite all outside sources and materials that you made use of. I consider the use of uncited external sources as portraying someone else's work as your own, and as such it is a violation of the University's policies on academic dishonesty. Instances will be dealt with harshly and typically result in a failing course grade.
Unless otherwise specified, you should assume that the UMD Code of Academic Integrity applies.
Topics
The following list of topics is very tentative. Depending on time, some topics may be added or dropped, and the order of topics may change.
 Review of algorithm analysis:
 Example: Stable Marriage Algorithms. Review of algorithm analysis (and summations and recurrences), review of basic graph theory and graph representations.
 Graph Exploration:
 DFS and BFS, connected components, topological sorting, strong components and cut vertices
 Greedy Algorithms:
 Interval scheduling and partitioning, scheduling to minimize lateness, greedy graph algorithms (and applications), Huffman coding
 Dynamic Programming:
 Weighted interval scheduling, longest common subsequences, chain matrix multiplication, shortest paths in graphs (FloydWarshall and BellmanFord)
 Network Flow:
 Network flows (FordFulkerson), bipartite matching, circulations and applications
 NP and Computational Intractability:
 Polynomialtime reductions, the definition of NP, NPcomplete problems
 Approximation Algorithms:
 Greedy algorithms and bounds on the optimum. Examples of approximation algorithms (vertex cover, travelling salesman, set cover)
