22C:031 Algorithms

Syllabus, Announcements, Homeworks, Projects, Exams, Lecture Notes, Sample code, Online Resources

Announcements

• 8/20: Welcome to the class! This is the place where you will see annoucements, homework assignments, etc.
• 9/5: There is a change to the weighting of homeworks, projects, and exams in the final score computation: (a) each homework counts for 1% (6 of them are still 0.5%; 29% in total); (b) each project will be 4% instead of 6% (16% in total); (c) the final exam will be 30% but the midterm exam will remain to be 25% (55% in total).
• 9/21: Project 2 is due on 10/12/12.
• 9/27: Some bugs in Project2's java files have been fixed. Please use the new codes.
• 10/12: Project 3 is due on 11/02/12.
• 10/15: Answer keys of Midterm Exam is here. The distribution of the scores: >= 70: 6; 60-69: 6; 50-59: 5; <50: 6. Total number of students = 23.

Homeworks

• Homework 1 is due on 08/24/12 before or in class.
  Problem 1-5 on page 27. In addition to finding counterexamples for each algorithm, please also provide a description of the algorithms in pseudocode. Please also provide an algorithm (in pseudocode) based on exhaustive search to solve the knapsack problem (also called the subset-sum problem).
  sample solution
• Homework 2 is due on 08/27/12 before or in class.
  Problem 2-1 on page 57;
  Problem 2-19 on page 60.
  sample solution
• Homework 3 is due on 08/29/12 before or in class.
  Problem 2-25 on page 61;
  Problem 2-38 on page 63.
  sample solution
• Homework 4 is due on 08/31/12 before or in class.
  Problem 2-47 on page 64;
  Problem 3-1 on page 98. We also assume that the input string contains not only "(" and ")", but also "{", "}", "[", "]", and English letters.
  sample solution
• Homework 5 is due on 09/5/12 before or in class.
  Problem 3-3 on page 99.
  sample solution
• Homework 6 is due on 09/7/12 before or in class.
  Problem 3-7 on page 99;
  Problem 3-10 on page 100 (only for the best-fit heuristic).
  sample solution
• Homework 7 is due on 09/10/12 before or in class.
  Problem 3-13 on page 100;
  Problem 3-20 on page 101.
  sample solution
• Homework 8 is due on 09/12/12 before or in class.
  Problem 3-28 on page 102 (please design an O(n) algorithm);
  Problem 3-29 on page 102.
  sample solution
• Homework 9 is due on 09/14/12 before or in class.
  Problem 4-1 on page 139; How to divide the players into two teams as fairly as possible? (that is, the difference of the sums of the numerical ratings for each team becomes minimal.)
  sample solution
• Homework 10 is due on 09/17/12 before or in class.
  Problem 4-13 on page 140;
  Problem 4-17 on page 141.
  sample solution
• Homework 11 is due on 09/19/12 before or in class.
  Problem 4-21 on page 141;
  Problem 4-22 on page 142.
  sample solution
• Homework 12 is due on 09/21/12 before or in class.
  Problem 4-18 on page 141;
  Problem 4-26 on page 142.
  sample solution
• Homework 13 is due on 09/24/12 before or in class.
  Problem 5-2 on page 185;
  Problem 5-10 on page 186.
  sample solution
• Homework 14 is due on 09/26/12 before or in class.
  Problem 5-13 on page 187.
  Problem 5-14 on page 187.
  sample solution
• Homework 15 is due on 09/28/12 before or in class.
  Problem 5-5 on page 185 (the chromatic number of a graph is the minimal number of colors we can use to color each node so that no two adjacent nodes have the same color).
  Problem 5-16 on page 187.
  sample solution
• Homework 16 is due on 10/01/12 before or in class.
  Problem 5-21 on page 188;
  Problem 5-28 on page 189.
  sample solution
• Homework 17 is due on 10/03/12 before or in class.
  Problem 6-8 on page 226 (Your algorithm should run in O(n^2) receive full credit);
  Problem 6-9 on page 226.
  sample solution
• Homework 18 is due on 10/05/12 before or in class.
  Problem 5-19 on page 188;
  Problem 6-19 on page 228.
  sample solution
• Homework 19 is due on 10/15/12 before or in class.
  Problem 7-2 on page 270;
  Problem 7-5 on page 270 (no implementation is needed; you may describe your algorithm as an instance of the constraint satisfaction problem (CSP)).
  sample solution
• Homework 20 is due on 10/17/12 before or in class.
  Problem 7-8 on page 188 (see the comment for Problem 7-5);
  Problem 7-10 on page 228 (see the comment for Problem 7-5).
  sample solution
• Homework 21 is due on 10/19/12 before or in class.
  Problem 7-17 on page 271;
  Problem 7-18 on page 271.
  sample solution
• Homework 22 is due on 10/22/12 before or in class.
  We will practice local search on two small problems:
  (1) 5-queen problem: We want to place 5 queens on a 5x5 chessboard so that two queens attack each other. Let a configuration of the queens be represented by (c1, c2, c3, c4, c5), where c1 contains the row number of the queen in column 1, etc. The neighbors of (c1, c2, c3, c4, c5) are those configurations where one of the c values is changed. The objective function for the local search is the number of attacks among all queens. Please apply the local search to the initial configuration (1, 2, 3, 4, 5) and list all the configurations computed by the local search until a local minimum is found.
  (2) SAT problem: Give a set of propositional clauses on { x, y, z, u }, where "-" is negation and "|" is disjunction (i.e., OR):
  (x | y | z), (-x | y | u), (x | -z | u), (-y | -z | u), (x | -z | -u), (-y | z | u)
  Let (x, y, z, u) = (0, 0, 0, 0) be the initial assignment, where 0 is false (and 1 is true). The neighbors of an assignment is all the assignments obtained by flipping the value of one variable from { x, y, z, u }. If the objective function for the local search is the number of false clauses under the given assignment, please list all the assignments generated during the local search until a local minimum is found.
  sample solution
• Homework 23 is due on 10/24/12 before or in class.
  Problem 8-2 on page 310.
  sample solution
• Homework 24 is due on 10/26/12 before or in class.
  Problem 8-4 on page 311.
  sample solution
• Homework 25 is due on 10/29/12 before or in class.
  Problem 8-11 on page 312;
  Problem 8-12 on page 312.
  sample solution
• Homework 26 is due on 10/31/12 before or in class.
  Problem 8-13 on page 312.
  sample solution
• Homework 27 is due on 11/2/12 before or in class.
  Problem 8-21 on page 314.
  sample solution
• Homework 28 is due on 11/7/12 before or in class.
  Problem 9-1 on page 350;
  Problem 9-8 on page 351.
  sample solution
• Homework 29 is due on 11/9/12 before or in class.
  Problem 9-9 on page 351.
  sample solution
• Homework 30 is due on 11/12/12 before or in class
  Problem 9-10 on page 352;
  Problem 9-13 on page 352.
  sample solution
• Homework 31 is due on 11/14/12 before or in class.
  Problem 9-15 on page 352.
  sample solution
• Homework 32 is due on 11/16/12 before or in class.
  Problem 9-16 on page 353.
  sample solution
• Homework 33 is due on 11/28/12 before or in class.
  Problem 9-19 on page 353;
  Problem 9-23 on page 354.
  sample solution
• Homework 34 is due on 11/30/12 before or in class.
  Problem 9-25 on page 354;
  Problem 9-28 on page 354.
  sample solution

Compute Projects

• Project 1 is due on 09/21/12 on ICON.
  project specification
• Project 2 is due on 10/12/12 on ICON.
  project specification
• Project 3 is due on 11/02/12 on ICON.
  project specification
• Project 4 is due on 12/03/12 on ICON.
  project specification

Exams

• Midterm Exam is on 10/10/12 in class, 50 minutes.
  Answer keys
• Final Exam is in the final week, on 12/12/12, 8-10pm.

Lecture Notes

• Chapter 1: Introduction ch01Intro.pdf Introduction to Java Eclipse Java Tutorials Engineers vs Scientists
• Chapter 2: Algorithm Analysis ch02Analysis.pdf
• Chapter 3: Data Structures ch03DataStr.pdf ch03.3Dictionary.pdf ch03.7Hash.pdf redBlackTree.ppt
• Chapter 4: Sorting and Searching ch04Sort.pdf heapsort.ppt quicksort.ppt radixsort.ppt
• Chapter 5: Graph Traversal ch05Graph.pdf graphtraversal.ppt ch05SCC.ppt
• Chapter 6: Weighted GRaph Algorithms ch06WGraph.pdf ch06MST.ppt ch06UnionFind.ppt ch06allpairs.ppt ch06Network.ppt
• Chapter 7: Combinatorial Search ch07Backtrack.pdf ch07Constraint.ppt ch07localsearch.ppt
• Chapter 8: Dynamic Programming ch08Dynamic.pdf ch08Dynamic.ppt sample solutions
• Chapter 9: Intractable Problems ch09NP.pdf ch09Reduction.ppt ch09NPC.ppt
• Chapter 9.10: Approximate Algorithms ch09Approx.pdf ch09Approx2.ppt sum1.ppt

Sample code