Announcements
- Textbook:
Introduction to Algorithms (2nd edition), Cormen, Leiserson, Rivest and Stein.
- Exams: 2 midterms (20% each) and a final (30%).
- For a syllabus, or near equivalent, see last year's
517.
- The grader is Wenghui Lin, and his email is linwh0520 at hotmail.
- The practicum is an optional 1 credit component of this course.
It does not met.
Programming assigments coordinated with class material
will be assigned. If this interests you, sign up for CSC 402.
- Midterm: Friday, October 12.
- Sample midterm released.
- Histogram of midterm results.
- Final is Wednesday Dec 12, 11 to 1:30.
Class notes
- Introduction
- Machine models, solvability, correctness, efficiency.
- Sorting a hand of cards, sorting a deck of cards..
- Tools of the Trade
- The Sorting Zoo
- Hashing
- Elementary data structures (review)
- O(1) access, encoding, hash function.
- Collision resolution.
- Universal Hashing (just for fun)
- Perfect Hashing (just for fun)
- Deletion in hash tables.
- Cuckoo
Hashing (link)
- Probability and Probabilistic Analysis
- Probability spaces and axioms
- Conditional probability, independence, and Bayes
- Random variables and expectation
- Binary Search Trees
- Making and breaking lower bounds
- Lower bound on sort in the decision tree model
- Counting sort
- Radix sort
- Bucket Sort
- ---midterm---
- Median Find (just for fun!)
- Dynamic Programming
- Recurrence Equations
- By substitution
- By tree diagram
- By master formula
- Greedy Algorithms
- Graph Algorithms
- Breadth First Search
- Depth First Search
- Topological Sorting
- Strongly Connected Components
- Mininum Spanning Tree
- Binomial Queues (just for fun)
- Single Source Shortest Paths
- Linear Programming
Reading
- Chapters 1 through 3.
- Chapters 6 and 7 (Posted 8/27)
- Chapters 4 and 5 (Posted 9/7)
- Chapters 10 and 11 (Posted 9/14)
- Chapters 12 and 13 (Posted 9/26)
- Appendix C (Posted 9/28)
- Chapters 8 and 9 (posted 10/8)
- Chapters 15 and 16 (posted 10/17)
- Chapters 22, 23 and 24 (posted 11/2)
- Chapter 21 (posted 11/19)
Assignments
- 1.1-2, 1.1-5, 1.2-2, 1.2-3 and 1-1. Due: Friday, Aug 31.
- 6.4-1, 6.4-2, 6.4-3, 6.4-4; 6.5-5, 6.5-6, 6.5-7, 6.5-8. Due: Friday, Sep 14.
- 3.1-1, 3.1-2, 3.1-3, 3-1, 3-2, 3-4. Due: Friday, Sep 21.
- 11.2-1, 11.2-2, 11.2-3, 11.2-4, 11.2-5, 11.4-1, 11.4-2, 11.4-4.
Due: Friday, Sep 28.
-
12.1-1, 12.1-2, 12.1-3,
C.2-2, C.2-3, C.2-5, C.2-6,
C.3-1, C.3-2, C.3-3, C.3-4
Due: Friday, Oct 5.
-
4.1-1, 4.1-2,
4.2-1, 4.2-2, 4.2-3,
4.3-1, 4.3-2 and 4.3-3.
Due: Friday, Oct 26.
-
Problems 15-1 and 15-2.
Due: Friday, November 9.
-
22.1-1, 22.1-2, 22.1-3, 22.1-4, 22.1-5,
22.2-1, 22.2-1, 22.2-6, 22.2-7,
22.3-2, 22.3-3.
Due: Monday, Nov 19.
-
22.4-1, 22.4-2, 22.4-3, 22.5-1, 22.5-2, problem 22-4.
Hint: SCC and Topo sort.
Due: Monday, Nov 26.
Practicum
- Write one of the n log n sorting routines in JavaScript.
The starting point is webpage on
selection sort. Due Monday, Sep 10.
- An exercise in hashing,
Due Monday, Sep 24.
- An exercise in tree rotation, called double cross the boss.
Due Friday, October 19 (on or before the break).
- Write a web page for the Longest Common Subsequence program.
Implement the dynamic programming algorithm for LCS in javascript in
your web page. It should take two inputs and show the dynamic programming
table and the result.
Note: Try to make a nice presentation.
Due Friday, November 16.
References