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 n2 (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.DateNotesTopicsReadingHomework
1Wed, Jan. 17pdfIntroductionLevitin Ch. 1; CLRS Ch. 1,2.1,2.2
2Fri, Jan. 19pdfInsertion SortCLRS Ch. 2HW1 out (due Jan 26)
3Mon, Jan. 22 pdfAsymptotic Notation, Divide and Conquer, MergesortCLRS Ch. 2,3.
4Wed, Jan. 24 pdf Binary Search, Exponentiation, Integer MultiplicationCh 4.2 (recursion trees)
5Fri, Jan. 26 pdfRecurrences: Substitution MethodCh. 4.1Hw1 in, HW2 out (due Fri, Feb. 2)
6Mon, Jan. 29pdfRecurrences: Master TheoremCh. 4.3
7Wed, Jan. 31pdfQuicksort: Basic DescriptionChapter 7.1
8Fri, Feb. 2pdfQuicksort AnalysisChapter 7, Problem 7-2HW2 in, HW3 out (due Fri, Feb. 9)
9Mon, Feb. 5pdfQuicksort Analysis and Order StatisticsChapter 7, Problem 7-2
10Wed, Feb. 7pdfOrder Statistics: Randomized Algorithm Ch. 9.1, 9.2
11Fri, Feb. 9pdfOrder Statistics: Algorithm Analysis Ch. 9.2HW3 in, exam announcement and practice exam out
12Mon, Feb. 12Midterm 1 review
Wed, Feb. 14Canceled. Snow day.
13Fri, Feb. 16pdfAbstract Data Types, QueuesCh. 10HW4 out
14Mon, Feb. 19Priority Queues and HeapsCh. 6
15Wed, Feb. 21Heaps continuedCh. 6
16Fri, Feb. 23Heaps finished and Hashing startedCh. 6HW5 out, due Mar. 2
17Mon, Feb. 26Midterm recap
18Wed, Feb. 28pdfAnalysis of Hashing with ChainingChap. 11
19Fri, Mar. 2Binary Search TreesCh. 12
20Mon, Mar. 5 Binary search trees, continuedCh. 12
21Wed, Mar. 7pdfBalanced Search Trees: 2-3 treesNot in book. Notes are by A. Gordon-Ross from UC Riverside.
22Fri, Mar. 92-3 trees continued.
23Mon., Mar. 19pdfAugmenting Data Structures: range treesCh. 14
24Wed., Mar. 21Augmenting Data Structures: general methodology, interval treesCh. 14
25Fri., Mar. 23Augmenting Data Structures: interval treesCh. 14HW 7 out
26Mon., Mar. 26pdfGraphs: introduction
27Wed., Mar. 28Paths, shortest paths, Dijkstra's algorithm
28Fri., Mar. 30Dijkstra's algorithm: analysisHW 7 in.
29Mon., Apr. 2Midterm review
30Wed., Apr. 4BFS, DFS and topological sorting
31Fri., Apr. 6(continued for several lectures)
32Mon., Apr. 9
33Wed., Apr. 11
34Fri., Apr. 13
35Mon., Apr. 16
36Wed., Apr. 18Optimization Problems and Greedy Algorithms CLRS Ch. 16
37Fri., Apr. 20Greedy Algorithms: "Greedy Stays Ahead"
38Mon., Apr. 23pdfGreedy Algorithms: Exchange arguments
39Wed., Apr. 25Dynamic Programming. CLRS Chap. 15.
40Fri., Apr. 27Dynamic Programming (Weighted Interval Scheduling).KT p. 251-260 (on Angel)
41Mon., Apr. 30Dynamic Programming (Matrix Chain Multiplication).CLRS Ch. 15.2
42Wed., May 2 P and NP.
43Fri., May 4 Final exam review.

Adam Smith
Last modified: Wed Jun 20 21:53:33 EDT 2007