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, divide-and-conquer algorithms, dynamic programming, network-flow algorithms, NP completeness and computational intractability, approximation algorithms, and randomized algorithms.

Text

• Required: None
• Recommended references:
  • Algorithm Design, by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2005.
  • Introduction to Algorithms, (3rd Edition), by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGraw-Hill, 2009.
  • Algorithms, by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 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:30am-12: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 (Floyd-Warshall and Bellman-Ford)

Network Flow:

Network flows (Ford-Fulkerson), bipartite matching, circulations and applications

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 (vertex cover, travelling salesman, set cover)