Design and Analysis of Algorithms -- CSE 101

Finals week schedule:

Instructor office hours: Tuesday 2-4, APM 3337C

TA office hours: Wednesday 4-5:30, APM 3349A

Final review: noon-1:50pm Thursday, HSS 1330 (same room as discussion sections have been held in)

Final Friday 11:30-2:30, Center 115

Homework 1 (due Oct. 20): Postscript HTML

Notes on Multiplication Using Divide-and-Conquer: Postscript HTML There is a bug in the algorithm in these notes - there should be a base case that just multiplies the bits together if there is at most 1 bit in the numbers (n<=1).

10/6/98: Optional review problems on asymptotic notation, sums, and recurrences (not to be turned in): Exercises 2.1-1 through 2.1-7, Problems 2-1 through 2-4, Exercises 3.1-1, 3.1-5, 4.1-1, 4.1-2, 4.1-4 through 4.1-6, 4.2-1 through 4.2-5, 4.3-1 through 4.3-3, Problems 4-1, 4-4. The "Problems" are especially helpful in checking yourself to see that you understand these topics. To check some of your answers, here are the answers to Problem 2-2 and Problem 4-1: Postscript HTML

Quicksort Correctness Proof: Postscript HTML

Practice Midterm Questions: Postscript HTML There is a bug in the algorithm of question 3 - a should be the number of elements in a third of the array, (r-p+1)/3. Then lines 3-5 should merge-sort-three elements p to p+a, p+a+1 to p+2a, and p+2a+1 to r. Lines 6-7 should call merge with p, p+a, p+2a, then with p, p+2a, r.

Practice Midterm Answers: Postscript HTML

Homework 2 (due November 17, at the beginning of lecture): Postscript HTML

Homework 1 Answers (Note that some of these answers may include more detail than would necessarily be expected of you. Also, the run-this-algorithm-on-this-example answers are fairly straightforward, and are not included here - ask a TA if you have questions about these.) Postscript HTML

Homework 3 (due Friday, December 4, at the beginning of section): Postscript HTML

Homework 2 answers: Postscript

Final reading list: Postscript HTML

Final practice questions: Postscript

Homework 3 answers: Postscript HTML

Final practice answers: Postscript

Instructor:

Chris Rosin

Class:

Tuesday and Thursday, 12:45-2:05; Center Hall 115

Discussion Session:

Friday, 3:35-4:25; HSS 1330

email:

cse101-request@cs.ucsd.edu

WWW:

http://www.cse.ucsd.edu/classes/fa98/cse101

Instructor Office Hours:

Tuesday 2:05pm-4:00pm, Thursday 10:30am-11:30am; 3337C AP&M.

TAs:

Chris Vogt, James Brannick

TA Office Hours:

Monday 12:00-1:30pm, 3337A AP&M. Wednesday 4:00-5:30pm, 3349A AP&M.

Prerequisites:

CSE 21, CSE 100.

Text Book:

Cormen, Leiserson, and Rivest: Introduction to Algorithms

Grading:

There will be three homework assignments, a mid-term exam, and a final exam. Homework will account for 30% of the grade for the class, the mid-term will account for 30%, and the final will account for the remaining 40%.

Homework is due at the beginning of lecture (or discussion section) on the day given on the assignment. Late homework will only be accepted at the beginning of the next lecture or discussion section after the due date, and will be marked off 20%. After that, late homework will not be accepted.

You may talk to other students in the course about homework problems, but the write-up you hand in must be your own: in your own words, reflecting your own understanding of the solution. Don't look for answers to homework problems in other texts, but if you accidentally find a solution while studying a different text or the solutions to another problem set, the reference should be credited. If this happens, the write-up you hand in should still be your own; such a solution may be given partial or no credit if it follows the source too closely. Note that copying another solution, with superficial modifications such as variable name changes, does not constitute ``doing your own write-up.''

Some homework and exam problems will only require you to present a brief solution, but others will ask for proofs. Grading of problems that ask for proofs will be based both on correctness and on logical consistency and completeness, i.e., ``mathematical style.'' For these problems, it is your obligation to provide a compelling argument that forces the reader to believe the result, not just notes from which a proof might be reconstructed.

Topics:

We generally won't be using class time to review topics that you have already seen in CSE 20, 21, and 100. If you need review on these topics, consult chapters 2-6 for mathematical preliminaries, and chapters 11-15 and 19-22 for data structures. We will sometimes use results on data structures from CSE 100 without reviewing their foundations; feel free to do this when solving homework and exam problems.

A tentative schedule of topics and corresponding reading is given below. This schedule may change - updated details will always be given in class.

Divide & Conquer, Sorting, and Selection:

Introduction, Insertion Sort, and Merge Sort (Chapter 1), Quicksort (8), Counting Sort (9.2), Selection (10). Homework 1 will cover this material.

Dynamic Programming, Greedy Algorithms, and Graph Problems:

Dynamic Programming and Matrix Chain Multiplication (16.1-16.2), All-Pairs Shortest Paths (26.1-26.2), Greedy Algorithms and Scheduling (17.1-17.2), Graphs and BFS (23.1-23.2), Minimum Spanning Trees (24), Single-Source Shortest Paths (25.1-25.2). Homework 2 will cover this material. The midterm will probably cover material through All-Pairs Shortest Paths.

Hard Problems:

Lower Bounds (9.1), NP-Completeness (36), Approximation Algorithms (37), Heuristics and Exhaustive Methods (not in text), Parallel Computers (30). Homework 3 will cover this material.