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

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

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

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)

by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

published by MIT Press and McGraw-Hill.

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).

- Introduction (Chapter 1)
- Insertion Sort/First Analysis (Chapter 2)
- Growth of Functions (Chapter 3)
- Recurrences (Chapter 4)
- Heapsort (Chapter 6)
- Quicksort (Chapter 7)
- Graphs and Trees (Sections B.4 and B.5)
- Dijkstra's Algorithm (Section 24.3)
- NP-Completeness (Chapter 34)

- Sorting in Linear Time (Chapter 9)
- Medians and Order Statistics (Chapter 9)
- String Matching (Chapter 32)