Announcements
- Semester number is 091, first semester of 2009 year, although course begins on Wednesday, August 27,
2008.
- Required textbook:
Introduction to Algorithms (2nd edition), Cormen, Leiserson, Rivest and Stein. (follow link, amazon search seems bad)
- Programming and CSC401: let's suppose you would like to program in Javascript and DHTML. Then you will be happy to sign up for CSC 401, the practicum associated with 517. If you do, then you will be happy to learn that it will be using javascrip and DHTML, you will get one unit of credit, and studies show that you will learn the material more effectively. Those not enrolled in 401 will most probably not have programming.
- Content: for an idea of the course's contents, you can follow this web page, as it develops. Also last year's version is CSC517.018 and previous years can be found back to 2001.
- Grading: There are homeworks, one or two midterms, and a final. It is very important to do the homeworks!
- Grader: is Wenghui Lin, and his email is linwh0520 at hotmail.
- Blog: The class Blog
- Midterm: Wednesday, October 15.
- Histogram of midterm results.
- Final is scheduled for Tuesday, December 16, 11 to 1:30, in the classroom.
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
- Making and breaking lower bounds
- Lower bound on sort in the decision tree model
- Counting sort new
- Radix sort
- Bucket sort
- Recurrence Equations
- Substitution Method, Tree Method, Master Method
- Sorting algorithms, again.
- Selection in Random Linear Time
- Median Find in Deterministic Linear Time
- Hashing
- Probability and Probabilistic Analysis
- Probability spaces and axioms, see notes.
- Random variables and expectation
- Conditional probability, independence, and Bayes
- Hiring problem (number of maxima)
- Generating a random permutation.
- Hashing analysis.
- Midterm
- Binary Search Trees
- Algorithmic Paradigms
- Dynamic Programming
- Greedy Algorithms
- Linear Programming
- Graph Algorithms
- Breadth First Search
- Depth First Search
- Topological Sorting
- Strongly Connected Components
- Mininum Spanning Tree
- Single Source Shortest Paths
- Bellman-Ford
- Dijkstra
- Binomial Queues
- Fibonacci Heaps
- Fast Fourier Transform (PDF notes)
Assignments
- Problem Set 1; due Friday, Sep 12.
- Read chapters 1 and 2.
- Do problems 2-2, 2-3, and 2-4.
- Problem Set 2; due Monday, Sep 22.
- Read chapters 3, 6 and 7.
- Read class notes on Big-Oh
- Exercises 6.2-1, 6.3-1, 6.4-1, 6.4-2; Problem 6-3.
- Problem Set 3: due Monday, Sep 29
- Reread chapter 3.
- Exercises 3.1-1, 3.1-2, 3.1-3, 3.1-4.
- Problem 3-1.
- Exercise 7.1-1, Problem 7-1.
- Problem Set 4: due Monday, Oct 6
- Read chapter 4.
- Exercises 4.1-1, 4.1-2 (same proof, just use the opposite inequality everywhere, ok?), 4.2-1, 4.2-2.
- Read chapter 8.
- Exercises 8.2-1, 8.3-1, 8.3-2.
- Problem Set 5: due Monday Oct 13
- Redo the partition assignment, exercise 7.1-1. Use the array:
A = [13, 19, 9, 5, 12,8, 7, 4, 21, 2, 6, 11] (the 11 and 21 are switched from book)
- Read chapters 9 and 11.
- Exercises 11.2-2, 11.4-1, 11.4-4
- Problem Set 6: due Monday Nov 3
- Read chapters 10, 12 and 13.
- Exercises 12.1-1, 12.1-3, 12.1-4, 12.2-1, 12.2-2, 12.2-3;
- Problems 12-1, 12-2;
- Problem 13-1.
- Problem Set 7: due Monday Nov 17
- Read chapters 15 and 16
- Exercises 15.2-1, 15.4-1, 15.4-2, 15.4-5
- Problems 15-2 and 15-7.
- Exercises 16.1-1, 16.1-2, 16.3-2, 16.3-8.
- Problem 16-1.
- Problem Set 8: due Monday Nov 24
- Read chapters 29 and 22.
- Exercises 29.1-1, 29.1-2, 29.1-3, 29.3-4, 29.3-5 and 29.3-6.
- Problem Set 9: due Friday Dec 5
- Read chapters 21, 23 and 24.
- Exercises 21.1-1, 21.2-1, 21.2-2, 21.3-1, 21.3-2.
- Exercises 23.2-1 and 23.2-2.
- Problem Set 10: due Friday Dec 5 (same date as above)
Extended deadline PS 9 and 10, Monday 8
Practicum
- Project 1: due Wed, Sep 10.
- Look over the code of Enter Name.
- Make a web page using Javascript that converts teaspoons to gils.
- Look over the code of Number Build.
- Make a web page using Javascript like Number Build, except that
rather than powers of 2 only, the user can select from powers of 2, 3, 4, up to 7.
- Project 2: due Wed, Sep 17.
- Project 3: due Mon, Sep 29.
- See RANDOMIZE-IN-PLACE algorithm in chapter 5.3, page 103 on the second edition. Implement it. Start with an array of 12 cells, and a button "Randomize" that applies the algorithm with each click.
- Project 4: due Monday, Oct 13.
- Implement the Young Tableau algorithm.
- Make the HTML presentation similar to what you have been doing up to now.
- You will want a table (it can be a fixed size, say 16 by 16, and a text box for inputs.
- Show the tableau being filled and emptied item by item using a "step" button.
- Project 5: due Monday, Dec 8. New deadline.
- Implement Dijkstra's Algorithm. Let the user input nodes and edge distances.
- Use DHTML, but you do not have to visualize the graphs. You can use text input
and output.
References