CMSC 351 Algorithms

 

Instructors:

 Samir Khuller     A.V. Williams Building  3217 Office hours:  TuTh 12:30--1:30   (or by appointment) On FRI Nov 1 I will be around at 10:30am

 Brian Postow     A.V. Williams Building  3217 Office hours:  TuTH 3:30-4:30   (or by appointment)

Teaching Assistants:

Shang-chieh J. Wu(meou@cs.umd.edu)     A.V. Williams Building  1151 Office hours: 9:00-12:00 Wed 
Srinivas Kashyap (raaghav@cfar.umd.edu)    A.V.Williams Building  1151 Office hours: 1:00p-4:00p Mon 
Haibin Ling (hbling@cs.umd.edu)     A.V. Williams Building  1151 Office hours: 12:00-2:45pm Wed  Office hour at Dec 18 will end at 1:30pm

Important Notices:



There will be an additional review session CSIC 1121 today, December 16th 6:00-7:00.

There may be a review session on Monday Dec 16th from 6:00-7:00. IF we cand find a room. If there is, it will be posted here monday afternoon.

Because classes were canceled on Thursday December 5, you do not need to do problem 5 on Homework 9. The homework IS still due on December 10 as specified.
There will be a REVIEW SESSION in CSIC 3117 on Tuesday Dec 17th from 12 to 1pm.

The final exam (for all sections) will be held in PHY 1412 on December 18, 4-6 pm. Look under COMMON FINALS FOR CMSC 251 (old number of this class). Finals
YOU MAY BRING ONE SHEET OF NOTES LIKE YOU DID FOR THE MIDTERM.


The final is now graded. Final grades will be assigned on Monday the 23rd. If you need to see your exam, you may see it on 24th Dec between 10am and 12 noon.

The midterm is now graded. The following link contains the scores based on last 4 digits of your S.ID. Scores till Now (last updated: 12/19/02) If the link does not work, it just means that the information is still being entered by the TA's. Do not send email.

If your grand total out of 53 is lower than 25, it does look as if you will not pass this class unless you get close to a FULL score on the final exam (which given your performance until now, is a low probabilty event).

The quiz will be 30 minutes during lecture on October 8. You will be allowed to bring in one sheet of paper with any formulas written on it that you want.


A sample sheet is available here (in ps) and here (in pdf)


Syllabus.ps Syllabus.pdf
NP-completeness.ps NP-completeness.pdf

Homework Assignments:

HW 1(ps) HW 1 (pdf) HW 1 Solution(ps) HW 1 Solution(pdf) HW 1 TA Explanation(pdf) HW 1 Grading Misc.(pdf) HW1 P3b Test Input(pdf)

HW 2(ps) HW 2 (pdf) HW 2 Solution(ps) HW 2 Solution(pdf) HW2 Grading Explanation(pdf)

HW 3(ps) HW 3 (pdf) HW 3 Solution(ps) HW 3 Solution(pdf) HW 3 Grading Policy (PDF) (PS)

HW 4(ps) HW 4 (pdf) Iteration Method HW 4 Solution(ps) HW 4 Solution(pdf) HW 4 Grading Policy(PDF)

HW 5(ps) HW 5 (pdf) HW 5 Solution(ps) HW 5 Solution(pdf) HW 5 Grading Explanation

HW 6(ps) HW 6 (pdf) HW 6 Solution(ps) HW 6 Solution(pdf)

HW 7(ps) HW 7 (pdf) HW 7 Solution(ps) HW 7 Solution(pdf) HW 7 Grading Explanation

HW 8(ps) HW 8 (pdf) HW 8 Solution(ps) HW 8 Solution(pdf) HW 8 Grading Explanation

HW 9(ps) HW 9 (pdf) HW 9 Solution(ps) HW 9 Solution(pdf) HW 9 Grading Explanation

Practice Problems(ps) Practice Problems(pdf)

Sample Midterm(ps) Sample Midterm(pdf) Sample Midterm Solutions(pdf)

Course Overview:

This course presents an introduction to the techniques for designing  efficient computer algorithms and analyzing their running times. General topics include asymptotics, solving summations and recurrences,  algorithm design techniques, graph algorithms and analysis of data structures,  and introduction to NP-completeness.
 

Text:

Introduction to Algorithms, Second Edition
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
published by MIT Press and McGraw-Hill.
 

Prerequisites:

CMSC 214 and CMSC 250.
Each student is expected to know the basic concepts of programming (e.g. loops, pointers, recursion), discrete mathematics (proof by induction, sets), simple data structures (lists, stacks, queues, trees), and calculus (logarithms, differentiation, integration).

Course Work:

Course work will consist of 10 homework assignments, and 3 exams (one quiz, one midterm and a comprehensive final). The quiz will be around the end of september (date will be discussed in class) and the midterm in late October. The final exam will be on ***. Homework problems will generally be mathematically oriented (some of the homeworks may involve programming). Homeworks are to be turned in at the start of class on the due date. Homeworks will usually be given out on Tuesday's and will be due a week later. Since homework solutions may be discussed in class, NO LATE HOMEWORKS WILL BE ACCEPTED. (In other words, hand in whatever you have finished.) All class work is to be done independently. The academic dishonest policy of the University will be taken very seriously. Assignments are to be written up NEATLY. Badly written assignments will not be graded. Please staple your homework. It is your responsibility to make sure that you pick up all homeworks and handouts. All course information and homeworks will be available on the web page. Solutions to homeworks will posted on the secure class web page.

Grading:

Final grades will be based on homework assignments, the quiz, the midterm exam, and the comprehensive final exam. The relative weights of these will be 15% for the homework total, 15% for the quiz, 30% for the midterm, and 40% for the final exam.
 

Syllabus:

The topics and order listed below are tentative and subject to change. Other topics to be covered time permitting: