In-class notes for 02/24/2014 (CS 121B (CS1), Spring 2014)

In-class notes for 02/24/2014

CS 121B (CS1), Spring 2014

Homework assignment
Added syntax for if and specs for or, not to notes for last time.

Submitted questions on assignments and technology

Upcoming

Homework 7
Read online text: Recursion
submit at least one reading question by 9am before the next class meeting
Although this means reading the chapters out of order, we want to start using the other kind of repetition (recursion) sooner rather than later, for applications. Example below
Quiz on Wednesday. See below for topics.

______

Submitted questions on readings

Accumulators, revisited

Example of a loop:

        count = 0
	# invar: count holds the number of invitations printed so far
        for name in ['Bob', 'Carol', 'Ted', 'Alice']:
            print("Hi,", name, "-- please come to my party!")
            count = count + 1

Output from that loop:

    Hi, Bob -- please come to my party!
    Hi, Carol -- please come to my party!
    Hi, Ted -- please come to my party!
    Hi, Alice -- please come to my party!

The final value of count is 4. The variable count is an accumulator, i.e., a variable we use to build up an answer over time.
Tracing accumulators..

Another example: the accumulator from countPositives

        count = 0
	# invar:  count holds the number of positive elements seen so far
	for elt in [4, -2, 7.8, 0, -1, 5]:
	    if elt > 0:
		count = count + 1

Trace...

Exercises: By hand, trace the following loops with accumulators; also predict the final values of those accumulators

    posct = negct = zeroct = 0
    # invar:  
    #   posct holds the number of positive elements seen so far AND
    #   negct holds the number of negative elements seen so far AND
    #   zeroct holds the number of zeroes seen so far
    for elt in [4, -2, 7.8, 0, -1, 5]:
        if elt > 0:
            posct = posct + 1
	elif elt < 0:
            negct = negct + 1
	else:  # assert:  elt == 0
	    zeroct = zeroct + 1

    prod = 1
    # invar: prod holds the product of the first N-1 positive integers
    for N in range(1, 5):
        prod = prod * N

Anatomy of iteration

A loop is a language statement for repetition through iteration, one of two strategies we will explore for repeating computer actions in Python3.
By "anatomy" of iteration (as in a loop), we mean the structural elements that are common to all iterations.

Example:


    # invar: i holds the number of lines printed so far

    for i in range(1, 5) :

        print(i, i*i)

Anatomical parts of an iteration:
- initialization: assign initial value(s) to loop control variable(s). In this case, the loop control variable is i, and its initial value is 1
- invariant: a statement of what is logically true at the beginning and end of each iteration (repetition). We include this in a Python3 comment (intended for human reader)
- guard: stopping condition for the iteration. In this case, the iteration stops when the loop control variable i reaches the value 5 (specified in the range() call)
- body: programming-language statements to be repeated. In this case, the body consists of the print() statement.
- progress: how to adjust the loop control variable for the next iteration. In this case, range(1, 5) adds 1 to i to obtain the next value.

While loops

Syntax for a Python3 while loop:

We can use while loops instead of for loops to accomplish any iteration we can program with for. Examples:

    # invar: i holds the number of 
    #          lines printed so far    
    for i in range(1, 5) :
        print(i, i*i)

    i = 1
    # invar: i holds the number of 
    #          lines printed so far    
    while i < 5:
        print(i, i*i)
        i = i + 1

However, we will need to learn more about lists before we can use while loops that are controlled by lists
for is convenient when the number of repetitions is known in advance.

while is convenient when the number of repetitions is not known in advance
Anatomy of iteration in a while loop:

Image manipulation

______

Example of recursion

Recall the computer art example from HW1

The program for generating this "sprig" drawing accomplishes repetition without for or while loops:

import turtle

window = turtle.Screen()
fred = turtle.Turtle();

def drawSprig(tu, length, factor, angle, colors):
    if colors != []:
        prevcolor = tu.pencolor()
        tu.pencolor(colors[0])
        tu.forward(length)
        tu.left(angle)
        drawSprig(tu, length*factor, factor, angle, colors[1:])
        tu.right(angle)
        drawSprig(tu, length*factor, factor, angle, colors[1:])
        tu.right(angle)
        drawSprig(tu, length*factor, factor, angle, colors[1:])
        tu.left(angle)
        tu.up()
        tu.backward(length)
        tu.down()
        tu.pencolor(prevcolor)

fred.left(30)
drawSprig(fred, 100, .5, 40,  ['black', 'green', 'blue', 'red'])

This is repetition through a function calling itself in its own definition --- "do the same thing again, with changed parameters"

This type of repetition is called recursion, and it gives the best solutions to some kinds of programming problems (such as drawing a sprig).

To study for quiz

for loops
function defs, given specs
accumulators

< >