CSE 465 Data Structures and Algorithms, Spring 2007

Welcome to the course web page for CSE 465!

Course Staff

	Office	Phone	Email @cse.psu.edu	Office Hours
Prof. Sofya Raskhodnikova	IST 343F	x3-0608	sofya	Wed. 2:45pm - 4:45pm
Prof. Adam D. Smith	IST 338K	x3-0076	asmith	Wed. 9am - 11am
T.A. Shuyi Zheng	IST 343D	x3-7324	shzheng	Thu. 3-5pm

Announcements

Mar. 17, 2007

There is an FAQ related to the programming assignment. We will update it occasionally, so please check it first if you have questions.

There will be no regular homework due on Friday March 23 (due to the programming assignment due Wednesday). However, you may resubmit a solution to question 2 from assignment 6 (on the "birthday paradox"). If you submit nothing, your original answer will be graded.

This is the question that we asked you to answer on Angel in addition to submitting the usual write up. The experiment with Angel grading was unsuccessful: looking at write ups we realized that many students either submitted only answers with no explanations or correct answers with incorrect or unrelated "explanations". As you know, we value correct reasoning much more than the ability to guess answers. You will get (full or partial) credit only for answers with correct reasoning. No credit will be given even for correct answers if no explanation is provided.

To repeat: you can resubmit a solution to this problem by Friday, March 23, before the lecture. We will grade only the latest submitted non-Angel solution.

Mar. 1, 2007

Homework 4 solutions posted on Angel. Also, check your Angel mail for an addendum to HW5, problem 2(a).

Feb. 28, 2007

Midterm 1 Solutions posted on Angel.

Feb. 15, 2007

Practice Exam solutions posted on Angel.

Feb. 12, 2007

A mistake in Problem 4 of the practice exam was corrected.

Feb. 11, 2007

Homework 3 solutions are posted on Angel.

Feb. 10, 2007

An exam announcement is posted with some further details about the exam. The most important things there are about the material on the exam and the handwritten crib sheet you should prepare. A practice exam for the first midterm has also been posted. The format is identical to that of the midterm, although the practice exam is probably a bit longer than the real one.

Feb. 7, 2007

Homework 2 solutions posted on Angel.

Jan 31, 2007

Problem 3 in Homework 2 was reworded for clarity. New version below.

Jan 29, 2007

Angel usage: We will be using Angel mainly for posting homework solutions and grades and for maintaing the class mailing list. However, another good use for us is to have a list of student names along with pictures. Please upload a good, clear picture of your face to your Angel account. This will make it easier for us to put faces to names and remember you.

Solutions to Homework 1 will be available on Angel as of Tuesday morning, Jan. 30.

Jan 23, 2007

There is a modification to homework 1. The new version is posted in the handouts section below. In Question 2(c), the values in the array should be integers between 1 and n² (that is, n squared), instead of between 1 and n. Sorry for the confusion.

Jan 18, 2007

Midterm exam times: Both exams will be held from 8:15-10:15 pm in Room IST 113 (the same building as our offices). The dates are the same as on the general information handout: Thursday, February 15 and Tuesday April 3.

Handouts

1. General Course Information: pdf
2. Chapter 1 of Levitin. Photocopy handed out in class.
3. Homework 1, due Jan. 26: pdf (modified), tex
4. Homework 2, due Feb. 2: pdf (clarified), tex
5. Pages 231-234 of Kleinberg and Tardos (integer multiplication). Photocopy handed out in class.
6. Homework 1 solutions. Available on Angel.
7. Homework 3, due Feb. 9 before class: pdf, tex
8. Homework 2 solutions. Available on Angel.
9. Exam 1 Announcement: pdf.
10. Practice exam for Midterm 1: pdf
11. Homework 3 Solutions. Available on Angel.
12. Levitin, p. 123-125 (Master theorem). Available on Angel.
13. Practice Exam 1 solutions. Available on Angel.
14. Homework 4, due Fri, Feb. 23: pdf, tex
15. Homework 5, due Fri. Mar. 2: pdf, tex
16. Midterm 1 solutions on Angel.
17. Homework 4 solutions on Angel.
18. Homework 6, due Fri. Mar. 9: pdf, tex
    Note: Programming assignment 1 is due Wed. Mar. 21 (see the FAQ).
19. Homework 7, due Fri. Mar. 30: pdf, tex
20. Homework 5 Solutions on Angel.
21. Exam 2 Announcement: pdf, tex
22. Practice exam 2: pdf
23. Practice exam 2 solutions on Angel.
24. Homework 8, due Fri. April 13: pdf, tex
25. Homework 9, due Fri. April 20: pdf, tex
26. Homework 10, due Fri. April 27: pdf, tex
27. Homework 11, due Fri. May 4: pdf
28. Homework 10 solutions (on Angel)
29. Kleinberg-Tardos, p. 251-260 (Dynamic Programming and Weighted Interval Scheduling) on Angel.

Lecture notes, syllabus, etc.

Lec.	Date	Notes	Topics	Reading	Homework
1	Wed, Jan. 17	pdf	Introduction	Levitin Ch. 1; CLRS Ch. 1,2.1,2.2
2	Fri, Jan. 19	pdf	Insertion Sort	CLRS Ch. 2	HW1 out (due Jan 26)
3	Mon, Jan. 22	pdf	Asymptotic Notation, Divide and Conquer, Mergesort	CLRS Ch. 2,3.
4	Wed, Jan. 24	pdf	Binary Search, Exponentiation, Integer Multiplication	Ch 4.2 (recursion trees)
5	Fri, Jan. 26	pdf	Recurrences: Substitution Method	Ch. 4.1	Hw1 in, HW2 out (due Fri, Feb. 2)
6	Mon, Jan. 29	pdf	Recurrences: Master Theorem	Ch. 4.3
7	Wed, Jan. 31	pdf	Quicksort: Basic Description	Chapter 7.1
8	Fri, Feb. 2	pdf	Quicksort Analysis	Chapter 7, Problem 7-2	HW2 in, HW3 out (due Fri, Feb. 9)
9	Mon, Feb. 5	pdf	Quicksort Analysis and Order Statistics	Chapter 7, Problem 7-2
10	Wed, Feb. 7	pdf	Order Statistics: Randomized Algorithm	Ch. 9.1, 9.2
11	Fri, Feb. 9	pdf	Order Statistics: Algorithm Analysis	Ch. 9.2	HW3 in, exam announcement and practice exam out
12	Mon, Feb. 12		Midterm 1 review
	Wed, Feb. 14		Canceled. Snow day.
13	Fri, Feb. 16	pdf	Abstract Data Types, Queues	Ch. 10	HW4 out
14	Mon, Feb. 19		Priority Queues and Heaps	Ch. 6
15	Wed, Feb. 21		Heaps continued	Ch. 6
16	Fri, Feb. 23		Heaps finished and Hashing started	Ch. 6	HW5 out, due Mar. 2
17	Mon, Feb. 26		Midterm recap
18	Wed, Feb. 28	pdf	Analysis of Hashing with Chaining	Chap. 11
19	Fri, Mar. 2		Binary Search Trees	Ch. 12
20	Mon, Mar. 5		Binary search trees, continued	Ch. 12
21	Wed, Mar. 7	pdf	Balanced Search Trees: 2-3 trees	Not in book.	Notes are by A. Gordon-Ross from UC Riverside.
22	Fri, Mar. 9		2-3 trees continued.
23	Mon., Mar. 19	pdf	Augmenting Data Structures: range trees	Ch. 14
24	Wed., Mar. 21		Augmenting Data Structures: general methodology, interval trees	Ch. 14
25	Fri., Mar. 23		Augmenting Data Structures: interval trees	Ch. 14	HW 7 out
26	Mon., Mar. 26	pdf	Graphs: introduction
27	Wed., Mar. 28		Paths, shortest paths, Dijkstra's algorithm
28	Fri., Mar. 30		Dijkstra's algorithm: analysis		HW 7 in.
29	Mon., Apr. 2		Midterm review
30	Wed., Apr. 4		BFS, DFS and topological sorting
31	Fri., Apr. 6		(continued for several lectures)
32	Mon., Apr. 9
33	Wed., Apr. 11
34	Fri., Apr. 13
35	Mon., Apr. 16
36	Wed., Apr. 18		Optimization Problems and Greedy Algorithms	CLRS Ch. 16
37	Fri., Apr. 20		Greedy Algorithms: "Greedy Stays Ahead"
38	Mon., Apr. 23	pdf	Greedy Algorithms: Exchange arguments
39	Wed., Apr. 25		Dynamic Programming.	CLRS Chap. 15.
40	Fri., Apr. 27		Dynamic Programming (Weighted Interval Scheduling).	KT p. 251-260 (on Angel)
41	Mon., Apr. 30		Dynamic Programming (Matrix Chain Multiplication).	CLRS Ch. 15.2
42	Wed., May 2		P and NP.
43	Fri., May 4		Final exam review.