CS U690 (Algorithms and Data)

Instructor: Gene Cooperman
Spring, 2009
There is now a summary of the corrections and hints for the take-home final exam given out in class on Monday.

The final exam is now ready both online (/course/csu690/final-csu690.pdf) and in printed form to be handed out in class on Thursday, April 9.

I will answer questions about the exam in-class. The final exam will be due by Wednesday at 6:00 p.m. at my office (336-WVH). We will still hold class on Monday at 9:15 as usual. We will use that time for me to answer general questions about the exam and the related material.

For hw1, there were 50 points possible, and 35/50 is scaled to 100%.
For hw2, there were 85 points possible, and 50/85 is scaled to 100%.
For hw3, there were 60 points possible, and 45/60 is scaled to 100%.
For hw4, there were 60 points possible, and 30/60 is scaled to 100%.
For hw5, there were 60 points possible, and 50/50 is scaled to 100%.
For hw6, there were 60 points possible, and 60/60 is scaled to 100%.

The homework is scaled this way so that each homework can include problems of varied difficulty, but each student should look at all problems. Skipping the "extra credit" problems is not possible. Please check back here for the scaling of later homeworks.

The course syllabus is at /course/csu690/syllabus.pdf. It is available both via the Web and via the CCIS Linux/UNIX filesystem.

Please look in the course directory for the syllabus and latest assignments.

Encyclopedic Reference of Algorithms and Data Structures:

Topics discussed in course:

(Please note that the online notes are often incomplete or simply informal examples. They are intended only as a quick entry into the the ideas of the text. Please also read the textbook for a complete and rigorous proof.)
  1. RSA cryptography (public-key cryptography) (Chapters 0 and 1)
  2. Hash functions (Chapters 1.5.0 - 1.5.1)
  3. Fast Integer Multiplication (Chapter 2.1)
  4. Fast Polynomial Multiplication (Chapter 2.6)
  5. Complexity, O(), and Recurrence Relations (Chapter 2.2)
  6. Strongly Connected Components (Chapter 3.4.2)
  7. Best-First Search, Priority queues, and Binary heaps (and other Data Structures) (Chapter 4)
  8. Union-Find (Chapter 5.1.4)
  9. Huffman Encoding (Chapter 5.2; There is no web page currently. In some future year, I will add one.)
  10. Dynamic Programming (Chapter 6)
  11. Binary Decision Diagrams (BDDs) (not in textbook)