Homework assignment 04
Homework assignments
Homework assignment 07
Document also available in PDF, Postscript, DVI, pure text and LaTeX.
2.3. More on Proof of Correctness
Exercise 1 13 p. 120 Function to return the value of the
polynomial anxn + an-1xn-1 + ... + a1x+a0
at a
given value of x:
|
Poly(real an;...; real a0; real x) |
| Local variables: |
| integers i,j |
| |
i = n |
| j = an |
| while |
i != 0 do |
| j = j * x + ai-1 |
| i:=i-1 |
| end while |
| //j now has value of the polynomial evaluation return j |
| end function Polly
|
Proof: [Correction]
Before the first iteration, we have j0=an. Then, after one
iteration, we have j1=anx +an-1, and at the end, we want to
have
| j |
= |
anxn + an-1xn-1 + ... + a1x+a0 |
| |
= |
|
|
Qk: jk = anx |
|
+ an-1x |
|
+ ... +
a |
|
x+a |
|
.
|
Let's assume that after k iterations, Qk holds, and prove that
Qk+1 holds after one more iteration. By the assignment rule, we
get ik+1=ik-1. Using Qk and the assignment rule, we get
| jk+1 |
= jk x + ai-1 |
| |
| = (anx |
|
+ an-1x |
|
+ ... + a |
|
)x+a |
|
|
| |
| = anx |
|
+ an-1x |
|
+ ... + a |
|
x+a |
|
|
| |
| = anx |
|
+ an-1x |
|
+ ... + a |
|
x+a |
|
. |
|
After the loop, Q holds and we have i=0. Therefore j=anxn +
an-1xn-1 + ... + a1x+a0, as wanted.
2.4. Recursion and Recurrence Relations
Exercise 2 40 p. 141
Give a recursive definition for the set of all strings of well-balanced parentheses.
Proof: [Correction]
-
The empty string is a string of well-balanced parenthesis.
- If P and Q are strings of well-balanced parenthesis, then
(P)Q is also well a string of of well-balanced parenthesis.
For example, we get the string () by taking P and Q to be empty.
2.5. Analysis of Algorithms
Exercise 3 1 p. 152
For the algorithm of Example 45, count the total number of
assignments and comparisons done in the best case (least work) and
the worst case (most work); describe each of these cases.
Following is an algorithm to write out the sum of the m quiz
grades for each student on a grade roster after dropping each
student's lowest grade. The outer loop goes through each of the
n students; the inner loop goes through the quizzes for the
current student. The algorithm assigns values to variables and
performs comparisons (to find the lowest quiz grade for each
student). It also does some adding and subtracting, and we will
count the work contributed by these arithmetic operations.
|
for |
i := 1 to n do |
| low := roster(i).quiz(1) |
| sum := roster(i).quiz(1) |
| for |
j = 2 to m do |
| sum := sum + roster(i).quiz(j) |
| if |
roster(i).quiz(j) < low then |
| low := roster(i).quiz(j) |
| end if |
| end for |
| sum := sum - low; |
| write(``Total for student '',i,`` is '',sum) |
| end for
|
Proof: [Correction]
In either the ``best'' or ``worst'' case, a certain base number of
comparisons and assignments are made. For instance, sum
will undergo n(m+1) assignments. This is the case, because
sum is first assigned the initial quiz score, then added to
m-1 times, and the lowest score is then subtracted once (all of
which is repeated n times). We also have 2n(m-1) test (as, we
have the tests in the loops and the test if
roster(i).quiz(j)< low). So we have a total of 3nm
base comparisons and assignments which do not depend on the values
of the quizzes.
The ``best case'' is when all n students had their lowest score on
their first exam. In this case, you have the base case of 3nm.
The ``worst case'' is when each student had a lower score on each
exam, such that quiz1>quiz2>quiz3>...>quizm. The
reason why this is the ``worst case'' is that low is
assigned a new value m times. This would bring the total to
4nm-n comparisons or assignments.
Exercise 4 8 p. 153
In a part of the algorithm SelectionSort
, the index of the
maximum item in a list must be found. This requires comparisons
between list elements. In an n-element (unsorted) list, how many
such comparisons are needed in the worst case to find the maximum
element? How may such comparisons are needed in the average case?
SelectionSort(list L; integer j) //recursively sort the
items from 1 to j in list L into increasing order
|
if |
j=1 then |
| sort is complete, write out the sorted list |
| else |
| find the index i of the maximum item in L between 1 and j |
| exchange L(i) and L(j) |
| SelectionSort(L,j-1) |
| end if |
| end function SelectionSort |
Proof: [Correction]
n-1 comparisons are made for the ``best,'' the ``worst,'' and the ``average'' case.
Exercise 5 9 p. 153
Defining the basic operation as the comparison of list elements and
ignoring the amount of work required to exchange list elements,
write a recurrence relation for the amount of work done by
SelectionSort on an n-element list. (Hint: Use the
result from Exercise 8.)
Proof: [Correction]
The number of comparisons for a list of n-elements is C(n) =
C(n-1)+n-1, where C(1)=0. The reason being that it took n-1
comparisons to find the maximum, the maximum is then placed at the
end of the list and we are left with a list of n-1 elements.
Exercise 6 10 p. 153
Solve the recurrence relation of Exercise 9.
Proof: [Correction]
Since we are only concerned with the number of comparisons, the work
is merely the total number of comparisons. Since it takes n-1
comparisons in the first run, n-2 comparisons in the second run,
..., and 0 comparisons in then nth run, the total
number of comparisons is C(n)=n(n-1)/2.
Homework assignment 04
Homework assignments
Homework assignment 07
Homework assignment 06 /
CSM MACS-358 /
Nicolas M. Thiéry
Last modified: Tue Dec 2 13:40:28 2003