HW Notes

General

In addition to be correct and complete, your work should be easy to read & understand.

Clarity and neatness count

If I must squint to distinguish characters or guess at your assumptions, I get ... cranky.

Think about what you are writing down and how it sounds "outside your head".

Just as missing information is bad, so is going on and on when a brief statement will do. You will get practice with this but do the best you can from the beginning.

Your paper surface also can help or hurt here. Plain white works great as long as your handwriting does not tend to... wander. Lined paper should be considered if it does. Graph paper is NOT ACCEPTABLE unless it is the very lightly lined and does not *in any way* (to be determined by your instructor!) interfere with a reader's understanding of your handwritten work.

Every submission should have prominent first page header giving
your name & the date as well as dept, course#, and hw#
                       Chris Jeronimo
                       Sept 12, 2019
                       CSCI 320 -- HW 0
               
For our assignments, justification is always required. Unless explicitly told to leave your answer as yes/no or something similarly short, you should always include a brief justification for the provided response. "Just 'cause" is generally off limits.
In all submissions, please use only one side of your paper unless you are using a heavier weight paper than usual. Between your writing and my grading, double-sided submissions become difficult to easily read.

PseudoCode

Pseudocode requires a "method signature"-like first line. You should also include all pre-conditions, post-conditions necessary to determine exactly what problem the pseudocode proposes to solve as well as clarifying comments throughout where things get "tricky" or convoluted

Whether explicitly instructed to do so or not, always include a brief discussion of running time whenever you are asked to provide pseudocode. This falls under heading of "justification".

Loop Invariants - Guidelines for writing them.

A 'loop invariant' statement is a statement which is always true.

L.I.'s are declarative statments of verifiable fact.

They never include conditions or instructions.

They are as 'strong' as possible.


               Consider this psuedocode:

               SillyLoopPsuedoCode()

               1)  i = 5
               2)  while ( i <= 10 )
               3)     print i
               4)     i = i + 1
               5)  print 'Good bye' 


               For the pseudocode above we might come up with many...'invariant' statements.  

                    a)  i is always positive

                    b)  i is always greater than 5

                    c)  i is always less than 1000

                    d)  i is always between 5 and 10

                    e)  i is always an integer

                    f)  the value of i is always getting bigger

                    g)  i is always an integer value [ 5 , 11 ]

               

               Which is/are 'strongest'?


               Which are invariant?  How can you prove it?

               To demonstrate a L.I. is 'always true' we show that it is true
                  before, during and after the loop is executed.  These three
                  points are referred to by your text as 

                  initialization (ie, i=5 on line 1 of pseudocode)
                  maintanence    (ie, as i is incremented on line 4 of loop body)
                  terminatation  (ie, when line 5 is reached)

          

Loop Invariants - Guidelines for proving them.

Initialization, Maintenance & Termination altogether prove the L.I.
(Although init & term are usually simpler, you should never leave them out!)

Your maintenance step should ASSUME the L.I. holds for all previous iterations and then discuss at length by appeal strictly to that inductive hypothesis and the pseudocode of A SINGLE ITERATION through the loop body that the L.I. is maintained during the execution of an arbitrary iteration.

It is a mistake to include discussion of what happens over multiple iterations in a "maintenance" step for Loop Invariant (L.I.) proofs. Limit your discussion to exactly what happens during a single iteration.

Though your maintence step discussion is a "single iteration" your discussion of it may have more than one case, (ie, conditional).