A lab consultant who can help with C251 questions is in LF105 or LF111.

See: www.ius.edu/rwisman/lab for current schedule.

Contact me by email with any questions. I can also usually arrange to meet on campus.

Options:

1. Bring a handwritten homework to class on due date.
    
2. Email Word document HW4.doc to instructor by 13:00 on due date.

The special symbols can be copied from the notes and pasted into Word. Here are some:

$"¬®³¹«£ºÆÏÎÈÍÇ ë û é ù

• Graph the following three functions on the same plot:
  1. x+4
  2. x
  3. 1/x

  And answer True/False:

  1. After some value of x, x is bounded above by x+4.
  2. After some value of x, x is bounded below by 1/x.
  3. After some value of x, 1/x is bounded above by x.
  4. After some value of x, 1/x is bounded above by x+4.
      
• Section 3.1 -- pp. 177 - 178
  • 6
  • 8
  • 12
  • 14
• Section 3.2 -- p. 191
  • 2 a, b, c, d (only)
  • 6 - Derive C and k following method used in class.
  • 10
  • 14

    For example, 14a. asks whether x³ is O(x²).

• Section 3.3 -- pp. 199 - 200
  • 8 a and b

    8b) hint: Count the total multiplications and additions in: y := y * c + a_n-i

  • 10 - You might find a spreadsheet handy if you don't have a fancy calculator.
  • 12 a, b (only)

   

• Section 4.1 -- pp. 279
  • 4 (use 3 as a model)

  Extra credit

  • Induction Proof of loop invariant - Summation of a sequence

    Hint: See Chapter 4 notes Example proof of loop invariant - Maximum of a sequence

    Note

    Use of P_k and P_k+1 not necessary but helpful in thinking about the induction.

    a. What is the postcondition?

    b. What is the loop invariant?

    -- Precondition:  ∃a1 procedure Pn( a1, a2, a3, ..., an : integers) Pk ← a1 i ← 1 while  i < n Pk+1 ← Pk + ai+1 i ← i + 1 Pk ← Pk+1

    Show ∀j: 1 ≤ j ≤ i, ∑a_j = P_k ^ i ≤ n is always true

    1. Base Step: before the loop,	c. Base step?
    2. Inductive Step: Pk → Pk+1 at the end of each loop,	d. Show what for Pk+1? e. Assume what? f. Proof
    3. and after the loop completes	i = n ∴ ∀j: 1 ≤ j ≤ i = n, ∑aj = Pk