CMSC 251: Algorithms
Course Syllabus
Spring 1998

Instructor:

Dave Mount. Office: AVW 3209. Email: mount@cs.umd.edu. Office phone: (301) 405-2704. Office hours: Mon-Wed 2:00-3:00. I am also available immediately after class for questions. Feel free to send me email if you cannot make these times to set up another time.

Teaching Assistant:

Kyongil Yoon. Office: AVW 1151. Email: kiyoon@cs.umd.edu. Office hours: Tue 2:00-3:00, Wed 1:00-2:00. Send him email if you cannot make these times, to set up another time.

Class Time:

Tue, Thur 11:00-12:15. Room: CLB 0111.

Course Overview:

This course presents an introduction to the techniques for designing efficient computer algorithms, proving their correctness, and analyzing their running times. General topics include asymptotics, solving summations and recurrences, algorithm design techniques (such as divide-and-conquer, dynamic programming, and greedy algorithms), analysis of data structures, sorting, search, and selection, and introduction to NP-completeness.

Text:

T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms, McGraw Hill and MIT Press, 1990.

Prerequisites:

CMSC 112, CMSC 150. Each student is expected to know the basic concepts of programming (e.g. loops, pointers, recursion), discrete mathematics (proof by induction), and calculus (logarithms, differentiation, integration).

Course Work:

There will be about 7-10 homeworks. Because solutions will be discussed in class on the due date, homeworks are to be turned by the start of class on the due date. Late homeworks will be not be accepted. (In other words, hand in whatever you have finished.) The lowest homework grade will be dropped. In exceptional circumstances (illness, university business, religious observances) extensions may be granted. However, all extensions must be approved by the course instructor BEFORE the due date.

All class work is to be done independently. You may discuss homework problems and general solution strategies with classmates, but no written communication (by paper, on chalkboards, by email, etc.) is permitted. Instances of academic dishonesty will be dealt with harshly.

As a courtesy to the grader, homeworks are to be written neatly. 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 simplicity, clarity, and elegance of your solutions. The burden of the proof of correctness of your algorithms is on you.

Grading:

Final grades will be based on the homework assignments, two midterm exams (tentatively planned for March 3 and April 7) and a comprehensive final exam. The relative weights of these will be roughly 25% for the homework total, 20% for each midterm, and 35% for the final exam.

Syllabus:

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

Analysis of Algorithms:

Basics of the analysis of algorithms, worst-case behavior, order notation, asymptotics, recurrences, summations.

Sorting and Selection:

Comparison-based sorting algorithms (mergesort, quicksort, and heapsort), medians and order statistics, lower bounds on sorting, radix and counting sorts.

Other Algorithms:

Algorithms on graphs, strings, and geometric objects.

NP-completeness:

Complexity classes P and NP, examples of reductions.

Return to CMSC 251 Class Page.