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

In-class notes for 03/03/2014

CS 121B (CS1), Spring 2014

Homework assignment
Quiz returned... Wed

Submitted questions on assignments and technology

HW9 E problem 2f

Recall example from last time

import cImage as image

def negative(img):
    for row in range(img.getHeight()):
        for col in range(img.getWidth()):
            pixel = img.getPixel(col, row)
            red = pixel[0]
            green = pixel[1]
            blue = pixel[2]
            img.setPixel(col, row, image.Pixel(255-red, 255-green, 255-blue))
    return img    

def main():
    win = image.ImageWin()
    img = image.Image("stomag.png")
    img.draw(win)  # shows the image before modification
    img = negative(img)
    img.draw(win)  # shows the image after modification
    
    img.save("stomag_negative.png")
    win.exitonclick()

main()

The goal for the sepia problem is to compute new red, green, and blue intensities as described in the sepia problem.
Images:

Recursion problem 8d -- modifying drawSprig()

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'])

clear() method for turtle.Screen() objects.

Upcoming

Homework 10
Quiz on Friday this week, instead of Wednesday.

Submitted questions on readings

Image processing

Functions that create new image objects

cImage.EmptyImage

2 arguments: Non-negative integers
State change:: Creates a new Image object with arg1 columns and arg2 rows, all initialized as white pixels.
Return: That newly constructed Image object

Example call:

    import cImage as image
    win = image.ImageWin()
    img = image.EmptyImage(200, 300)
    img.draw(win)  # shows a white image, 200x300 pixels

Doubling the size of an image

Recursion

Review
In-class exercise last time:
- Exercise 1: Write a function that counts the number of elements in a list, using recursion
  
  countElements
  
  One argument: A Python3 list
  
  Return: A non-negative integer, the number of elements in arg1
  
  Example call:
```
    countElements([1, 'a', 2]) --> 3
    countElements([]) --> 0
```
- Solution:
```
    def countElements(lis):
        if lis == []:
	    return 0
        # assert: lis is a non-empty list
        else:
	    return 1 + count_elements(lis[1:])
```

Problem solving with recursion

Start with a spec. Recursion requires recognizing the same programming goal with smaller data, and a spec clearly states what a function's programming goal may be.

Example:

countElements

One argument: A Python3 list

Return: A non-negative integer, the number of elements in arg1

Example call:
```
    countElements([1, 'a', 2]) --> 3
    countElements([]) --> 0
```
To find the number of elements in a list [1, 'a', 2],
1. First, find the number of elements in shorter list ['a', 2]
2. Then, add 1
3. Syntax for these steps: 1 + countElements(lis[1:])
  Because: countElements(lis[1:]) is the number of elements in the "tail" lis[1:], according to the spec of countElements().
Use cases. With list arguments, there are usually at least two cases
1. Empty list -- typically solved directly, i.e., without using recursion.
2. Non-empty list -- typically solved using recursion, since we don't know how many elements remain in that list
Syntax: Use if/else (for two cases) or if/elif/else (or nested if, for more than two cases)
```
    if lis == []:
	return ______
    # assert: lis is a non-empty list
    else:  
	______
```
Write # assert comments as you go. These comments describe the logical state at a particular point in the computation, and taking the time to write that helps you focus on what needs to be done at that point.

Example:
```
    if lis == []:
	return ______
    # assert: lis is a non-empty list
    else:  
	______
```
Note: As in the example above, we will write # asserts just before the syntax for the next case, to describe what must be true if we get that far.

Recursive functions that return a list

Recall concatenation operator for lists.
Tracing a list concatenation.

Exercises

Exercise: Write a function that produces a list of doubles of elements in a list of numbers, using recursion

double

One argument: A list of numbers

Return: A list of numbers, whose elements are twice the corresponding elements of the list arg1

Example call:
```
    double([4, 7, -1.5]) --> [8, 14, -3.0]
    double([]) --> []
```
Hints:
- Use the concatenation operator + assemble the answer.
- As before: use if to handle the empty-list case separately; no accumulator; use a slice.

Exercise: Write a function whose return value replaces particular value in a list with another value, using recursion

replace

3 arguments: Any two Python3 values and any Python3 list
Return: A list, whose elements are the same as the elements of the list arg3, except with each occurrence of arg1 replaced arg2.

Example calls:

    replace ('a', 77, [4, 'a', 1]) --> [4, 77, 1]
    replace (5, 8, [5, 5, 0, 5, 7]) --> [8, 8, 0, 8, 7]
    replace (5, 8, []) --> []

Hints:

This problem needs three cases:
- empty list
- first element matches arg1
- first element doesn't match arg1
Use if/elif/else (or nested if/else to program for each case separately
As before, use concatenation operator, slice, etc.
Be sure to include the first two arguments in your recursive calls

Upcoming recursion topics

Two other ways to think about recursion (besides problem-solving/specs): patterns; tracing recursion
Stack frames
Recursion with nested lists

Strings

String methods
String operators: [ ] (index) [ : ] (slice) + (concatenate) * (repeat) == != < > <= >= in not in
May talk about L-systems later

Built-in function len()

len (builtin)

One argument: A list or a string
Return: A non-negative integer: if arg1 is a list, returns the number of elements in that list; and if arg1 is a string, returns the number of characters in that string.

Example calls:

    len([1, 'a', 2]) --> 3
    len([1, 'a', [2, 5]]) --> 3

    len("apple") --> 5

Builtin functions for characters: chr(), ord()

< >