Python

Computer Programming for Computer Scientists Quick Start

General Information

Instructor: Ilkka Kokkarinen, ilkka.kokkarinen@gmail.com

Schedule: Mon-Thu for two weeks, for a total of eight days and 32 hours. Each day first has 2 hours of lecture and then 2 hours of lab.

Goal: To become familiar with computer programming and the Python programming language, allowing the computer science majors enrolling in this course to better succeed in the computer science courses during the following freshman year and beyond.

Material: The course material consists of a bunch of Python example programs developed by the instructor that are used as lecture notes and examples. In addition, the students can read the official Python 3 Tutorial, and consult the Python 3 Library Reference wherever instructed to do so. Two excellent Python textbooks that can be read free online are “Dive Into Python 3” and “Think Python: How To Think Like Computer Scientist”.

Download: The students might want to download and install Python on their home computers and laptops. Note that since this course uses Python 3 that differs in a couple of important places from the older (although currently more widely used) Python 2, that is the one you should download. Windows, Linux and Mac users can all find the Python 3.2 download links at the official Python download page.

Outline

Since this course is taught the first time this summer, I really can’t say exactly what our pace covering the following topics is going to be, and how these examples and labs will split over the eight days. Each day, we will simply cover whatever material we can in a convenient and natural pace, and see how this turns out in the end.

For convenience, here are the following example programs in a single archive: PythonExamples.zip

first.py Introduction to Python language and its statements. Declaring variables, assignment. Namespaces in Python. Basic numerical and text data types. Basic input and output. Formatted output. Type conversions. Doing calculations with Python. Importing functions from libraries defined elsewhere. Functions versus methods.
listdemo.py The basic list data type of Python. Indexing and slicing a list. Basic list manipulation operations.
iteration.py Iterating over the elements of a list. Defining lists with list comprehensions.
tuples.py Tuples, immutable lists. Sets and dictionaries. Defining, accessing and manipulating tuples, sets and dictionaries.
ifdemo.py Making decisions in Python. Nested and laddered decisions. Equality and order comparison operators. Creating complex decisions with logical operators and, or and not. The constants True and False. Making complex decisions based on a dictionary.
whiledemo.py The general-purpose while-loop of Python. Loops that need to run an unknown number of times. Solving computational problems with said loops. Random numbers in Python.
exceptiondemo.py When unexpected things happen to good programs. Raising exceptions and handling them. Using exceptions as a control structure. Explicit iteration of lists.
defdemo.py Defining your own functions. Making a function call versus referring to that function. Default arguments for functions. Named keyword arguments. Handling arbitrary arguments and keyword arguments in a function.
bankaccount.py Object-oriented programming in Python. Defining your own classes, and methods in them. The important parameter self. Data fields in classes and objects. Creating and using objects. Special methods that allow your class to seamlessly work with arithmetic and other built-in mechanisms of the Python language.
cards.py More on object-oriented programming in Python. Data fields and methods meant to be private. Extending an existing class into a specialized subclass type.
spellcheck.py Reading and analysing large text files. Analysing, searching and splitting strings with regular expressions.
functional.py Thinking of functions as data objects. Writing meta-functions that take functions as parameters and create and return functions as results. Writing generators in Python. Finite and infinite generators. Function objects. Memoization. Defining and using small anonymous lambda functions.
recursion.py Thinking about problems recursively. Expressing and solving a problem based on smaller instances of the problem. Searching with recursion.

The files english.txt and warandpeace.txt are needed with some examples.

Lab Exercises

Here are the exercises to be done in the lab each day. As this course is not graded, just do as many as you can in your own pace, and there is no point cheating. The problems are not listed in order of difficulty or complexity.

(after first.py)

Use the interactive Python prompt to solve the following math word problems. Define the necessary quantities as variables before using them in the formula that gives you the asked result, so that this formula doesn’t have any numerical values in it, only your variables and some basic arithmetic that combines them to produce the result. (a) If a bucket has a capacity to hold 5 gallons of water, and you have 15 buckets, how much water can you keep in them? (b) If your car can get 15 miles per gallon, and you drive 55 miles per hour, how many hours can you drive with 10 gallons of gas in the tank?
Next, write a Python program (so do not use the interactive prompt) that asks the user to enter the age of a dog in years, and then outputs the equivalent age in human years (dog years times seven).
Write a program that asks the user to enter the width and the height of a rectangle, and then outputs the perimeter length and the area of that rectangle.
Write a program that asks the user to enter the number of cows and the number of chickens that are currently in the barnyard (you need to use two separate input statements here), and then outputs the total number of legs that can be found in the barnyard.
Write a conversion program that asks the user to enter an amount of money in Canadian dollars, and then outputs the equivalent amount in American dollars and Euros. (Look up the current conversion rates online.) Use the format method of the output string to nicely place these converted amounts into their proper places in the output.
Python comes “batteries included” so there is no need to reinvent the wheel that is already rolling smoothly. Let us practice importing and using functions defined in a pre-existing library. First, read the library documentation of the random library for generating random numbers (which are useful in many games and serious programs) and import the library functions to the interactive environment by typing from random import * , after which you should try generating three random numbers from the normal distribution with the mean of 100 and standard deviation of 15.
Next, look at the library documentation of datetime library that defines two classes date and timedelta that we use here. Define two datetime.date objects today and dob, corresponding to today and your date of birth. Compute the difference today - dob (the result will be an object of the type datetime.timedelta used to represent lengths of periods of time without a fixed start point) and find out how many days old you are. What day in the future will you be exactly twice as old as you are today? (Hint: to find this out, add two times your timedelta age to your date of birth.)
For further handling and analysis of dates, see the library documentation of the calendar library. Use its functions to find out the weekday of your birthday, and then output the calendar for this month and this year.
For measuring how much time it takes for the computer to do something, the library time (documentation) defines a function time() that returns the number of seconds that have elapsed since the epoch, which is computer-dependent but usually the start of the year 1970. So it’s a pretty huge number by now, and grows by one every second. However, after importing the time library, write the statement starttime = time.time() to the Python interactive environment. What statement would you now use to find out how many seconds have elapsed since the moment you entered in that previous statement?

(after listdemo.py and iteration.py)

Write a program that asks the user to enter a positive number n. After that, your program should count down from n to zero, outputting each value on the console on a separate line, and finally after the zero, output the text “Liftoff!”
Write a program that first defines a to be a list of ten numbers (just make up some ten numbers randomly). Then your program should, using the list iteration with for, output the elements of a on the console, one number per line.
Continue the previous program so that it defines the list b to contain precisely the numbers in a that are greater than 42. Initialize b to [], and then use the for iteration to go through the elements of the original list, using append to append them to b if they are greater than 42.
Redo the previous question, but now use list comprehension instead of for iteration. Which way do you like better?
Now consider the numbers in your list a to be Celsius temperatures. Use list comprehension to create another list that contains these same temperatures in Fahrenheit, except that all the negative temperatures (in Celsius) are filtered out.
Write a for-loop that goes through your list a and calculates the average of its values (call this quantity avg), and the average of the squares of its values (call this quantity avgSq), and finally outputs the value of the expression avgSq - avg*avg, which is the variance of the elements in the list.
Write a for-loop that finds the element in a whose difference to its previous element is the largest, and outputs that element. For example, if called with the parameter list [4,2,7,9,1,5], the loop would output 7.
The basic for-loop just goes through the elements of the list one at the time. Sometimes we want to do more complicated iteration. The standard library itertools is a big help here. First read the library documentation for itertools, and try going through the results of the functions product, permutations and combinations on some simple lists to see how these functions work.
Write a program that asks the user for a positive integer n, and then outputs all the permutations of the numbers 1, 2, …, n. The previous itertools library is a big help here. Try out your program with n=4.
Let dict be a dictionary { “Tom”:42, “Bob”:35, “Tina”:50, “Jane”:27 }. Recall that dictionaries have a method items() that returns a list of key-value pairs in the dictionary. How would you create a dictionary that is the reverse of the original dictionary in that it maps the original values to keys instead of keys to values? (For example, in your new reverse dictionary the key 42 should be mapped to value “Tom”.) Can you see any trouble ahead of using this technique with some other dictionaries?

(after ifdemo.py and whiledemo.py)

Write a program that asks the user to enter three numbers a, b and c. The program will then output the median of these three values: not the minimum or the maximum number, but the one that is in the middle.
Write a program that asks the user to enter the lengths of three sides of a triangle. Your program then checks if these lengths could logically be possible lengths of triangle sides, that is, they are all positive, and the sum of any two of them is greater than the third one. If this is not the case, ask the user to enter these lengths again.
Go visit the Ryerson grade scales page and look up the letter grade table for science and engineering. Write a program that asks the user to input the numerical grade, and outputs the equivalent letter grade. An if-else ladder is probably the easiest solution here, but there are other more concise and sophisticated ways, such as using a list of tuples of grades and lower bounds such as (“B”, 70) listed in sorted order descending on value, and then looping through this list to find the first tuple whose number part is less than equal to the given grade.
Write a program that keeps asking the user to enter numbers until the user enters a zero. Collect these entered numbers (not including the zero) into a list, and then output precisely the elements that are greater than the average value in the list. Could every student in Lake Wobegon High really be above average?
In a simple physics simulation, the ball thrown straight up in a vacuum under Newtonian gravity g (for Earth, g = 9.80655) has a position y that is initially 0, and a velocity vy that your program should first ask the user. Time t starts at zero. Your program should run in a while loop that, as long as either quantity y or vy is positive, increases t by 0.001, increases y by vy * 0.001, and decreases vy by g * 0.001. When the loop terminates, it should output how long it took for the ball to come to the ground. How long will your ball fly when given the initial upwards velocity of +10.0?
An office worker initially has uh umbrellas at home and uo umbrellas at the office. Every morning he walks from home to office, and every evening he walks back from office to home. For his each walk, it rains with probability 40% independently of other walks. If it rains, the man takes one umbrella from wherever he leaves from, and then leaves this umbrella to wherever he goes to. How many days will this man stay dry so that he doesn’t walk in the rain without an umbrella? Run the program a couple of times and tabulate the results.
Write a program that asks the user for two numbers m1 and m2 and the standard deviation sd. The program should then create two lists of numbers, each consisting of 1000 random numbers drawn from the normal distributions (m1, sd ) and (m2, sd ) (use the function normalvariate in the library random), and sort both lists. The program should then create third list results the following way: whichever of these two lists is currently headed by a larger number, pop that out and add it to results. Do this 100 times, as you also keep track of how many numbers you have taken from each list. For parameters m1=90, m2=110 and sd=15, how many numbers end up taken from the second list?
Three positive integers a, b, c are called a Pythagorean triple if a2 + b2 = c2. Find the only Pythagorean triple for which a + b + c = 1000. You can simply use brute force to go through all possible combinations of a, b and c between 1 and 1000, check if the triple satisfies the requirement, and break out of the loop once you find the solution.
Last, look at the library documentation page for hashlib that contains classes for computing a secure message digest for given text, using various algorithms. Write a program that first creates an md5 digestor, then reads the file warandpeace.txt one line at the time (see near the end of the example iteration.py for how to read text files one line at the time), and updates the current digest by each line. When the entire file has been read, your program should output the md5 digest that it computed for this file.

(after defdemo.py)

Write a function stutter(seq) that creates and returns a list that contains the same elements as the parameter sequence seq, but each element is duplicated. For example, if this function is called with the parameter list [1,2,3], it would create and return the list [1,1,2,2,3,3]. Your function should not modify the original sequence.
Write a function everyother(seq) that creates and returns a list that contains the elements in the even-numbered locations of the sequence seq. For example, if this function is called with the parameter [1,2,3,4,5,6,7], it would return the list [1,3,5,7].
Write a function dotproduct(s1, s2) that gets as parameters two sequences s1 and s2, assumed to be of the same length (let us here denote this length by n). Your function should compute and return the scalar sum s1[0]*s2[0] + s1[1]*s2[1] + … + s1[n-1]*s2[n-1], called the dot product of these sequences.
Write a function ispalindrome(seq) that returns True if its parameter sequence seq is a palindrome, that is, the same read from left to right and right to left. For example, “rotator”, [1,8,-3,-3,8,1] and [7, 4, 7] would be palindromes.
Write a function isvowel(c) that returns True if the parameter c is a character that is a vowel (aeiouAEIOU), and returns False otherwise.
Continue the previous program by defining a function disemvowel(s) that creates and returns a string that is otherwise the same as the parameter string s, but with all its vowels removed. For example, if this function is called with the parameter “Kokkarinen”, it would return the string “Kkkrnn”. (Hint: initialize a result to empty string, then loop through the characters of s, and for each character, add it to result if it is not a vowel, and otherwise ignore it.)
The Hamming distance between two sequences s1 and s2, assumed to be the same length, is the number of locations in which these two lists have different elements. Write a function hamming(s1, s2) that computes and returns the Hamming distance of sequences s1 and s2.
The falling power operation fp(b, n) is defined as the product b * (b-1) * … * (b-n+1). For example, the falling power fp(10, 4) = 10 * 9 * 8 * 7 = 5040. Write the function fp(b,n) to calculate the falling power of b and n. If b < 1, the function should return 1.
Write a function runningmax that gets a sequence of numbers as a parameter, and creates and returns a list of the same length whose each element equals the maximum of the elements of the original list up to that point. For example, if the function is called with the parameter [1,4,2,6,3,8,5], it would create and return the list [1,4,4,6,6,8,8].
In the famous subset sum problem, you are given a list of numbers and a goal, and your task is to find a subset of these numbers that together add up to the goal, or report that no such subset exists. For example, if the list is [4,7,10,11,18,21,30] and the goal is 55, the subset [7,18,30] would be one possible answer. Write a function subsetsum(numbers, goal) that returns True if numbers contains such a subset, and False otherwise. (Hint: function combinations in the itertools library is a big help here. First check all the subsets of size 1, then all the subsets of size 2, and so on, until you either find a solution or try out every possibility without finding one.)

(after bankaccount.py and cards.py)

To practice object-oriented programming, let us start with the classic vending machine example. Define a class VendingMachine whose objects remember how many bottles of pop they currently contain (this quantity is initialized at the object creation), and how many dollars users have inserted in them. Define the methods insertDollar that adds one dollar in the machine, and a method buyPop that, if there is at least one dollar in the machine, gives out a bottle of pop (output a suitable message such as “A can of pop comes out of the machine”) and decreases the dollar count. Otherwise the method should output the message that you need to put in money first.
Next, to practice inheritance, define a superclass Animal and its three subclasses Horse, Cow and Chicken. In each of these four classes, define the __init__ method so that it outputs a message saying that it is the init method of the said class. In each subclasse, define a method getlegs that returns the number of legs that animal has. Create a list that contains two animal objects of each kind, and write a loop that computes and outputs the total number of legs of the animals in your list.
Define a class Particle whose each instance has two data fields x and y, the current numerical coordinates of the particle. Define the __init__ method so that it initializes x and y to the values given to it as parameters, and the method __str__ so that it returns a string that contains the coordinates of the particle. Then write a method move that when it is called, it adds a random number from [-1,1] separately to both x and y.
Write a class ParticleField whose each instance contains a list of 1,000 particles, their coordinates randomly initialized in the range [-10,10]. Write a method moveall(n) that when called, calls the move method n times for every particle in its list.
In the class ParticleField, write another method getXmax that goes through the list of particles and finds the minimum and maximum values for the x coordinate there, returning both of them as a tuple. Write a similar method getYmax.
A functionoid is an object that can be directly called as if it were a function. (Then again, if it walks like a duck...) To make your object a functionoid, simply define the method __call__ in that class. Write a class Accumulator whose functionoid objects initially contain the value 0, and each time that they are called as functions, they add their parameter to their current value, and return that new current value. For example, after the assignment a = Accumulator(), the call a(10) would return 10, after which the call a(10) would return 20.

(after functional.py and recursion.py)

The harmonic sum Hn is defined as the sum of the first n reciprocals of unity, that is, Hn = 1/1 + 1/2 + 1/3 + … + 1/n. Write a generator that produces the infinite series H1, H2, H3, … , and output its first 50 terms.
Write a generator for the Fibonacci series 1,1,2,3,5,8,13,21,... where each number equals the sum of the two previous numbers. Your generator should remember the last two numbers it has so far yielded (initially 1 and 1) and then always add those up compute the next number in the series, and yield that. (Can you use your generator to find the first Fibonacci number that has more than 1000 digits?)
Read the library documentation page for the functools library that defines handy functions to manipulate functions. Using reduce with lambdas, write the functions mysum(a) and mymax(a) that compute and return the sum of elements and the largest element in the list a, respectively.
Let us go back to the itertools library and look at some of the useful functions there. First, you define an infinite generator powersof2 that yields the values 1,2,4,8,16,32... Then, use the function takewhile to create a list of powers of two that are less than one billion. Write the first parameter to takewhile as a lambda.
Use the itertools function dropwhile to create an infinite generator of powers of two that are greater than one billion. Output the first ten such powers on the console.
itertools has useful functions that take an iterator and give you another iterator based on that. However, we can still write additional ones. Write a generator groupiterator(it, n) that returns the elements from it in chunks, each chunk a list of n elements, except the elements in the end are given as one chunk of however many elements there are. For example, when applied to list [1,2,3,4,5,6,7] with n=3, the resulting iterator would first yield the list [1,2,3], then yield the list [4,5,6], and then finally yield the list [7].
Define a function selfapply(f) that calls its parameter function f by passing the function f itself as its parameter. What happens if you make the call selfapply(selfapply) ? Why?