CS328 Homework Assignments

Objective of Homework

1. Develop problem solving skills.
2. Develop the ability to communicate knowledge.

Software development is generally done in teams. When solving problems, you must be able to communicate that solution to co-workers as well as communicate the correctness of the problem solution. In solving problems, you must be able to methodically present the solution so it can be verified.

Credit for Solutions

Each step of your problems solutions must be thoroughly explained. If you arrive at a correct answer and I cannot follow how you arrived at the answer, you will not receive credit. If you arrive at a wrong answer, and I can follow through your process of how you arrived at the answer, you will receive partial credit.

Homework must be submitted to D2L prior to the beginning of class on Monday of the class following the completion of the associated chapter.

For all textual information, a word processor must be used. It is acceptable for diagrams to be neatly hand drawn.

Appendix A

Exercises:

1. 2
2. 4 a (you must use induction)
3. 5 a, b, c
4. 12
5. 25

Chapter 1

Appendix B

1. Question 1a
2. Solve by substitution:

   T(n)=T(n-1) + 2^n

   T(0)=1=2^0

3. Suppose a divide-and-conquer algorithm always divides an instance of size n of a problem into 10 sub-instances of size n/3 and the dividing and combining steps take theta (n^2) if n > 1 and it performs one basic operation if n = 1.

   a. Write a recurrence equation for the running time of T(n).

   b. Solve the recurrence equation for T(n). Hint: 3 different ways to solve recurrence equation:

   • Guess a solution and use induction to prove
   • Solve by substitution
   • Theorem B.5

   Substitution is not a good way to solve this recurrence.

Chapter 2

1. Show the details of the nesting of recursive calls for Mergesort (Algorithm 2.4) and QuickSort (Algorithm 2.6) to sort the following array:

   [128, 34, 189, 56, 150, 12, 9, 240]

   Show the parameter list of each call and the order the calls execute.

2. Explain the input that elicits the worst-case behavior of Quicksort assuming it chooses the first item as the pivot point.
3. Explain the input that elicits the worst-case behavior of Mergesort.
4. Explain the input that elicits the worst-case behavior of binary search.
5. Question 5
6. Come to class prepared to work on the Towers of Hanoi Problem

Chapter 3

1. Page 105 of the text provides a formula for the value of D^k[i][j] as the minimum of the equalities (3.3) and (3.4). Explain the recursive formula.
2. Show the values of D^1, D^2, and D^3 for the graph whose edges and weights are represented in the following adjacency matrix:
   

   	1	2	3
   1	0	1	2
   2	3	0	6
   3	infinity	1	0

3. For n=4, produce M using Algorithm 3.6

   Matrix	Dimension
   A	4 x 2
   B	2 x 3
   C	3 x 1
   D	1 x 2

4. Use Algorithm 3.2 to compute the binomial coefficient: B[5,3]. To receive any credit, you must show each step of building the array.
5. Explain the Principle of Optimality and how it is used.
6. Question 1.

Chapter 4

1. Question 2. Use the high-level algorithm for the trace.
2. Question 7. Use the high-level algorithm for the trace.
3. Question 9.
4. Question 13. Use the high-level algorithm for the trace.

Chapter 6

1. Question 1.

Chapter 7

1. Question 9.

There is a misprint in the text. It should read show .... has n(n-1)/2 inversions.

2. Question 10.

Chapter 8

1. Question 10. /li>

Last modified 11/4/2023