CSE 101, Winter 2001                     Final Solutions ps, pdf.

INSTRUCTOR AND TEACHING ASSISTANTS.

• Instructor: Andrew B. Kahng, abk@ucsd.edu, 3802 AP&M, tel. 858-822-4884 (office), 858-353-0550 (cell). Office Hours: MW noon-2pm, TuTh 8:30-9:30pm, and by appointment. CSE 101 students have priority during the M noon-1pm and TuTh office hours.
• Teaching Assistants: Joe Drish, Victor Gidofalvi, Eric Hall, Cynthia Sheng.
• Contact Information:



Name	Email	Office Hours	Office Location
Andrew B. Kahng	abk@ucsd.edu	send email if you cannot make OH's above	APM 3802
Joe Drish	jdrish@cs	by appointment	n.a.
Gyozo (Victor) Gidofalvi	gyozo@cs	Wednesday / Thursdays 1pm-2pm (-3pm if necessary)	APM 3349A / APM 2331
Xi (Cynthia) Sheng	xsheng@cs	Cancelled from Mar 07
Eric M. Hall	emhall@cs	Wednesday 10am-11am	APM 3337A

AFTER THIS FRIDAY, JANUARY 25. THE FRIDAY SECTION IS MOVED TUESDAY 11:15-12:05, WLH 2111. The reason for this move is to allow students more time to review the homework to prepare questions for section.

REQUIRED TEXTBOOK. Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms", SECOND EDITION.

USEFUL LINKS. This page contains useful links for this course. This page contains even more useful links for the course.

DISCUSSION BOARD ON THE WEB. There is a Discus web-based message board for questions that are of interest to other students. This board will be shut down, or postings will be moderated, if inappropriate use occurs. "Inappropriate" includes any distribution of homework solutions, and any offensive material.

THEMES. The goal is for students to acquire a toolkit/mindset for design (and analysis) of practical algorithms and heuristics for useful applications. The class will be built around three fundamental elements: (1) toolkits including solution of recurrences, use of loop invariants, elementary discrete mathematics, reduction, and problem-solving patterns; (2) classic problems (i.e., applications) including sorting, shortest paths, arithmetic, string processing, and computational geometry; and (3) algorithm design paradigms including Divide-and-Conquer (DQ), Dynamic Programming (DP), Greed, Implicit Enumeration (e.g., Branch-and-Bound), and Meta-Heuristic. Where possible, we will look for interesting problem formulations from practical applications.

IMPORTANT LOGISTICS.

• There are now FOUR discussion sections:
• Mon 2:30PM - 3:20PM, SOLIS 104 (??? seats) (Eric Hall)
• Tue 11:15 - 12:05, WLH 2111 (Joe Drish)
• Wed 09:05AM - 09:55AM, WLH 2204 (76 seats) (Eric Hall)
• Wed 11:15AM - 12:05PM, CENTR 212 (146 seats) (Joe Drish)
• The first week will have only the Friday discussion section; for the first week, there is no specific material that will be developed in discussion.
• Discussion sections may develop material that is not covered in lecture (e.g., solution of recurrence relations, structure of induction proofs, etc.).
• All material covered in lecture, in the assigned reading, in the homework, and in discussion sections is fair game for exams. Discussion sections will be aligned to achieve the same coverage of material.
• Two in-class QUIZZES will each be worth about the same as a homework assignment (if there are six homeworks and two quizzes, then each quiz is 5% of your total grade). The quizzes will be on the Thursdays of 3rd week and 8th week, and will be at the beginning of class.
• Prerequisites include: CSE 12, CSE 21 or Math 15B, CSE 100 or Math 176. Other restrictions: (1) Majors only; (2) credit not offered for both Math 188 and CSE 101; (3) equivalent to Math 188.
• Homeworks may involve programming and/or web download / compilation / execution to obtain desired answers. There will not be any substantive programming assignment, however.

SYLLABUS AND SCHEDULE. This will become more refined, and is subject to change, as we go through the quarter.

• Week 1, January 8, 10. Introduction. What is an algorithm? Example algorithm analysis (e.g., recurrences) and problem-solving patterns (e.g., establish notation, study small and/or limiting cases, try to reduce to a known problem, check whether all information was used, attempt to generalize, ...). Criteria for algorithms. Asymptotic growth. Beginning of "A Sorting Excursion" (lower bounds on worst and average cases under the comparison model; practical issues; simple methods; closing the O(n log n) gap). READING: CLRS Chapters 1-4, 6, 7. It will turn out eventually (but not immediately) useful to read 5.1, 5.2 and 5.4.4. The sorting lower bounds are given in CLRS 8.1. DISCUSSION SECTIONS: NONE, DUE TO ROOM LOGISTICS.
• Week 2, January 15, 17. Continuation of "A Sorting Excursion" (example of randomized analysis of Quicksort). Selection. The D/Q framework and the "Master Method" of solving certain recurrences. Will have seen general solution given characteristic polynomial of recurrence, shift-cancel and unrolling techniques. READING: CLRS Chapters 8, 9. The "Master Method" is in CLRS 4.3. "Constructive induction", used in analysis of linear-time selection, is noted as "strengthening the induction hypothesis" in the "Subtleties" part of CLRS 4.1. DISCUSSION SECTIONS: Review of how to solve recurrences, and how to form and present induction proofs. Pointer to other handouts on the web, on basics of set theory and graph theory.
• Week 3, January 22, 24. Divide and Conquer for various applications. Arithmetic (multiplying large numbers, multiplying matrices). Computational geometry (convex hull, closest pair). READING: CLRS 28.2, Problem 30-1, Chapter 33 (especially 33.3-4)
• Week 4, January 29, 31. The Greedy Method. Single-processor job scheduling. Huffman codes. The Minimum Spanning Tree (MST) problem, Prim's and Kruskal's algorithms, and use of data structures in efficient implementation (union-find / union-by-rank). READING: CLRS Chapters 16, 23, 21.
• Week 5, February 5, 7. Graph traversal and Topological Sorting (a prelude to Shortest Paths). IN-CLASS MIDTERM ON FEBRUARY 7TH. READING: CLRS Chapter 22.
• Week 6, February 12, 14. Dynamic Programming and Shortest Paths. Principle of optimality; principle of successive approximation and relaxation. Single-source shortest paths (Dijkstra; a Prim-Dijkstra tradeoff; Bellman-Ford). All-pairs shortest paths (Floyd-Warshall) and similarity to other formulations (transitive closure, Gaussian elimination, ...). Matrix Chain Product. Knapsack. READING: CLRS Chapters 15, 24, 25.
• Week 7, February 19, 21. Continuation of Week 6 material.
• Week 8, February 26, 28. Implicit Enumeration. What is meant by "intractability" (i.e., "hardness") of a problem. Examples of hard problems. Branch-and-Bound for N-queens, possibly game tree (alpha-beta pruning). READING: HANDOUTS ON WEB, plus skim CLRS Chapters 34, 35. This week's material does not rely greatly on the textbook.
• Week 9, March 5, 7. Approximation algorithms. Geometric TSP (MST and Christofides algorithms). Vertex cover. On-line bin-packing (performance ratio of Next-Fit). READING: CLRS Chapter 35.
• Week 10, March 12, 14. NP-Completeness. Succinct proofs / certificates. NP-completeness. Reduction. Examples of NP-complete problems, and NP-completeness proofs. PRE-FINAL EXAM REVIEW OF COURSE MATERIAL AS FEASIBLE. READING: CLRS Chapter 34.

• HOMEWORK 1. Assigned: January 10th. Due: January 17th at end of class. There will be a collection box in the classroom.
• Question 1. CLRS 4.1.6.
• Question 2. CLRS 4.2.4.
• Question 3. (a) CLRS 4.3-1. (b) CLRS 4.3-2. (c) CLRS 4.3-3.
• Question 4. CLRS 4-2.
• Question 5. CLRS 4-6.
• Question 6. Prove by mathematical induction that the sum of the cubes of the first n positive integers is equal to the square of the sum of these integers.
• Question 7. Explain in at most two sentences what is wrong, if anything, with the following induction proof (from the Brassard/Bratley textbook).
• Claim: All horses are the same color.
• Proof: We prove this by showing that any set of horses contains only horses of a single color; in particular, this is true of the set of all horses. Let H be an arbitrary set of horses. We show by induction on n, the number of horses in H, that all horses in H are the same color.
• Basis: The cases n = 0 and n = 1 are immediately seen to be true.
• Induction step: Consider any number n of horses in H. Call these horses h1, h2, h3, ..., hn. By the induction hypothesis, any set of n-1 horses contains only horses of a single color. Consider the set H1 obtained by removing horse h1 from H, and the set H2 obtained by removing horse h2 from H. There are n-1 horses in each of these sets, hence the induction hypothesis applies to each: H1 has all horses of a single color (say, c1), and H2 has all horses of a single color (say, c2). But, since horse hn is common to both sets H1 and H2, the two colors c1 and c2 must be the same. This completes the induction step.
• Question 8 (problem-solving). "The Depot Problem."
• Your task is to drive a car once (completely) around a circular track, somewhere in the desert. To drive around the track requires 30 gallons of gasoline. The car's gas tank has capacity 30 gallons. You are allowed to start at any point along the track.
• Your "adversary" empties your gas tank, then takes exactly 30 gallons of gasoline and distributes the gasoline in an arbitrary manner among various "depots" along the track. There are no restrictions on how many depots there are, or how closely or widely apart they are spaced.
• Your adversary then taunts you, but offers to tow your car to wherever you want along the track (where you can start your task of driving).
• Prove that there is always some depot from which you can start your drive, such that you will be able to drive completely around the track without running out of gasoline.

• HOMEWORK 2. Assigned: January 20th. Due: January 31st at end of class.
• Question 1. Heap Data Structures. Consider a min-heap storing the values 1, 2, 3, ..., 15. Answer each of the following questions, and justify your answers.
(a) Where in the heap can the value 1 possibly go?
(b) Which values can possibly be stored in entry A[2]?
(c) Where in the heap can the value 15 possibly go?
(d) Where in the heap can the value 6 possibly go?
• Question 2. Binary Tree Isomorphism. Two binary trees are isomorphic if there is a one-to-one correspondence between their vertices, with an edge between two vertices of one graph if and only if there is an edge between the two corresponding vertices in the other graph. Give as efficient as possible an algorithm to test whether two binary trees are isomorphic. Justify the correctness of your algorithm, and analyze its runtime.
• Question 3. CLRS 9.3-8 (2nd edition pg. 193).
• Question 4. DQ Skylines. A city's n buildings are rectangles placed on top of the x-axis, with each building specified as Bi = (si, fi, hi) for 1<=i<=n. Here, (si, fi, hi) denotes a building with left edge at x = si, right edge at x = fi, and height hi. When seen from a distance, the city's buildings define the city's skyline, which at each x-coordinate has height (i.e., y-coordinate) equal to the height of the tallest building Bi with si <= x <= fi. Give a DQ algorithm that computes the city's skyline from the list of buildings. (The skyline is a series of points connected by line segments.)
• Question 5. CLRS 7-3 (2nd edition pg. 161).
• Question 6. DQ Maximal Elements. Let S be a set of n points in the XY-plane. A point p = (xp,yp) is said to dominate another point q = (xq,yq) if xp >= xq and yp >= yq. (For example, (2,1) dominates (1,1). But, neither (2,1) nor (1,2) dominate each other.) A point p is a maximal element of S if there does not exist q in S such that p != q and q dominates p. Give an O(n log n) time divide-and-conquer algorithm that determines the set of all maximal elements in S.
• Question 7. CLRS 8-4 (2nd edition pg. 179).
• HOMEWORK 3. Assigned: January 31st. Due: February 14th at end of class.
• Question 1. CLRS 16.1-3 (2nd edition pg. 379).
• Question 2. Consider the problem of making change for n cents. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels and pennies. Prove that your algorithm yields an optimal solution, in that it always uses the fewest possible coins.
• Question 3.You are given a set of items to be packed into uniform-height bins. All the items have the same width and length (the same as the width and lenght of the bins), but they have different heights. The heights are given in a list H=(h1,...,hn). Each item height is at most the bin height, e.g., if the bin height is = 1 then O < hi <= 1 for all i. The goal is to pack the items into bins using as few bins as possible. Consider the following greedy, on-line algorithm for this problem:

  FirstFit (H):
        for i = 1 to n do
                Place item i in the first (i.e., lowest-index) bin that has enough room for H[i];
  end FirstFit.
  

  Give an example to show that this algorithm does not always use the optimal number of bins.
  
  Extra Credit: Consider the following greedy off-line algorithm:

  FirstFitDecreasing (H):
        Sort H so that the items are ordered from largest to smallest;
        for i = 1 to n do
                Find the first (i.e., lowest-index) bin that has enough room for H[i];
                Place item i in this bin;
  end FirstFitDecreasing.
  

  Give an example to show that this algorithm does not always use the optimal number of bins.
• Question 4. CLRS 22.4-3 (2nd edition pg. 552).
• Question 5. CLRS 23.1-7 (2nd edition pg. 566).
• Question 6. CLRS 23.2-8 (2nd edition pg. 574).
• Question 7. You are given a set S containing n numbers, and a number x.
  • a. Design an algorithm to determine whether there are two elements of S whose sum is exactly x. The algorithm should run in time O(n lg n).
  • b. Suppose now that the set S is given in a sorted order. Design an algorithm to solve this problem in time O(n).
• HOMEWORK 4. Assigned: February 15th. Due: TUESDAY, February 26th at end of class.
• Question 1. CLRS 24.3-4 (2nd edition page 600).
• Question 2.
  • (a) Given a set of points in the Euclidean plane, describe an algorithm for computing the maximum-weight spanning tree over the point set. The weight of an edge is the (Euclidean) distance between its endpoints.
  • (b) Given two sets of points P and Q, their split, denoted split(P,Q), is the minimum distance between any pair of points p, q where p is an element of P, and q is an element of Q. Given a set of points in the Euclidean plane, describe an algorithm for dividing the points into two subsets P and Q, such that split(P,Q) is maximized. Hint: the minimum-weight spanning tree may help...
  • (c) NEW, EXTRA CREDIT (half-question worth). Given a set of points P its diameter, denoted diam(P), is the maximum distance between any pair of points p1, p2 in P. Given a set of points in the Euclidean plane, describe an algorithm for dividing the points into two subsets P and Q, such that max(diam(P), diam(Q)) is minimized. Hint: the maximum-weight spanning tree may help...
• Question 3. A ski rental agency has m pairs of skis. The height of the i-th pair of skis is Si. There are n skiers who wish to rent skis. The height of the i-th skier is Hi. Each skier wishes to obtain a pair of skis whose height matches his own height as closely as possible. Describe an efficient algorithm to assign skis to skiers so that the sum of the absolute differences of the heights of each skier and his skis is minimized. Analyze the running time of your algorithm. Extra Credit (worth one question): Describe an efficient algorithm to assign skis to skiers, such that the maximum absolute difference, over all skiers, of the heights of the skier and his skis is minimized.
• Question 4. You wish to construct the tallest tower possible out of building blocks. You are given n types of blocks, and an unlimited supply of blocks of each type. The i-th block type is a rectangular solid with linear dimensions {xi, yi, zi}. A block may be placed on any of its sides. Thus, any two of its three dimensions determine the dimensions of a base, and the remaining dimension determines the height. The rule for building the tower is that in order to put one block on top of another, the base dimensions of the upper block must both be strictly smaller than the corresponding base dimensions of the lower block. (For example: you can put a 4x6 base block on top of a 5x8 base block; you cannot put a 4x6 base block on top of a 5x5 base block; you cannot put a 4x6 base block on top of a 4x6 base block.) Design an efficient algorithm to determine the height of the tallest tower that can be built.
• Question 5. You need to drive along a highway, using rental cars. There are n rental car agencies 1, 2, ..., n along the highway. At any of the agencies, you can rent a car that can be returned at any other agency down the road. You cannot backtrack, i.e., you can drive only in one direction along the highway. So, a car rented at agency i can be returned only at some agency j > i. For each pair of agencies i, j with j > i, the cost of the i-to-j car rental is known.
  • (a) Give an O(n^3) time dynamic programming algorithm that takes the matrix of i-to-j rental costs as input, and returns the optimal sequence of rentals that takes you from location 1 to location n. (I.e., you must rent your first car at 1, and you must return your last car at n.) Justify the time complexity bound.
  • (b) The greedy algorithm for this driving/renting problem might always choose the lowest-cost rental from the current location. I.e., at location i, always choose the i-to-j rental with minimum cost. Give (and explain) a counterexample showing that the greedy choice property does not hold.
• Question 6. The algorithms for finding shortest paths discussed in class break ties arbitrarily. (Or, tie-breaking was not discussed.) Describe how to modify these algorithms such that, if there are several different paths of the same minimum length, the one with the fewest edges will be chosen. Extra Credit (one question's worth): Given an edge-weighted graph G = (V,E), two identified vertices s and t, and a positive integer k that is less than or equal to |V|. Describe an efficient algorithm that finds the shortest path from s to t that contains exactly k edges.
• Question 7. Given a vertex-weighted graph G = (V,E), and an identified source vertex s. Every vertex v_i in the graph has an associated positive cost, c(v_i). The cost of a path (s, v_1, v_2, ..., v_k, t) is the sum of the costs c(v_1) + c(v_2) + ... + c(v_k). (In other words, you are not charged for the costs of the starting and ending vertices of the path.) Design an efficient algorithm to find the minimum-cost paths from s to all other vertices, and analyze the running time of your algorithm.

• Question 1. Best-first search is a general search algorithm that always considers (expands) the estimated best partial solution. This is typically implemented with a priority queue. March 1, 11:20pm: Please see DISCUS for details of Best-First Search. One well-known best-first search algorithm estimates the cost of a partial solution as the cost of getting to the node that represents that partial solution, plus an estimate of the cost of getting from that partial solution to a complete solution ("the goal"). More formally:
  • g(n) = the cost of path from the initial state to state(n)
  • h(n) = estimated cost of the cheapest path from the state represented by the node n to a goal state
  • f(n) = g(n) + h(n) = estimated cost of the cheapest solution through n
  Given a grid graph G representing the 2-dimensional Manhattan grid (i.e., integer lattice) with all edges having unit cost, we wish to find the shortest path from node s to node t. Let g(n) be the path length from node s to node n, and let h(n) be the Manhattan distance between node n and t, where the Manhattan distance between nodes a and b is defined as d(a,b) = |x_a - x_b| + |y_a - y_b|.
  • (a) Show with contour lines the order in which nodes in G are expanded by the algorithm. Justify your drawing with a few sentences.
  • (b) Give an estimate of how many nodes are expanded by the algorithm as a function of whatever parameters you feel appropriate (e.g., d(a,b), |x_a - x_b|, |y_a - y_b|, etc.).
  • (c) Does your estimate in (b) depend on how the priority queue is implemented? Describe an implementation of the priority queue that allows the search algorithm to reach t while expanding the minimum possible number of nodes.
• Question 2. Prove the optimality of the above algorithm, given the assumptions that (1) the h function is admissible, and that (2) the f = g + h function is monotonic. Intuitively, admissible means acceptable or reasonable. Formally, h(n) is admissible if it is always true that:

  h(n) =  estimated cost of cheapest path from state(n) to goal
       <= actual cost of cheapest path from state(n) to goal
  

• Question 3. Imagine that there are obstacles in the search space, i.e., vertices in G that cannot be visited. (Such obstacles might represent real obstacles, e.g., in a VLSI chip routing problem.)
  • (a) Draw contour lines as in Question 1 to represent the order of nodes visited or expanded by the algorithm in Question 1, when an obstacle is placed in the close vicinity of s. To be specific, suppose that s is at (0,0); and that the obstacle consists of all vertices on the line segments (-3,5) to (5,5), and (5,-3) to (5,5).
  • (b) Draw contour lines as in Question 1 to represent the order of nodes visited or expanded by the algorithm in Question 1 when an obstacle is placed in the close vicinity of t. Specifically, assume a symmetric situation to that given in part (a).
• Question 4. Suppose we simultaneously run the above algorithm starting from s (to find the shortest path to t), and starting from t (to find the shortest path to s).
  • (a) What do the contour lines look like? Do you think that, in general, this "bi-directional" approach is more efficient than the original "uni-directional" approach? Explain your thinking.
  • (b) Is it true that when the two expanding wave fronts first meet, you have found a shortest path from s to t? If yes, justify your answer. If no, then under what condition have we actually found a shortest s-t path?
• Question 5. Given the following branch-and-bound tree, where the numbers at the nodes represent the incremental costs of visiting that node (i.e., growing the partial solution vector), and the leaves represent complete solutions. Trace the execution sequence of depth-first branch-and-bound (DFBB) by showing the sequence of visited nodes.

                      0
                    / | \
                   /  |  \
                  /   |   \
                 2   12    3
                / \       / \
               4   7     1   3
              / \   \     \   \
             1   6   1     1   3
  

• Question 1. HAMILTONIAN PATH - HAMILTONIAN CYCLE
  • Definitions:

    Hamiltonian Path

    A Hamiltonian path in an undirected graph G = (V,E) is a path of |V| - 1 edges that visits each vertex (including the start and end vertices) exactly once.

    HAM-PATH(G)

    Given G = (V,E), does G contain a Hamiltonian path?

    Hamiltonian cycle

    A Hamiltonian cycle in an undirected graph G = (V,E) is a cycle of |V| edges that starts at some vertex v, visits every other vertex exactly once, and returns to v.

    HAM-CYCLE(G)

    Given G = (V,E), does G contain a Hamiltonian cycle?

  • (a) Given that HAM-PATH is NP-Complete, prove that HAM-CYCLE is NP-Complete.
  • (b) Given that HAM-CYCLE is NP-Complete, prove that HAM-PATH is NP-Complete.
  
  NOTE: To prove that a problem A is NP-Complete, one must:
  1. give a polynomial-time verifier for A,
  2. give a polynomial-time reduction of another problem B to A, where B is NP-Complete.
• Question 2. Approximate TSP: CLRS 35.2-3 (2nd edition pg. 1033)
• Question 3. 2-CNF-SAT: CLRS 34.4-7 (2nd edition pg. 1003)
• Question 4. Consider the Bin packing problem as defined in Question 3 of Homework 3.
  • Give a tight approximation ratio for the NextFit algorithm, described below.

    NextFit (H):
    	current_bin = 1;
    	for i = 1 to n do
    		Place item i in current_bin if it has enough room,
    		otherwise increment current_bin by 1 and place item i in
    		   this new bin.
    end NextFit
    

  Use the definition of approximation ratio given in CLRS on pg. 1022.
• Question 5. INDEPENDENT SET: CLRS 34-1 (a)-(c) (2nd edition pg. 1018)

PRACTICE PROBLEMS.

• Problem 1. CLRS 9.3-7(2nd edition pg. 193)

• Problem 2. CLRS 8.3-2(2nd edition pg. 173)

• Problem 3. CLRS 8.3-4(2nd edition pg. 173)

• Problem 4. CLRS 8.2-4(2nd edition pg. 170)

Practice problems solutions: PDF

LECTURE NOTES. here on the class web page. Eventually (perhaps after first week), the notes will be posted at least a day in advance of the class. (January 10: I have had requests for 4-up PDF's. PowerPoint does not "print" handouts in this form; you can use Distiller and any number of "green" postscript manipulation utilities to construct a 4-up printout.)

• Unified (first and second sets of notes, updated at end of second lecture) set of notes, covering slightly past the second lecture (we went through slide 48 on 1/10): PowerPoint source , PDF , or PDF (printed 6-up).
• Third set of notes: PowerPoint source , PDF , or PDF (printed 6-up).
• Fourth set of notes (we went through most of this, up through the randomized analysis of QSort average-case complexity, during Lecture 4): PowerPoint source , PDF , or PDF (printed 6-up).
• Fifth set of notes: PowerPoint source , PDF, or PDF (printed 6-up).
• Sixth set of notes (Greed, and some pieces of DP - posted February 28 at 12:20pm - UPDATED on March 12 at 6:40pm): PowerPoint source , PDF, or PDF (printed 6-up).
• Seventh set of notes (posted February 19th; see sixth set for MCP and LCS examples): PowerPoint source , PDF, or PDF (printed 6-up).
• Eighth set of notes (Branch-and-Bound, posted February 28th): PowerPoint source , PDF, or PDF (printed 6-up).
• Ninth set of notes (NP-Completeness, posted March 12 at 6:40pm (btw, see Manber's text for the same tree of NP-Completeness reductions)): PowerPoint source , PDF, or PDF (printed 6-up).
• Tenth set of notes (Approximation), posted March 20 at 1:40am: PowerPoint source , PDF, or PDF (printed 6-up).

• Homework 1 Solutions 1,3,4 , 2 , 5 , 6,7,8 .
• Here is the grading criteria we have used for homework 1.
• Here is the grading criteria and solution set for quiz 1.
• Homework 2 Solutions.
• Homework 2 grading criteria.
• Homework 3 Solutions.
• Homework 3 grading criteria.
• Homework 4 Solutions.
• Homework 4 grading criteria.
• Homework 5 Solutions.
• Homework 6 Solutions.

SECTION NOTES.

 The following section notes are either in HTML, Acrobat Portable Document Format (PDF), PostScript (PS)
 

• Handout on mathematical induction in PDF , or PS.

• Handout on solving recurrences in PDF

• Handout on basic math notations in PDF

• Handout on basic graph concepts in PDF , or PS .

• Handout on turning recursive algorithms into iterative ones in PDF, or PS.

• Handout on reduction in PDF.

• Handout on dynamic programming in PDF, or PS.

• Handout on greedy algorithms in PS.

MIDTERM PRACTICE PROBLEMS.

• Midterm practice problems in HTML.
• Solutions or hints to the practice problems are here.

MIDTERM SOLUTIONS.

• Midterm solutions in PSor PDF.
• Midterm grading criteria.

QUIZ 2 PRACTICE PROBLEMS, SOLUTIONS.

• Quiz 2 practice problems in TXT.
• Quiz 2 practice solutions in TXT.
• Quiz 2 Solutions in PS, PDF.
• Quiz 2 Grading standards.

FINAL PRACTICE PROBLEMS

• Final practice problems in pdf.
• Final solutions ps, pdf.