CS 282 DESIGN & ANALYSIS OF EFFICIENT ALGORITHMS

Fall 2012

Office Hours:

Henry Kautz Friday 11:00-12noon CSB 709
Tim Kopp Monday 1:00-3:00pm CSB 724
Undergrad TAs Tuesday 5:00-6:00pm Hylan 301

Facebook Discussion Group: https://www.facebook.com/groups/159217487617318/

Textbook: [DPV] = Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani (a draft is available online), 2006.
Note: this registrar's schedule listed a different text (Cormen, Leiserson, Rivest, & Stein); you may return that text or keep it for general reference.

Other resources/recommended reading (all on a 2 hour reserve in the library):
Introduction to Algorithms (3rd edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2009
Algorithm Design, J. Kleinberg and E. Tardos, 2005.
The Design and Analysis of Algorithms, D. Kozen, 1991.
The Design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.
Algorithms Algorithms, R. Johnsonbaugh, M. Schaefer, 2003.
How to Think About Algorithms Algorithms, J. Edmonds, 2008.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher, E. Upfal, 2005.
Randomized Algorithms, R. Motwani, P. Raghavan, 1995.
Approximation Algorithms, V. Vazirani, 2004.

Prerequisites: CSC172 OR MTH172

Clusters: N1CSC008, N1CSC011, N4CSC011

Description: How does one design programs and ascertain their efficiency? Divide-and-conquer techniques, string processing, graph algorithms, mathematical algorithms. Advanced data structures such as balanced tree schemes. Introduction to NP-completeness and intractable combinatorial search, optimization, and decision problems.

Grading: Your final grade will be based on 1/2 exams (in class) and 1/2 assignments. Students requiring accomodations for testing or classroom participation should notify the instructor at the start of the semester, and suitable arrangements will be made. Assignment due dates and quizzes are not intended to be scheduled on religious holidays; if one is scheduled in error, please notify the instructor so it can be rescheduled. Make-up exams will be allowed only for students who have made previous arrangements (at least two days before the exam) with the instructor due to a conflict with a university sponsored activity, or who can provide a medical excuse signed by a doctor.

Homework Rules: You may work on your own or with other students in the class on the homework problems, but you must each write up your solutions separately, without any written aid. In other words, do not write up your final solution while actively collaborating, and do not refer to any notes you made while collaborating. Your assignment must clearly indicate the names of the other students with whom you worked. Assignments should be turned in in printed form. Assignments that do not require creating an executable program should be typed or neatly writing using block letters (not cursive); points will be deducted for assignments that are hard to read.

Assignments can be turned in at the class before the due date, or in CSB 708 (Melissa Singkhamsack's office, administrative assistant to Prof. Kautz). Late assignments will be accepted only under the following conditions:

Being unable to complete an assignment on time for reasons such as vacation travel or non-university activies is not an acceptable excuse. The grade for late assignments will be reduced by 20% per day late.

Academic Honesty: Turning in work that was copied from another person, the internet, or any other source without explicit citation of the original creator(s) is plagerism. All cases of plagerism will be referred to the university Council on Academic Honesty. Punishments for plagerism include failing the class and expulsion from the university.

Schedule: There is no class on Tuesday 8 October (Fall Break) and Thursday 28 November (Thanksgiving Break). There is no final exam.

Calendar

Tuesday Thursday Friday
Sept 3 Topic: Big-O complexity. Reading: [DPV Ch 0 and Sec. 1.2.3] Lecture 01. Algorithms. Asymptotic complexity. Fibonacci numbers. Exponential growth. Sept 5 Lecture 02. Big O notation. Analyzing nested iterations. Fixed vs infinite precision arithmetic. Euclid's algorithm for greatest common divisor. Assignment 1 posted.  
Sept 10 Topic: Divide-and-conquer algorithms. Reading: [DPV Ch 2]. Lecture 03. Infinite precision multiplication. Divide-and-conquer algorithms. Gauss's multiplication trick. Master theorem for recurrence relations. Sept 12 Lecture 04. Randomized divide-and-conquer algorithm for selection. Computing expected values. Randomized complexity analysis.

Sept 13 Assign 1 Due

Sept 17 Topic: Core graph algorithms Reading: [DVP Ch 3-4]. Lecture 05. Representing graphs. Depth and breadth first search. Connected components. Sept 19 Exam 1. Assignment 2 posted.  
Sept 24 Lecture 06. Strongly connected components. Sept 26 Lecture 07. Shortest paths in graphs. Breadth first search. Dijkstra's algorithm. Bellman-Ford algorithm.  
Oct 1 Topic: Greedy algorithms. Reading: [DVP Ch 5]. Lecture 08. Minimum spannning trees. Disjoint sets (union / find). Path compression. Oct 3 Topic: Lecture 09: Huffman Coding [DPV Sec. 5.2]. Oct 4 Assign 2 Due
Oct 8 Break Oct 10 Exam 2. Assignment 3 posted.  
Oct 15 Dynamic programming. Reading: [DVP Ch 6] . Lecture 10. Longest increasing subsequences. Edit distance. Oct 17 Lecture 11. Knapsack.  
Oct 22 Lecture 12. Chain matrix multiplication. All pairs shortest paths. Oct 25 Lecture 13. Memoization. Oct 25 Assign 3 Due
Oct 29 Topic: Linear programming Reading: [DVP Ch 7]. Lecture 14. Linear programming and reductions. Oct 31 Exam 3. Assignment 4 posted.  
Nov 5 Lecture 15. Flows in networks. Using lp_solve, a free solver for linear programming, integer programming, and mixed integer-linear programming. Precompiled binaries for Windows, Linux, and Mac OSX can be downloaded. The Windows version includes a GUI as well as command-line interface. Nov 7 Class cancelled.  
Nov 12 Lecture 16. Duality. Nov 14 Lecture 17. Simplex Algorithm Nov 15 Assign 4 Due
Nov 19Introduction to NP Completeness. Reading: [DVP Ch 8]. Lecture 18. Search problems. Examples of intractable problems. Reductions. Nov 21 Exam 4.  
Nov 26 Lecture 19: NP Completeness continued Nov 28 Thanksgiving Break  

Dec 3 Lecture 20: Practice with reductions and NP-completeness proof for Hamiltonian Circuit.

Assign 5 posted. This assignment will be discussed in the workshops but not turned in.

Dec 5 Lecture 21: Quantum Computing

 
Dec 10 Quantum Computing continued Dec 12 Exam 5