**Instructor:**
Neil Rhodes

**Email:**
nrhodes@cs.ucsd.edu

**Office:**
APM 3151

**Office hours:**
Tuesday 2:30-3:30 Thursday 3:30-4:30 or by appointment; drop-ins are welcome.

Unfortunately, I am unable to answer questions after lecture, as I have another class immediately after. I will usually be early to class, though, and can answer questions then.

**TAs:**

- Dipti Borkar (dborkar@cs.ucsd.edu) Office hours: Tuesday 1-2, Wednesday 11-12, EBU-1 6307 First week only: Thursday 1-2
- Qian Peng (qpeng@cs.ucsd.edu) Office hours 9th week: Tuesday 6:30-8:30 EBU-1 6307 No office hours 10th week Office hours: finals week Tuesday: 5:30-6:30

**Tutors:**

- Ming Kawaguchi (mwookawa@ieng9.ucsd.edu) Office hours: Monday 12-1, EBU-1 6307 Extra office hours: Saturday 10th week 1-2
- John Lee (johnchunyuenlee@yahoo.com) Office hours: Monday 1-2, EBU-1 6307
- Adam O'Neill (amoneill@ucsd.edu) Office hours: Wednesday 5-6, EBU-1 6307 Extra office hours: Friday 10th week 2-3 Tuesday finals week 2-3
- Nakul Verma (naverma@cs.ucsd.edu) Office hours: Wednesday 3-4, EBU-1 6307

**Announcements:**

Monday, finals week. I anticipate being 30-60 mminutes late for the review session that starts at 3:00. However, we can stil run the review session for two hours since we have the room until 6.

3/2/05: Homework 0, exercise 3 (Edmonds 3.9.1). Instead of doing all five problems in this exercise from Edmonds, do only the first four.

**Lectures:**
Tuesday/Thursday 11:00-12:20 Center 113

**Mandatory Discussion Section :**
Fr 4:00-4:50 HSS 1330 *(Keep this time free! Midterms will take place during this time.)*

**Website:**
http://www.cse.ucsd.edu/classes/sp05/cse101

**Class mailing list:**
Mailing list is cse101@cs.ucsd.edu. Add yourself to the list by sending email to cse101-join@cs.ucsd.edu.
I'll use this list only for important messages like corrections to homework, or cancellations of class.

**Discussion board:**
Discussion board available at http://discus.ucsd.edu. TAs and Instructor will monitor this board.

**Textbook:**
*Algorithm Design* by Kleinberg and Tardos. ISBN: 0-321-29535-8. This book was scheduled to arrive at the bookstore by March 25.
This book was just published, so used copies will not be available.
In addition, a supplementary PDF Edmonds textbook by Jeff Edmonds is available.

**Prerequisites:**
CSE 12, CSE 21, CSE 100 (or equivalents).
You should already be familiar with:

- Solving recurrence relations
- Proofs (for example, by induction, contradiction)
- Combinatorics
- Probability
- Performance analysis (big-O notation)

This information will not be covered in depth in lecture, but will be reviewed in the discussion section first week (day 2.5). Your first homework (Homework 0, not for credit) will deal with these prerequisites. Please do the homework even though it isn't for credit; it'll make sure you are familiar with material we assume, and will provide you an opportunity to learn how we grade and what we expect.

There are ten weeks in the quarter, with 2 lectures per week. I'll be calling them day 1 through day 20. The discussion sections will be referred to as day 2.5, day 4.5, through day 20.5.

**Day 1:** Introduction, Stable matching (Day 1 Slides).

**Day 2:** Runtimes, Loop invariants (Day 2 Slides). Read chapters 1-2 of Kleinberg, Chapter 8 of Edmonds.

**Day 2.5:** Discussions session. Inductive proofs, proving O(n), recurrence relations (Discussion 2.5 Slides).

**Day 3:** Greedy algorithms. Read chapter 4 of Kleinberg. (Day 3 Slides).

**Day 4:** Greedy algorithms. Homework 0 due (Homework 0 solution). (Day 4 Slides).

**Day 5,6:** Greedy algorithms, Divide & Conquer. Read Chapter 5 of Kleinberg (Dijkstras Alg Example)
(Day 5 Slides Day 6 Slides)

**Day 7:** Divide & Conquer. Quicksort, lower bounds on comparison sorting (Day 7 Slides, Inked Slides (pw=cse101))

**Day 8:** Divide & Conquer. Closest pair, Integer Multiplication, Master method for Recurrence Relations
Homework 1 due (Homework 1 solution)(Day 8 Slides)

**Day 9:** Dynamic Programming. (Day 9 Slides)

**Day 10:** Dynamic Programming. (Day 10 Slides)

**Day 10.5**: Midterm 1 Midterm 1 solution

**Day 11**: Midterm review

**Day 12**: Dynamic programming. (Day 12 Slides, Inked Slides (pw=cse101)) Homework 2 due (Homework 2 solution)

**Day 13**: Backtracking. (Day 13 Slides, Inked Slides (pw=cse101))

**Day 14**: Branch and Bound. (Day 14 Slides, Inked Slides (pw=cse101))

**Day 14.5**: Midterm 2 11-12 Peterson 108 (email me if you need to take it at the regular 4-5 time in HSS 1330)

**Day 15**: Network Flow. (Day 15 Slides, NetworkFlowExample, Inked Slides (pw=cse101))

**Day 16-18**: Network Flow. (Day 16 Slides, Inked Slides (pw=cse101)) Homework 3 due ( Homework 3 solution)

**Day 19-20**: NP-Completeness (Day 19-20 Slides, Inked Slides (pw=cse101) Homework 4 due
Homework 4 solution

The breakdown of your grade for this class is as follows:

30% 2 Midterm Exams (the lower midterm is dropped) (

Bring Photo ID)40% Final (

Bring Photo ID)30% Homework (4 assignments, the lowest score is dropped)

Grades are assigned as follows:

A ~85% and above

B ~75% - ~85%

C ~60% - ~75%

D ~45% - ~60%

F below 45%

For the Final, you can bring a 8.5x11 piece of paper with handwritten notes on both sides. You can download a study outline. The final is on Wednesday, June 8, from 11:30-2:30 in our normal classroom.

There is a practice final. The solution is available (username="solutions" password="abc123".

There is one review session Friday, 10th week, from 4 to 6 in HSS 1330.

There is a second review session Monday, finals week, from 3 to 5 in PCYNH 122. See announcements for time change!!

The first midterm will be a combination of multiple choice and free response. It will be given in Center 101 April 29 from 4-5 PM. Here's the material that the midterm exam will cover:

From Kleinberg: Chapter 1 (all) includes Stable matching problem Chapter 2 (all): includes Asymptotic growth (O, Omega, Theta, and proving), Priority Queues Chapter 3 (all): Graphs Chapter 4 (all but 4.8, 4.9): Greedy algorithms Chapter 5 (all but 5.6): Divide & Conquer

Everything covered in lecture/slides, including: Quicksort (not in Kleinberg book) Master method for solving recurrences (using it; not how to prove it).

From Edmonds book: Chapter 8 (all): loop invariants and proving correctness

and will cover through Chapter 5,

The second midterm will be a combination of multiple choice and free response. It will be given in Peterson 108 May 13th from 11-12. Here's the material that the midterm exam will cover:

From Kleinberg: Chapter 1 (all) includes Stable matching problem Chapter 2 (all): includes Asymptotic growth (O, Omega, Theta, and proving), Priority Queues Chapter 3 (all): Graphs Chapter 4 (all but 4.8, 4.9): Greedy algorithms Chapter 5 (all but 5.6): Divide & Conquer Chapter 6 (all) Dynamic Programming

Everything covered in lecture/slides, including: Quicksort (not in Kleinberg book) Master method for solving recurrences (using it; not how to prove it).

From Edmonds book: Chapter 8 (all): loop invariants and proving correctness

Midterm 2 solution is available. Note that since question 2 had 2 possible correct answers, and we didn't find that until after some of the exams had been handed back, all students will receive 4 points more than are marked on their exam.

Please turn in your homework on 3-hole punched paper with each problem on a separate page (for ease of grading). Student name(s) should appear at the top of each page.

Homework must be turned in during the first ten minutes of class on the day it is due. If you can't make it, have a friend, classmate, or roommate bring it. Late homework will not be accepted.

Students will be allowed to solve and write up all homework assignments in groups of size up to 4. All names should appear on the assignment.

Members of a group are responsible for all parts of any assignment with their names on it. Problems should be solved by the group, not divided up between group members. Each member of a group should participate in discussions about each problem. The front page should be signed by each member of a group; this is interpreted as the statement: "I participated in discussion for each problem, and have read and understood the answers here, which are summaries of our discussion." If this statement is true, just sign your name. If you wish to modify this statement, write and sign the modified statement instead. If the statement is not true of some of the problems, add "except for problems ...". You will not receive credit for these problems, but you also will not bear responsibility for them.

Students should not look for answers to homework problems in other texts or other sources
(e.g., on the Internet).
However, students may user other texts as a general study tool, and may accidentally see solutions to homework problems.
In this case, the student should write up the final solution without consulting this text or source, and
should give an acknowledgement of the text or source on the first page of their solutions.
Such a solution may be given partial or no credit if it too closely follows the source.
**Not giving an acknowledgement is academic dishonesty, and will be treated as such. This rule applies to any
material found on the internet, library or obtained from other people and to conversations with other people.
However, it does not apply to material handed out in class or on the class website for this quarter, or to conversations with
the instructor or teaching assistants.**

Be sure to follow these guidelines:

- Do not discuss problems with people outside your group (except with the TAs or me).
- Do not share written solutions or partial solutions with other groups.
- Prepare your final written solution without consulting any written material except class notes and the class text.
- Acknowledge all supplementary texts or sources that had solutions to homework problems.

Following is a list of the topics we'll be discussing and their tentative order:

- Stable matching (as an example algorithm)
- Greedy algorithms
- Divide and Conquer
- Dynamic Programming
- Network Flow
- Backtracking
- Randomized Algorithms
- P/NP