Spring 2003 2003-01-30

CMSC 351 - INTRODUCTION TO ALGORITHMS

Lecture Notes.

LECTURES:

Section 0101 Prof Perlis Tu/Th 11:00 - 12:15 CSI 3117
Section 0201 Prof Perlis Tu/Th 12:30 - 01:45 CSI 3117
Section 0301 Prof Kruskal Tu/Th 12:30 - 01:45 CSI 2117

OFFICE HOURS and EMAIL:

Prof C. Kruskal kruskal@cs.umd.edu Tu 10:30-12:30 AVW 3215
Prof D. Perlis perlis@cs.umd.edu Tu,Th 2:00-3:00pm AVW 3259
Srinivas Kashyap raaghav@cs.umd.edu W 10:00-12:00 AVW 1151
Ji Sun Shin sunny@cs.umd.edu M,F 11:00-12:00 AVW 1151
Nikhil Swamy nswamy@cs.umd.edu Tu,Th 9:30-10:30am AVW 1151

APPROXIMATE course contents and APPROXIMATE timetable:

Jan 28  - Algorithms, problems, programs
Jan 30  - Sorting and runtime

Feb  4  - Review of calculus, induction, and infinity
Feb  6  - More induction              [hwk 1 due]

Feb 11  - Probability
Feb 13  - Probability                 [hwk 2 due]

Feb 18  - SNOW DAY
Feb 20  - Order of functions

Feb 25  - Recurrence equations        [hwk 3 due]
Feb 27  - Master Theorem

Mar  4  - Summations

Mar  6  - Summations                  [hwk 4 due]

Mar 11  - Review
Mar 13  - EXAM I

Mar 18  - Quicksort
Mar 20  - Heap Sort                   

Mar 25    SPRING BREAK
Mar 27    SPRING BREAK

Apr  1  - Sorting bounds
Apr  3  - Linear-time sorting         [hwk 5 due]

Apr  8  - Graphs
Apr 10  - Graphs                      [hwk 6]

Apr 15  - Parallelism
Apr 17  - Parallelism                 [hwk 7 due]

Apr 22  - Complexity overview         [PROJECT due]
Apr 24  - NP Completeness             [hwk 8 due]

Apr 29  - Special topic
May  1  - Special topic               [hwk 9 due]

May  6  - Review
May  8  - EXAM II

May 13  - Review

May 19  - FINAL EXAM -- Monday, 4:00--6:00 pm

TEXT: There is no official text for this course. Extensive lecture notes will be posted on the web. However, the following may be useful for those that prefer a text: Introduction to Algorithms, by Cormen et al (any edition)

Introduction to Algorithms, by Manber

Algorithms Sequential and Parallel, by Miller and Boxer

GRADE SCHEME (approximate): Midterm exams (highest of 2) 25%, Final exam 45%, HW 15%, Project 15%.

EXAMS: Your lowest midterm-exam score will be dropped. If you miss a midterm exam, it will be the one dropped. THERE WILL BE NO MAKEUP EXAMS!!!

HOMEWORK: Homework assignments will be found on the web. Homeworks are due AT THE START OF CLASS on the day indicated, and LATE OR MAKEUP HOMEWORKS WILL NOT BE ACCEPTED!!!

PROJECT: There will one programming project. Computer accounts will be assigned.

HONOR CODE: We take the Code of Academic Integrity and the University of Maryland Student Honor Pledge (``I pledge on my honor that I have not given or received any unauthorized assistance on this assignment/examination'') very seriously. For details, see Code and Pledge. Our policy is that ``authorized'' assistance includes talking together about assignments and approaches to them, but *not* writing up with assistance or collaboration on---or with access to another's---actual final materials to hand in.


Comments?