cs272: Algorithms
|
||||||||||||||||||||||
Announcements
- Midterm Exam 4 is Friday, April 27. This will cover complexity
- P, NP, NP-Complete definitions and concepts
- Reductions
- NP-Complete proofs
- Common NP-Complete problems
The review sheet is here. - The final exam is Friday, May 4 at 2pm-4pm. It will be a comprehensive exam from the whole semester.
Schedule
| Week | Monday | Tuesday | Wednesday | Friday |
| Week 1 (1/15) | Lct: syllabus, intro | Lct: intro cont, coding theory, Huffman coding Read Chpt1 |
Lct: correctness | Lct: correctness |
| Week 2 (1/22) | MLK, no class | P1 due Read Ch2, Ch7 |
||
| Week 3 (1/29) | Book Assignment 1 Due | P2 due | ||
| Week 4 (2/5) | Programming Jam session, 6pm-9pm | Read Ch 15 | Midterm Exam 1 | |
| Week 5 (2/12) | ||||
| Week 6 (2/19) | Book2.pdf | Read Ch 3 | ||
| Week 7 (2/26) | Read Ch 4 | Book3.pdf DNA Word Wrapping |
||
| Week 8 (3/5) | Midterm 2 Book4.pdf |
|||
| (3/12) | Spring Break | Spring Break | Spring Break | Spring Break |
| Week 9 (3/19) | Ch 34, Ch1+2 in Garey Johnson | P6 due | ||
| Week 10 (3/26) | Book5 due | P7 due | ||
| Week 11 (4/2) | P8 due | |||
| Week 12 (4/9) | Midterm 3 | |||
| Week 13(4/16) | Chpt 35 in text Chpt 3 in G&J |
|||
| Week 14 (4/23) | Book6.pdf due | P9 due | Midterm 4 | |
| Week 15 (4/30) | last day of classes | Final Exam 2pm-4pm |
Examples and Downloads
- syllabus.
- Assignment1: Huffman coding. Due on Friday, January 26
- mystery.txt: A plain-text file used for Assignment 1 to create your library.
- secret.txt: An encoded message for Assignment 1, decode it and figure out what it is.
- Book Assignment 1: Due Wednesday, January 31. Please type in latex.
- Problem 2-2 (parts b,c only) on page 38: prove the correctness of bubble sort.
- Problem 2-3 (parts a through d) on page 39: prove correctness of Horner's rule.
- Find a loop invariant and prove the correctness of Heap Sort (page 136). You can assume the correctness of BUILD-HEAP (the proof is given in the text).
- Bonus (not required): 2.3-7 on page 37. See if you can figure out the algorithm by yourself. Can you prove the correctness?
- Assignment2: Sorting. Due on Friday, February 2.
- sorting.tar.gz (for Assignment2).
- Divide and Conquer Programming Data
- Book Assignment 2: Due Monday, February 19. Please type in latex.
BookAssignment2.pdf
- Use the matrix-chain multiply dynamic programming algorithm to find the optimal way to multiply 5 matrices with the following dimensions: A1 is 3x5, A2 is 5x4, A3 is 4x2, A4 is 2x6, A5 is 6x3. Compute the minimal number of multiplications, show the optimal parenthization, and show the table you constructed to solve the problem.
- The brute-force way to solve the matrix-chain multiplication problem is simply
to enumerate all the possible different ways to multiply the matrices and keep track
of the parenthization with the smallest number of multiplications. But this is
very inefficient.
For a matrix-chain multiply problem with n matrices, how many different ways are there to multiply them? Build a table showing the number of different ways for values of n = 1..10. Construct a recurrence relation that shows in general how many different ways there are to multiply the matrices for n matrices.
- Bonus: For the problem above, give a closed-form expression for the recurrence relation. Hint: do not try to solve this on your own using the techniques we learned in class -- it is too hard. This is a research problem, you'll have to hit the books to find the answer.
- Selection Sort Analysis (corrected).
- Book4.pdf written assignment and the source tex file is here. Due Friday March 9.
- Book Assignment 5: Due Tuesday, March 27. Please type in latex. 4.2: 1-2, 4.3: 1-4.
- Programming Assignment 7 is due Friday, March 30 by midnight. SATtest1.txt and SATtest2.txt are two sample test files.
- Programming Assignment 8 is due Friday, April 6 by midnight. eil5.txt is a sample test file.
- P9 due on Wednesday, April 25.
p1.txt is an example input file. - Book6.pdf written assignment is due on Tuesday, April 24 at the start of class.