Comp 215 Homeworks and Reading

Discussion Questions

• Questions for Wednesday of First Week:
  • Exercises 1, 3, 6, and 8 in Chapter 1.

  ---

• Questions for Friday of First Week:
  • Read through the Properties of Order on page 37. Try to convince yourself that all of them are indeed true. Come to class with questions about any of the properties that you are not convinced of.

  ---

• Questions for Monday of Second Week:
  • Exercise 15 in Chapter 1.
  • Exercise 19 in Chapter 1.
  • Parts a, b, and c of Exercise 1 in Appendix B.

  ---

• Questions for Wednesday of Second Week:
  • Parts a, b, and c of Exercise 12 in Appendix B.
  • Exercise 24 in Appendix B.

  ---

• Questions for Friday of Second Week:
  • Exercises 1, 2, 5, 6, 7, 8, 13 in Chapter 2.

  ---

• Questions for Monday of third week:
  • Exercises 19, 23, and 24 in Chapter 2.

  ---

• Questions for Wednesday of third week:
  • Sketch out your convex hull implementation. Come to class with questions.

  ---

• Questions for Friday of third week:
  • Exercises 4 and 7 in Chapter 3.
  • Use Floyd's algorithm to determine the shortest paths matrix for the graph whose adjacency matrix is:

    0	2	4	3
    3	0	∞	3
    5	∞	0	3
    ∞	1	4	0

  ---

• Questions for Monday of fourth week:
  • Exercises 2, 3, 5 and 8 in Chapter 4.

  ---

• Questions for Wednesday of Fourth Week:
  • Exercise 11, 24, and 26 in Chapter 4.

  ---

• Questions for Friday of Fourth Week:
  • Exercise 30, and 32 in Chapter 4.

  ---

• Questions for Wednesday of Fifth Week:
  • Exercises 16-20 in Chapter 5.

  ---

• Questions for Monday of Sixth Week:
  • Exercise 30 in Chapter 5.
  • Exercises 1 and 4 in Chapter 6.
  • (Use W=10 for all.)

  ---

---

• Questions for Wednesday of Seventh Week:
  • Exercise 7 in Chapter 6.

  ---

• More questions for Wednesday of Seventh Week:
  • Exercises 26,32, 37, and 38 in Chapter 7.

  ---

• Questions for Monday of Eighth Week:
  • Exercise 2 in Chapter 8. (I think S and T must be sorted for this to work, but I could be wrong.)
  • Radix sort the following numbers: 329, 457, 39, 657, 839, 79, 436, 8, 720, 355.
  • Insert the letters K, A, L, A, M, A, Z, O, and O one at a time into an initially empty 3-2 tree. Show the actions step-by-step.

  ---

• Questions for Friday of Ninth Week:
  • Apply the Selection Algorithm (Algorithm 8.5) to find the sixth-smallest value in the list 30, 80, 20, 100, 50, 40, 90, 60, 70, 10. Notice that Algorithm 8.5 is the algorithm that uses the first value as the pivot, not the one that uses the median of medians. You do not need to step through the partition algorithm: just partition the values yourself, leaving the values in each partition in the same order relative to the other values in the partition.
  • Exercise 15 in Chapter 9.
  • Double-CNF-SAT is the problem of determining whether a CNF formula has at least two satisfying assignments. Show that Double-CNF-SAT is NP-complete by showing a reduction from CNF-SAT.

  ---

• Questions for Monday of Tenth Week:
  • We define the MIN-ELEMENT decision problem as follows: given an unsorted list of n integers, and an integer k, determine whether the minimum integer in the list is smaller than k. Show that min-element is polynomial time many one reducible to CNF-SAT. Does this mean than min-element is NP-Complete?
  • Example 9.3 in our book describes the 0-1 knapsack decision problem. Show that the 0-1 knapsack decision problem is polynomial time Turing reducible to the 0-1 knapsack optimization problem. What can we conclude about the 0-1 knapsack optimization problem? (E.g. is it in P? NP? NP-complete? NP-hard?)