2016 November 1,

CS 111: Extra Exercises

This is a list of extra exercises, which you can attempt while studying. Some of them come from our textbook. I have annotated those with the skills they require. Others are of my own invention.

Exercises from Our Textbook

These exercises are scattered throughout Chapter 1.

• 1.6: math, logic
• 1.9: writing functions (write a function for it)
• 1.15: arithmetic
• 1.26: writing functions
• 1.32: range
• 1.38: drawing
• 1.39: drawing

These exercises are scattered throughout Chapter 2.

• 2.8-2.10: accumulator pattern, loops, writing functions
• 2.21-2.27: Booleans
• 2.32-2.33: Booleans, ifs, writing functions
• 2.38: Booleans, ifs, writing functions

These programming exercises come at the end of Chapter 2.

• 2.7-2.8: loops, writing functions

These exercises are scattered throughout Chapter 3.

• 3.1-3.4: strings
• 3.18: strings, loops, accumulator pattern
• 3.23-3.24: strings, loops, accumulator pattern

These exercises are scattered throughout Chapter 4.

• 4.1-4.2: basic list manipulation
• 4.6: lists, writing functions
• 4.10-4.11: aliasing

These exercises are scattered throughout Chapter 6.

• 6.1-6.3: cImage, algorithmic thinking
• 6.17: writing functions, higher-order functions (use imageMapped)
• 8.15: loops, strings, algorithmic thinking (use thewaroftheworlds.txt)
• 8.23: strings, loops (don't use regular expressions)

This is a good exercise from Chapter 9.

• 9.19: recursion, drawing, fractals

Exercise A

Write a function intFromBinary that takes a list of bits and returns the corresponding unsigned integer. Also write the inverse function binaryFromInt. For example, intFromBinary([1, 1, 1, 0]) returns 14, and binaryFromInt(14) returns [1, 1, 1, 0].

Exercise B

I have written a function abstractFor that expresses a for loop in terms of its four crucial pieces.

def abstractFor(start, end, step, body):
    for i in range(start, end, step):
        body(i)

To get an idea of what it does, try

abstractFor(0, 10, 1, lambda x: print(x ** 2))
abstractFor(10, -10, -6, lambda x: print(abs(x)))

You have two tasks. First, rewrite abstractFor so that it uses a while loop instead of a for loop. Second, rewrite abstractFor so that it uses recursion and no loops at all.

Exercise C

Here is a set of nested loops, with two levels in the nest:

for i in range(3):
    for j in range(2):
        print([i, j])

Here is a set of nested loops, with three levels in the nest:

for i in range(3):
    for j in range(2):
        for k in range(4):
            print([i, j, k])

When you write a program, you can nest loops as deeply as you want, right? But what if you need your program to decide, while it's running, how deeply to nest? I've written a general loop-nesting function called nestedLoop:

def nestedLoop(bounds, body):

The bounds argument is a list of non-negative integers. The length of bounds is the depth of the nest. bounds[i] is the bound on the ith level of the nest. The body argument is a function. As input it takes a list of indices, indicating the current values of the loop counters. It returns None. So, for example, the following two commands are equivalent to the two examples shown above.

nestedLoop([3, 2], lambda indices: print(indices))
nestedLoop([3, 2, 4], lambda indices: print(indices))

Your task is to complete the implementation of nestedLoop. My implementation calls a helper function. The helper function is six lines of code.

Exercise D

We have written analogues of map and thread for images, called imageMapped and imageThreaded. Design and write an analogue of reduce called imageReduced. Also explain why there is no sensible analogue of filter.

Exercise E

What is the running time, in big-O notation, for the algorithms in Exercises A-D above?