Special Announcements
Announcements
- Textbook:
Introduction
to Algorithms (3ird edition), Cormen, Leiserson, Rivest and Stein.
- Emails to me concerning the class should be sent to the tagged email
address burt+csc517@cs.miami.edu. (Note: tags might not be working.
If I don't respond at the tagged address, send without the tag.)
- New media: announcements on
twitter/csc_517
(enable SMS - very low traffic) and the
class blog.
- Syllabus: similar to
year's version is CSC517.111 and
to many previous years.
- Practicum:
The mainline of the course will have no programming. The optional practicum will assign
you the task of implementing some of the algorithms using Javascript, CSS, and DHTML.
If you would like to take the practicum, enroll in CSC 403.
- Grading: There are homeworks, one or two midterms, and a final.
Weekly homework is assigned most Wednesdays.
It is very important to do the homeworks!
- No
late homeworks accepted after the last day of class, Friday, Dec 2.
- Home work grades: mean and std dev.
- Grader:
Fu Huansong, a.k.a. Fu, fuhuansong at gmail.
- Office hours:
I am available Fridays, 1:30 to 3:00, and by appointment.
- Midterm: Wednesday, Oct 26.
- Midterm Histogram
-
Final: Monday, December 12, in class, from 2:00-4:30 PM.
- No class on Monday Nov 14th.
Class notes
- Introduction
- Machine models, solvability, correctness, efficiency.
- Sorting a hand of cards, sorting a deck of cards..
- Cheaper by Half
- Tools of the Trade
- Recurrence Equations
- Substitution Method, Tree Method, Master Method
- Max subarray problem and Strassen multiplication (integer and matrix)
- Randomized algorithms
- Probability theory, see notes.
- Probability spaces and axioms,
- Random variables and expectation
- Conditional probability, independence, and Bayes
- Hiring problem (number of maxima)
- Generating a random permutation.
- Selection in Random Linear Time
- Partition algorithm (animation)
- The power of randomness: Median Find in Deterministic Linear Time
- Making and breaking lower bounds
- Lower bound on sort in the decision tree model
- Linear sorts
- Review of O(n2) and O(n log n) sorts:
- Searching
- Hashing
- Elementary data structures (review)
- O(1) access, encoding, hash function.
- Collision resolution.
- Linear Probing (animation), double hashing.
- Universal Hashing, Perfect Hashing
- Trees
- Midterm
- Advanced data structures
- 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
- via Topological sorting
- Dijkstra
Assignments
- Problem Set 1; due Wed, Sept 7.
- Read chapters 1 and 2.
- Exercises 1.1-3., 1.1-4, 1.1-5, 1.2-2 and 1.2-3.
- Exercises 2.1-3, 2.1-4, 2.2-1, 2.2-2, 2.2-3 and 2.2-4.
- Problem 2-1.
- Problem Set 2; due Wed, Sept 14.
- Read chapter 3
- Problem 2-2 and 2-3.
- Exercises 3.1-1, 3.1-2, 3.1-3, 3.1-4 and 3.1-5.
- Problem Set 3: due Wed, Sep 21.
- Problems 3-1, 3-2, 3-3 and 3-4.
- Read chapter 4
- Exercises 4.3-1, 4.3-2, 4.3-3, 4.3-7 and 4.3-8.
- Problem Set 4: due Wed, Sep 28.
- Exercises 4.1-1, 4.1-2, 4.1-5;
- Exercises 4.4-1, 4.4-2, 4.4-3, 4.4-4, 4.4-5;
- Exercise 4.5-1.
- Problem Set 5: due Wed, Oct 5.
- Problems 4-1 and 4-3.
- Read chapter 5.
- Exercises 5.3-2, 5.3-3, 5.3-4 and 5.3-7.
- Problem 5-1.
- Problem Set 6: due Wednesday, Oct 12.
- Read chapters 8 and 9.
- Exercises 8.2-1, 8.2-2, 8.3-1, 8.3-2, 8.4-1, 8.4-2, 8.4-3.
- Exercises 9.3-3, 9.3-5, 9.3-6, 9.3-7, 9.3-8.
- Problem Set 7: due Wednesday, Oct 19.
- Read chapter 6, 7, 10 and 11.
- Exercises 6.3-2, 6.3-3, 6.4-3, 6.4-4, 6.5-5, 6.5-7. 6.5-8.
- Problem 6-2.
- Exercises 11.1-2, 11.1-3, 11.2-1, 11.4-1, 11.4-2, 11.4-3.
- Problem Set 8: due Wednesday, Oct 26.
- Read chapter 12.
- Exercises 12.1-1, 12.1-2, 12.1-4, 12.1-5;
- Exercises 12.2-3, 12.2-5, 12.2-6;
- Exercises 12.3-1, 12.3-2, 12.3-3;
- Midterm, Wednesday, Oct 26.
- Problem Set 9: due Wednesday, Nov 9.
- Read chapters 13, 14 and 21.
- Exercises 13.3-2, 13.3-3, 13.4-3;
- Problem 13-1;
- Exercises 14.1-1, 14.1-2, 14.1-3, 14.2-1, 14.3-1;
- Exercise 21.3-3, 21.3-3, 21.3-4;
- Problem 21-1.
- Problem Set 10: due Wednesday, Nov 16.
- Read chapters 15 and 16.
- Exercises 15.4-1, 15.4-2 and 15.4-5.
- Exercises 15.5-1, 15.5-2 and 15.5-3;
- Problems 15-1, 15-4 and 15-7;
- Exercises 16.1-2, 16.1-3, 16-1.4 and 16-1.5.
- Problem Set 11: due Wednesday, Nov 30.
- Read chapters 29, 22 and 23.
- Exercises 29.1-4, 29.1-5, 29.1-6, 29.1-7 and 29.1-8.
- Exercises 29.5-5, 29.5-6 and 29.5-7.
- Exercises 22.2-7, 22.2-8 and 22.2-9.
- Exercises 22.3-1, 22.3-2 and 22.3-3.
- Material on final.
- Please look over the exercises in chapter 23 for the final.
Practicum
- Project 0:
-
Email me for your class account login and password. You will
be working on the lab machines. You can login remotely using
lee.cs.miami.edu. Your webpages are placed in the public_html
subdirectory of your directory and will appear at
http://web.cs.miami.edu/home/loginname, example:
http://web.cs.miami.edu/home/burt
- Project 1: due Wed., Oct. 5.
- 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, Oct 19.
- See RANDOMIZE-IN-PLACE algorithm in chapter 5.3, page 126 on
the third edition. Implement it. Start with an array of 12 cells,
and a button "Randomize" that applies the algorithm with each click.
- Project 3: due Wed., Nov 9.
- Implement perfect hashing. Accept as input a set of numbers.
- Randomly select primary and a collection of secondary hash
functions as required in the book.
- Select and reselect the primary until the sum of the squares
of the number of items per primary bucket is less than 4n.
- Select and reselect hash functions for each bucket until
there are no collisions, when the secondary hash table is
of size a square the bucket size.
- Display the parameters and an image of the hash table(s).
- Then show the lookup for an input value (successful or unsuccessful).
- Project 4: due Wed, Nov 30.
- 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.
Writing Credit
Three essays, each at least 1500 words.
- The origin of algorithms. A historical paper.
There is actually a book, History
of Algorithms ... that might guide you.
-
The need to break military codes drove forward the construction
of computers during World War II.
Among the early computers were
the Colossus
designed by Tommy
Flowers, to break German Navel Codes (Tunny)
and Turing's Bomb,
to break army and high command codes (Enigma).
These were really the first computers ever built.
there were code breaking computers.
- A science fiction short story about algorithms, computers, etc.
If not original, you can do an analysis of some Sci-Fi books like
The Diamond Age, or Snow Crash.
Please write me with your proposed topics, if you elect writing
credit. One paper must be done before the midterm, and the other
two before reading days.
References
Typography
- Lucida Sans:
A typeface by Charles Bigelow and
Kris Holmes.
This year's default font. For its lightness, given that the actual subject matter is heavy.
- Futura: On
Macs, set in Futura.
Futura is not a font for the web, because it features low readability.
Despite that, I used it as the default font in previous years.
- Verdana: IKEA
booted Futura for
Verdana font, creating
a scandal
in the design world. Probably my favorite font for this page, but I went with Lucida.
- Trebuchet MS:
Set in Trebuchet
MS, a font by Microsoft font designer Vincent_Connare.
This font was meant to be "Microsoft's Verdana". Every nation-state has a national font. When the Franks
invaded Gaul they brought with them the Frankish hand. And what else ... (I'm making this up, you know.)