Welcome to the course web page for CSE 465!
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 |
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.
Solutions to Homework 1 will be available on Angel as of Tuesday morning, Jan. 30.
Lec. | Date | Notes | Topics | Reading | Homework |
---|---|---|---|---|---|
1 | Wed, Jan. 17 | Introduction | Levitin Ch. 1; CLRS Ch. 1,2.1,2.2 | ||
2 | Fri, Jan. 19 | Insertion Sort | CLRS Ch. 2 | HW1 out (due Jan 26) | |
3 | Mon, Jan. 22 | Asymptotic Notation, Divide and Conquer, Mergesort | CLRS Ch. 2,3. | ||
4 | Wed, Jan. 24 | Binary Search, Exponentiation, Integer Multiplication | Ch 4.2 (recursion trees) | ||
5 | Fri, Jan. 26 | Recurrences: Substitution Method | Ch. 4.1 | Hw1 in, HW2 out (due Fri, Feb. 2) | |
6 | Mon, Jan. 29 | Recurrences: Master Theorem | Ch. 4.3 | ||
7 | Wed, Jan. 31 | Quicksort: Basic Description | Chapter 7.1 | ||
8 | Fri, Feb. 2 | Quicksort Analysis | Chapter 7, Problem 7-2 | HW2 in, HW3 out (due Fri, Feb. 9) | |
9 | Mon, Feb. 5 | Quicksort Analysis and Order Statistics | Chapter 7, Problem 7-2 | ||
10 | Wed, Feb. 7 | Order Statistics: Randomized Algorithm | Ch. 9.1, 9.2 | ||
11 | Fri, Feb. 9 | 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 | 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 | 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 | 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 | 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 | 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 | 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. |