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?