320 HW 0

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 "double-spaced" 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 single-sided submissions only.

  1. Consider the formal definition for the sorting problem given on the first page of chapter 2 in CLRS.
    1. Using similar formalities, write a definition for a problem find-min 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.
    2. Write pseudocode for find-min.
    3. Using a loop invariant, prove that your algorithm for find-min is correct. Make sure that your loop invariant fulfills the three necessary properties.
  2. Consider the searching-problem

    Input: A sequence of n numbers A=<a1,a2,...,an> 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.

    1. Write pseudocode for linear-search, which scans through the sequence, looking for v.
    2. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
  3. 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[n-1]. Continue in this manner for the first n-1 smallest elements of A.
    1. Write pseudocode for this algorithm.
    2. What loop invariant does your algorithm maintain?
    3. What consequences would there be if instead of doing the search and exchange step n-1 times you did it ...

      for only n-2 times?

      for exactly n times?

    4. 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.

    1. I have not consulted any source other than the allowed
      1. Dr. Dale
      2. our textbook
    2. I have not consulted any other person, any other text, or the web.