Introduction to Computer Science:
Control Structures and Data Types

Welcome to Unit 2!

1. Branching Structures

A "branching structure" is an element in a program that allows a decision to be made, depending on some condition. In Python, the branching structure is the if statement.

1.a. The if statement

Python's branching structure is the if statement. In its most basic form, it looks like this:
if <Boolean condition>: <statement> <statement> <statement> <Statement that is NOT part of the suite>

The Boolean condition has a value that is True or False. If the condition is True, the 3 statements in the indented suite will be executed, and then the statement following that suite will be executed. If the condition is False, the 3 statements are skipped, and only the statement following the suite is executed. (Note that the suite has been indented 4 spaces, the standard in Python.)

Write a series of short programs to try each of these and see what happens:

if (2 < 3): print "hi!" print "bye"
if (3 < 2): print "hi!" print "bye"
if (2 <= 2): print "hi!" print "hi!"
n = "richard" if (n == "Richard"): print "I know you!"
letter = "b" if (letter != "A"): print "The letter is not A" print "The letter IS A!"

Did the very last example behave the way you expected it to? Probably not...

1.b. Types of Errors

Writing programs is really hard work. Depending on the type of program, you may find that the time you have to allot to working on it looks something like this:

Planning your program20% of total time
Writing/entering code10% of total time
Debugging code to eliminate errors70% of total time

The types of errors, or "bugs", that you'll have to deal with fall into three categories:

Syntax errors are the equivalent of spelling or grammar mistakes: you have mistyped something, or constructed a program statement in such a way that Python doesn't understand what you're trying to do.

In the case of most syntax errors, your program won't even run, and Python will try to give you an error message that may help you figure out what you did wrong.

Runtime errors are problems with your program that crop up when the program is running: you ask the user to enter two numbers to be added together, for example, and they type in the words "two" and "three". Writing robust programs that help to prevent this kind of problem is an important part of programming.

Logical errors have to do with unexpected behavior of the program. In the example here:

letter = "b" if (letter != "A"): print "The letter is not A" print "The letter IS A!"

... the program is syntactically correct, and it runs fine—it just didn't do what we'd expected it to do: It's output is:

The letter is not A The letter IS A!

The logical flow of the program doesn't match what we were anticipating.

So... how would we write that program to identify whether or not the value of letter is "A"?

1.c. Additional if statements

There are additional forms of the if statement that often come in handy:

If you want to manage a 2-way condition (either do this, or that), use the if-else statement:
if <Boolean condition>: <statement> <statement> else: <statement> <statement> <Statement that is continuation of program>

Note that the if and else suites are indented 4 spaces, which helps us visualize that they are the two different options in this part of the program.

Write a program that asks the user to enter a number. If the number is greater than 0, the program prints out a "Hello" message that many times. If the number is not greater than 0, the program should print out a brief error message telling them what they did wrong.

Some problems require that there be more than a single option considered. For these cases, you basically have two options:

  1. Organize your logical solution so that a series of if-else statements can be nested, allowing the program's logic to drill down to find the appropriate action, or
  2. if the actions can all be considered simultaneously, use an if-elif-else statement.

Usually one strategy will recommend itself over the other. The next two examples, though, show how each of the strategies can be used to solve the problem of calculating the roots of a quadratic equation.

Using a nested if-else statement to solve a quadratic equation:

a, b, c, = input("Enter coefficients a, b, and c: ") discrim = b**2 - 4 * a * c # "**" = exponent if (discrim < 0): print "There are no real roots! Sorry!" else: print "You have roots. Now calculating..." if (discrim == 0): # Here's our nested loop root = -b / (2 * a) print "You have a double root: ",root else: root1 = (-b + discrim ** 0.5) / (2 * a) root2 = (-b – discrim ** 0.5) / (2 * a) print "The roots are:",root1,"and",root2

Using an if-elif-else statement to solve a quadratic equation:

a, b, c, = input("Enter coefficients a, b, and c: ") discrim = b**2 - 4 * a * c # "**" = exponent if discrim < 0: print "There are no real roots! Sorry!" elif discrim == 0: # "elif" means "else-if" root = -b / (2 * a) print "You have a double root: ",root else: # if first 2 options passed... root1 = (-b + discrim ** 0.5) / (2 * a) root2 = (-b – discrim ** 0.5) / (2 * a) print "The roots are:",root1,"and",root2

Let's try a simple exercise to put some of these pieces together:

Write a program that asks the user to enter a name. If it's your name, the program should print a brief greeting to you and then say "goodbye." If it's anybody else's name the program should say ""Get out of here, <name>!" and then say goodbye.

Recall the syntax for having a user enter a string:

name = raw_input("Please enter your name: ")

Homework

Read Chapter 7, Sections 7.1-7.3; do Chapter 7 programming exercises #1, #3, #6, (#12 optional).

2. Programming Project 1 - CoinFlipper

For our first decent project, we're going to need a little outside help in writing the program. We're also going to introduce the format for the larger projects, which should give you the support you need to complete these assignments as required. This project is not actually much larger than the programs that we've been writing, so that makes it ideal for helping to ramp up your code-writing abilities.

2.a. Modules

A module in Python is a program that someone has written that can be used in a larger program.

One of the tremendous powers of Python is this ability to leverage the work that other people have already done, and the way one does that in Python is by importing modules.

To import a module that someone has already written so that you can use it in your own program, simply include the statement import <modulename> near the beginning of your program.

Try these examples in the Python interpreter:

$ python Python 2.5.1 (r251:54863, Feb 6 2009, 19:02:12) [GCC 4.0.1 (Apple Inc. build 5465)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> import math >>> print math.pi

If you were to type "pi" into a regular program, Python wouldn't know what to do with it. But the module math has some methods built into it that you can use, once you've imported that module.

Similarly, how would you go about calculating the square root of 11? There are actually two ways of doing this:

>>> print 11**(0.5) 3.31662479036 >>> print math.sqrt(11) 3.31662479036

What do you think this code might print?

>>> print math.sin(math.radians(90))

2.b. Help with Modules

If you need some quick help with a module or a method while in interactive mode, use the help command:

>>> help(math)

Most help files are more than a single screen in size, so you can use the f and b keys to page forward and backward through the help document. You can also search forward and backward through the document:

:/pi # searches forward for the term "pi"
:?pi # searches backwards for the term "pi"

If the first occurrence of the search term isn't the one you want, hit the n key for next.

When you're done with the help file, type q for quit.

2.c. CoinFlipper.py

Take a moment to get the CoinFlipper assignment. As much as you might consider it convenient to just work off an electronic copy on the computer, go ahead and print it on paper. It's almost always a good idea to be able to draw on the paper copy, highlight certain key ideas or components, maybe even sketch a quick flowchart or pseudocode of your solution to the program. These are things that are done more quickly and easily with a pen/pencil on paper, rather than on a keyboard. Save the keyboard for actual coding.

Got the printout? Good. Take a look at the assignment and get started.

2.d. Code Review

You can quickly improve both your coding and your debugging skills by examining programs that other people have written.

Be sure you take a few moments to go over other people's programs, see what techniques they've used that you hadn't though of, or see how their programs might be improved.

You'll quickly come to realize how important good comments are in a program, as well as using "self-commenting" variables that help one to understand how a program works.

Homework

Complete coinflipper and upload to server.

3. Indefinite Loops

Let's talk a little more about the while loop, and some of the different ways that it can be used in a program.

3.a. Review of for loops

The for loop is a loop that repeats a specified number of times:

for i in range(10):
for names in ("Joe", "Mary", "Bob"):
for counter in range(10,0,-1):
for number in (1,101,2):

3.b. The while loop

The while loop is typically used when you have a loop that needs to repeat some number of times, based on a condition. "While we haven't finished adding up this list of numbers, keep adding," for example.

Take a look at the following examples of while-loop programs, and identify the advantages and disadvantages of each.

3.b.i. Interactive loops

The interactive loop allows the user to approve a repeated process.

# Program to find the average of numbers # using an interactive loop sum = 0.0 # Make sure sum is real count = 0 keep_going = "Yes" while (keep_going == "Yes"): num = input("Enter a number: ") sum = sum + num count = count + 1 keep_going = raw_input("Keep going (Yes/No)?") print "You entered",count,"numbers" print "which have a mean of",sum/count

This loop works pretty well, but one of the problems is that it's annoying for a user to have to approve every iteration.

3.b.ii. Sentinel loops

One way of solving the problem of having to have a user repeatedly indicate that he/she wants to continue is by using a sentinel value. This value, when entered with the other numbers, will indicate to the loop that it should stop running.

# Program to find the average of numbers # using a sentinel loop sum = 0.0 # Make sure sum is real count = 0 num = input("Enter a number (<0 to quit): ") while (num >= 0): sum = sum + num count = count + 1 num = input("Enter a number (<0 to quit): ") print "You entered",count,"numbers" print "which have a mean of",sum/count

This loop works much more nicely... but it introduces a new problem: What if one of the numbers that I want to find an average of is negative?

Here's a new trick: have the user enter each number as a string:

# Program to find the average of numbers # using a sentinel loop sum = 0.0 # Make sure sum is real count = 0 num = raw_input("Enter a number, <Enter> quits: ") while (num != ""): sum = sum + eval(num) # eval function converts # a string to a number count = count + 1 num = raw_input("Enter a number, <Enter> quits: ") print "You entered",count,"numbers" print "which have a mean of",sum/count

This is the best version of this program yet.

3.b.iii. Using while loops to validate input

Your program will be more robust, and less fragile, if it attempts to validate input, making sure that the data coming in to the program is appropriate.

Not validating input makes your program easier to break, and in security applications, can be downright dangerous to your program, your user's data, and your computer.

Here are two quick examples of how you can use a while loop to validate a user's input after he/she has entered it.

# Program to validate input >0 positive_number = -1 # This is a "pre-seed" while (positive_number < 0): positive_number = input("Enter a number >0: ") print "Thanks for entering",positive_number,"!"

This next version of the program uses a loop that would repeat infinitely, except for the fact that—once we get the positive number that we're looking for—we use the break statement to break out of the loop.

# Program to validate input >0 while True: # This would be an infinite loop, but... positive_number = input("Enter a number >0: ") if positive_number > 0: break # Exits the loop print "Thanks for entering",positive_number,"!"

Homework

Read Chapter 8, Sections 8.1, 8.2, 8.3.1, 8.3.2; do Chapter 8 programming exercises #1, #5, (#7 optional).

4. Programming Project 2 - Craps

We are just about at a point where our projects are too big to fit into a single "program," and that's going to require a slight modification to our thinking about our programs. Before we jump into that, though, let's make a program that will allow the user to play craps on the computer.

4.a. More nano commands

For smaller programs, you're probably just fine using the arrow keys to move around in nano. Now that our programs are starting to get a little bigger, you should practice using some of the more advanced nano commands that will improve your efficiency in moving around the window.

More nano commands

  • ^a - "Control-a" takes you to the beginning of a line.
  • ^e - "Control-e" takes you to the end of a line.
  • ^w - "Control-w" finds where a specified text occurs.
  • ^\ - "Control-backslash" begins a Search-and-Replace process. Enter the text you want to search for and hit [Enter], then enter the text you want to use to replace the text you searched for and hit [Enter]. You'll then be given the option to replace individual occurrences of the searched text, or replace all, or Cancel the command.

4.b. Craps Assignment

Print out the Craps assignment. As before, draw on your printout, highlight important details and make a sketch, a flowchart, and/or pseudocode of your program.

Creating a good flowchart of your program is especially useful in determining how you will organize your code in terms of both loop structures and branching structures. It's all too easy to jump into coding before you have a real sense of how you're going to systematically solve your problem. So stop... take a moment to draw up a flowchart.

Compare your flowchart with mine. They don't have to look exactly the same, but they shouldn't be too far off from each other.

Once you think you have a good idea of what you want to do, open up a text editor and get coding!

Homework

Complete craps program, upload to server.

5. Strings

5.a. Basic Strings, Slicing, and Functions

The str (string) data type is used to work with alphanumeric text.

>>> print "Hello, world!"
>>> username = raw_input("Please enter your name: ")

Strings are simply a sequence of characters, and we can easily refer to them by their index, or position in the string.

Accessing a string via its indices is called slicing. The indices are referred to by enclosing them in square brackets [ ].

Note that the indices for the characters in a string start at 0, not 1. Thus, if password = "secret", password[1] is "e", not "s".

Predict what will be produced by each of the following statements.

>>> greet = "Hello, world!"
>>> print greet[1] # careful!
>>> print greet[0], greet[12]
>>> print greet[7:12]
>>> print greet[-1]
>>> print greet[0:4]
>>> print greet[7:]
>>> print greet[:5]
>>> print greet[1:-1]

In addition to splicing, there are a number of string operations that may be useful:

Predict what will be produced by each of the following statements.

>>> a_string = “Hello”; b_string = “world”
>>> print a_string + b_string # concatenation
>>> print 1 + b_string # careful!
>>> print 3 * b_string # repetition
>>> print len(b_string)
>>> for i in range(len(b_string),0,-1): ... print i, b_string[i] # This won't work--why?
>>> for i in range(len(b_string),0,-1): ... print i, b_string[i-1] # Ah! That's better!
>>> print b_string[::-1] # Tricky!

Of these operations, being able to determine the length of a string and being able to concatenate two strings are definitely among the most valuable.

It's also helpful to be able to do various conversions related to strings:

Predict what will be produced by each of the following statements.

>>> print "1" + "2"
>>> print eval("1" + "2") # careful!
>>> print eval("1") + eval("2")
>>> print eval(12) # will this work?
>>> print ord("b") # converts to ascii
>>> print chr(98) # converts from ascii

There are some other Built-In Functions that may be useful in working with string.

Predict what will be produced by each of the following statements.

>>> name = "jules verne"
>>> print name.capitalize()
>>> print name.title()
>>> print "DON'T SHOUT!".lower()
>>> print name.upper()
>>> print name.replace("jules","phileas")
>>> print name.split() # splits into a list # default separator is a space " "
>>> print "Wow. That's cool. Right?".split(".")
>>> print name.find("verne")
>>> print name.count("e")
>>> print " ".join(["i","love","you"]) # Joins a list # of items into a string # separated by " "

The built-in string functions in Python are certainly useful, but it helps to have additional functions. Soon, we'll learn how to import modules that other people have written, as well as learn how to write our own functions.

5.b. Formatting Output

Up to this point, we haven't worried very much about the format of our output—simple print statements have worked just fine.

If you do need to make your output look nice, or print data in columns, you can use Python's formatting operator, %.

You can specify the format of output as follows:

print "<formats>" % <values>

Some examples of how you can use formatting:

>>> print "***%6.2f***" % (math.pi) *** 3.14***

Here the "%6.2f" indicates that 6 columns total should be used to print a floating point number, with 2 places after the decimal point. The asterisks are just being used here to indicate the columns.

>>> name = "Richard" >>> print "%s!" % name Richard!

Here the "%s" indicates that name is a string that should be printed with an exclamation point directly after it.

>>> print "%s! Your # is %5d." % (name,42) Richard! Your # is 42.

Here the "%s" is used to print the string, while the %5d is used to print the number 42. There are 4 spaces between the word "is" and the 42: one space because there's a blank in the double quotes, and 3 spaces because we specified that the two-digit 42 should be printed in a total of 5 columns.

Note that there are a much wider variety of format possibilities available than what is listed here. See the Python documentation for further information.

Homework

Read Chapter 5, Sections 5.1-5.8; do Chapter 5 programming exercises #4, #5, #9.

6. Program Design Exercise

A user comes to you wanting a program that takes three numbers that she enters, and identifies the largest value.

Write the program.

6.a. "Compare each pair" solution

6.b. Multibranch "decision tree" solution

6.c. "Sequential comparisons" solution

6.d. Python max solution

6.e. List solution

Homework

Read Chapter 7, Section 7.5, 7.6. Read Chapter 11, Sections 11.1, 11.2

7. Lists

The list (called an array in most other programming languages) is an incredibly useful and powerful data type that you will learn to love.

7.a. Intro to lists

A list is a sequence of data values. Lists may be made up of any type of value: strings, ints floats, even other lists. Lists are indicated with square brackets enclosing the items in the list, which are separated by commas. Individual items in a list can be referenced by their index.

Examples:

  • my_fingers = [1,2,3,4,5,6,7,8,9,10]
  • my_data = ['Richard','White','626-845-1235',50]
  • my_friends = ["Robbie","Dana","Gary","Ruthie"]

What do you think the output will be for these statements?

>>> mylist = ["A","B","C","D","F"] >>> print mylist[2]
>>> print mylist[3:4] # careful!
>>> print len(mylist)
>>> print mylist[:]
>>> print mylist[::-1]

You can see that we can use some of the same tricks on lists that we used on strings.

7.b. Using lists

7.b.i. Iterating through a list

How are lists so powerful? Just as we've used a for loop to run through a range of numbers, we can easily set up a loop to run through a series of items in a list.

You could run through the items in the list this way:

>>> shopping_list = ["apples", "oranges", "bananas"] >>> for i in range(len(shopping_list)): ... print "I need to buy",shopping_list[i]

That's unnecessarily complicated, though. It's easier to do it this way:

>>> for item in shopping_list: ... print "I need to buy",item

Just as in a for loop with numbers, this loop will repeat: the first time through, item will represent the first piece of data in the list shopping_list ("apples"), the second time through it will be "oranges", and the third time through, "bananas".

In future programs, we'll quickly learn just how useful the list can be.

7.b.ii. Some list operations

Some of the more useful operations that can be performed with lists include:

  • listA + list_b - concatenates two lists into one
  • listA * <integer> - repeats a list a number of times
  • listA[n] - gets the item located at position n
  • listA[i:j] - slices a subset from the larger list
  • len(listA) - determines the length of a list
  • for j in listA: - iterate through the list
  • if (j in listA): - boolean, checks to see if an item is in the list

Write a program that asks the user to enter a word, and then tells them how many vowels there are in the word.

7.b.iii. Some list methods

List methods that you may find helpful include:

  • listA.append(x) - add an element to end of listA
  • listA.sort() - sort listA
  • listA.reverse() - reverse listA
  • listA.index(x) - find the first location of x in listA
  • listA.insert(i,x) - insert x into listA at index i
  • listA.count(x) - count how many occurences of x in listA
  • listA.remove(x) - remove the first occurence of x from listA
  • listA.pop(i) - returns element i from listA, and removes it from list. .pop() acts on the last item of the list.
Play with lists

Take a few moments to create some lists—of friends? sports teams? foods? bands?—and practice manipulating them: append items to your list, pop items from the list, print a slice of the list, sort the list, etc.

7.b.iv. Lists and Strings

You may find it useful to convert from strings to lists, or vice versa.

  • ','.join(myList) - takes the elements from myList and assembles them into a string, with each element separated by a comma. To just convert the list to a string without any separators, use ''.join(myList)
  • list(myString) - takes a string and converts it into a list of characters

Homework

Do Chapter 11, programming exercise #6, #11, and upload to server.

8. Using a Simple List

It's one thing to know about the concept of a list, and another to actually use it. Let's figure out how to write a simple but useful program that uses a list.

First, though, let's review the % (mod) operator.

8.a. The % (mod) operator

The mod operator returns the remainder from a whole-number division operation.

One obvious application for this operation is to determine whether one number is easily divisible by another.

Even or odd?

Write an if-statement to determine whether the integer stored in the variable n is even or odd.

Expanding on this idea:

Evenly divisible?

Write an if-statement to determine whether the integer stored in the variable n is evenly divisible by the integer stored in the variable x.

8.b. Finding primes

Based on what we know, write the following program.

A list of primes

Write a program that creates a table of the first million primes. Recall that a prime number is an integer (greater than 1) that is evenly divisible only by itself and 1.

Your program needs to print out the number of the prime, and next to it the value of that prime. Thus, the first few lines of output will be:

Prime # Prime Value 1 2 2 3 3 5 4 7

Your prime numbers should be stored in a list called "primes."

9. Sorting and Searching

Although we've just seen how Python has searching and sorting operations built into the language, it's instructive to consider algorithms that perform these operations, and build such algorithms ourselves.

We'll start out with the Selection Sort.

9.a. The Selection Sort algorithm

The Selection Sort algorithm works as follows:

  1. Begin with a list of unsorted items.
  2. Go through the list and find the smallest value.
  3. Place that value first in the list.
  4. Repeat, starting at 2nd position: go through list, find smallest item on list, and place it in 2nd position.
  5. Go through entire list in this fashion until done.

Let's write a Select Sort algorithm in Python.

SelectSort

Write a program that:

  1. creates a list of 100 items from random numbers between 1 and 1000, inclusive.
  2. applies a Select Sort to this list. Display the list onscreen as your program works.
  3. prints out the final sorted list.

Once you have the basic program working, consider ways in which you might improve its efficiency.

You can get some idea of how efficient your program works by determining how long it takes the system to run your code:

$ time python selectsort-whiter.py

A slightly more complex sorting algorithm is the Bubble Sort.

9.b. The Bubble Sort algorithm

The Bubble Sort algorithm works as follows:

  1. Begin with a list of unsorted items.
  2. Start with the first item in the list, and compare it with the one right after it. If the second item is smaller than the first, swap them. (At this point, the higher of the two items has been "bubbled" up in the list.)
  3. Continue on to the second item, and compare it with the third, swapping them as required like before. Continue through the entire list in this fashion. By the time you've passed through the list this first time, the highest value will have bubbled up to the end of the list.
  4. Repeat this process again, passing through the list and swapping items as necessary.
  5. Continue passing through the list in this fashion until no more swaps are performed. At this time the list is sorted.

Let's write a BubbleSort algorithm in Python.

BubbleSort

Write a program that:

  1. creates a list of 100 items from random numbers between 1 and 1000, inclusive.
  2. applies a Bubble Sort to this list. Display the list onscreen as your program works.
  3. prints out the final sorted list.

Once you have the basic program working, consider ways in which you might improve its efficiency.

You can get some idea of how efficient your program works by determining how long it takes the system to run your code:

$ time python bubblesort-whiter.py

A slightly more complex sorting algorithm is the Bubble Sort.

9.c. Searching

Okay, so we've got our lists of items sorted. How do you quickly go about finding something on the list? Just flipping through the list sequentially, starting with the first item and continuing until you get to the end doesn't seem very efficient, especially if you've got a very long list. (This is a legitimate search strategy—it's called a Linear Search.)

The Binary Search algorithm works as follows:

  1. Begin with a list of sorted items and a "search item" that you're looking for.
  2. Compare the search item with the item at the middle of the sorted list.
    • If the items match, you've found the location of that item!
    • If the search item is greater than the middle item of the list, the bottom half of the sorted list can be eliminated from consideration. The top half of the list will become our new search space.
    • If the search item is less than the middle of the list, the upper half can be eliminated, and the bottom half of the list will become our new search space.
  3. Continue searching through the smaller and smaller sections of lists until either the search item is found, or it is not found.

The Binary Search can be tricky to implement. Challenges include identifying the middle of a list of an even number of items, and keeping track of upper- and lower-bounds of the search space.

There are also more sophisticated concerns, like "what happens if you have a billion items to search through?" Large lists like this can tax an algorithm, and even the experts can get tripped up.

BinarySearch

Write a program that:

  1. creates a list of 100 items from random numbers between 1 and 1000, inclusive, and imports one of your Search programs as a module to sort the list, or asks the user to enter a list of numbers (useful for testing).
  2. asks for a search item (a number between 1 and 1000).
  3. performs a Binary Search for that item in your list, displaying the results as it goes.
  4. Print out the location of the search item, if it exists. Otherwise, print out a "search item not found" message.

Test your program with the following lists to see if it works. When testing your program, be sure to look for an item that is on the list, and also an item that isn't on the list.

  • [1, 3, 7, 8, 9]
  • [1, 3, 7, 8, 9, 11]