Handwritten submissions only.
Do not type your homework for this homework assignment.
We will discuss advisablity for subsequent homework submissions.
But for now, don't.
Why?
 Short Answer: Because.
 Long Answer: Judging from the submissions of your
predecessors in this course, it is exceedingly
difficult to properly format your work. You lose points
and/or your grader becomes cranky. (Which amounts to the
same thing.)
Anything else?
Write clearly. If people have told you in the past your work is hard to read of messy, you'll have to try harder or copy over your work neater when done solving problems.
Do not cram your lines together. You should
submit the handwritten equivalent of "doublespaced" work.
There should be a 1.5 inch margin on both left and right side of each page
to allow room for my comments and grading notes.
If you use lined paper, make sure your writing is darker than those lines!
The size of your writing should be 14pt font. No small writing. I want to be
able to read it easily.
For this assignment, at most one problem per page and singlesided submissions only.

Consider the formal definition for the sorting problem given on the first
page of chapter 2 in CLRS.
 Using similar formalities, write a definition for a problem findmin
that instead of modifying the input sequence, scans it for the smallest value and
returns the index of that value in the sequence no matter what it is.
 Write pseudocode for findmin.
 Using a loop invariant, prove that your algorithm for findmin is correct.
Make sure that your loop invariant fulfills the three necessary properties.

Consider the searchingproblem
Input: A sequence of n
numbers A=<a_{1},a_{2},...,a_{n}>
and a value v.
Output: An index i such that v = A[i]
or the special value NIL if
indicates that v does not appear in A.
 Write pseudocode for linearsearch, which scans through the sequence,
looking for v.
 Using a loop invariant, prove that your algorithm is correct.
Make sure that your loop invariant fulfills the three necessary properties.

Consider sorting n numbers stored in an array A by first finding the
smallest
element of A and exchanging it with A[n].
Then find the second
smallest
element of A and exchanging it with A[n1].
Continue in this manner for the first n1
smallest elements of A.
 Write pseudocode for this algorithm.
 What loop invariant does your algorithm maintain?
 What consequences would there be if instead of doing the search and exchange step
n1 times you did it ...
for only n2 times?
for exactly n times?
 If there is a relationship of numbers in an input array that causes your pseudocode to
run more slowly/quickly than another, describe it. If there is no such relationship, explain why not.
For this homework, you are asked to pledge the following.
 I have not consulted any source other than the allowed
 Dr. Dale
 our textbook
 I have not consulted any other person, any other text, or the web.