# Code Developed in CSCI-1100 Spring Semester 2016¶

## Lecture 1¶

**Module:** `lec01_three_doubles`

— Finds three consecutive pairs of double letters¶

Find all words containing three consecutive pairs of double letters in a file of all English words located at:

**Modules used:** `urllib`

**Author**: Sibel Adali <adalis@rpi.edu>, Chuck Stewart <cvstewart@gmail.com>

**Returns:** All words matching condition and the count of found words

**Pseudo Code**:

```
open the file from the web with all the words in English
for each word in the file:
for all positions l in the word
if the letters at positions (l and l+1) are the same
and the letters at positions (l+2 and l+3) are the same
and the letters at positons (l+4 and l+5) are the same then
output word and increment the count
```

**Code**:

```
""" Find all words containing three consecutive pairs of double letters
in a file of all English words located at:
http://www.greenteapress.com/thinkpython/code/words.txt
**Modules used:** :py:mod:`urllib`
**Author**: Sibel Adali <adalis@rpi.edu>, Chuck Stewart <cvstewart@gmail.com>
**Returns:** All words matching condition and the count of found words
**Pseudo Code**::
open the file from the web with all the words in English
for each word in the file:
for all positions l in the word
if the letters at positions (l and l+1) are the same
and the letters at positions (l+2 and l+3) are the same
and the letters at positons (l+4 and l+5) are the same then
output word and increment the count
"""
import urllib
def has_three_double(word):
""" Returns True if the word contains three consecutive pairs of
double letters and False otherwise.
"""
for l in range(len(word)-5):
if word[l] == word[l+1] and \
word[l+2]==word[l+3] and \
word[l+4]==word[l+5]:
return True
return False
# Comments that fit in a single line can be put in this format.
# Anything after a single pound sign is ignored.
# The main body of the program starts here
word_url = 'http://www.greenteapress.com/thinkpython/code/words.txt'
word_file = urllib.urlopen(word_url)
count = 0
for word in word_file:
word = word.strip().strip('\n')
if has_three_double(word):
print word
count = count + 1
if count == 0:
print 'No words found'
elif count == 1:
print "1 word found"
else:
print count, 'words were found'
```

## Lecture 3¶

**Module:** `lec03_raw_input`

— Demonstrate the use of raw_input in the volume calculation code.¶

**Code**:

```
"""
Write a program to
read the dimensions of a rectangular prism,
compute the surface area and volume, and
print them.
"""
length = float(raw_input("Enter the length of the rectangular prism ==> "))
width = float(raw_input("Enter the width of the rectangular prism ==> "))
height = float(raw_input("Enter the height of the rectangular prism ==> "))
area = 2 * (length*width + length*height + width*height)
volume = length*width*height
print "Rectangular prism with length %.3f, width %.3f, height %.3f" %(length, width, height)
print "Area %.3f, Volume %.3f" %(area, volume)
```

## Lecture 4¶

**Module:** `lec04_exercise_set_1`

— Demonstrate the use of some string functions for parts 3 and 4.¶

**Code**:

```
name2 = "Rensselaer Polytechnic Institute"
##a -> 1, e->a, 1->e
name2 = name2.replace("a","1")
name2 = name2.replace("e","a")
name2 = name2.replace("1","e")
print name2
word = 'Bring back the swarm'
word = word.title()
word = word.replace(" ", "")
word = "#" + word
print word
word = 'Bring back the swarm'
word = "#" + (word.title()).replace(" ","")
print word
```

**Module:** `lec04_exercise_set_2`

— Demonstrate the use of the math module¶

**Code**:

```
"""
Write a program to
read radius of a circle in float
compute its area and
print it.
"""
import math
radius = raw_input("Radius ==> ")
radius = float(radius)
## or
## radius = float(raw_input("Radius ==> "))
area = math.pi * radius**2
print "The area of a circle is:", area
print "The area of a circle is: %.2f" %area
```

**Module:** `lec04_cylinder`

— Demonstrate the use of some math modules to compute the area and volume of a cylinder.¶

**Code**:

```
""" Author CS-1 Staff
Purpose: This program reads radius and height
of a cylinder and outputs the area and volume.
"""
import math
# This is a comment
print "Computing the area and volume of a cylinder"
radius = float(raw_input("Enter radius ==> "))
height = float(raw_input("Enter height ==> "))
area = 2*math.pi*radius*height + 2*math.pi*radius**2
volume = math.pi*radius**2*height
print "Area is %.2f" % area
print "Volume is %.2f" %volume
```

**Module:** `lec04_triangle`

— Class exercise to calculate the hypotenuse of a right triangle¶

**Code**:

```
""" Author CS-1 Staff
Purpose: This program reads the lengths a and b
of the sides of a right triangle and outputs the
hypotenuse.
"""
import math
print "Computing the hypotenuse of a right triangle"
a = float(raw_input("Enter side a ==> "))
b = float(raw_input("Enter side b ==> "))
c = math.sqrt(a**2 + b**2)
print "Hypotenuse is %.2f" % c
```

## Lecture 5¶

**Module:** `lec05_surface_area`

— Use two functions to compute surface area¶

**Code**:

```
'''
Demonstrate the writing and use of two functions that compute the area
of a circle and the surface area of a cylinder.
'''
import math
def area_circle(radius):
return math.pi * radius ** 2
def area_cylinder(radius,height):
circle_area = area_circle(radius)
height_area = 2 * radius * math.pi * height
return 2*circle_area + height_area
print 'The area of a circle of radius 1 is', area_circle(1)
r = 2
height = 10
print 'The surface area of a cylinder with radius', r
print 'and height', height, 'is', area_cylinder(r,height)
```

## Lecture 6¶

**Module:** `lec06_height`

— Use if statements to compare height¶

**Code**:

```
""" Author: CS1 Staff
Simple program to demonstrate an if statement.
"""
name1 = "Dale"
height1 = int(raw_input("Enter the height of %s in cm ==> " %name1))
name2 = "Erin"
height2 = int(raw_input("Enter the height of %s in cm ==> " %name2,))
if height1 < height2:
print "%s is taller" %name2
max_height = height2
elif height1 > height2:
print "%s is taller" %name1
max_height = height1
else:
print "%s and %s have the same height!" %(name1, name2)
max_height = height1
print "The max height is %d" %max_height
```

## Lecture 7¶

**Module:** `lec07_ex1`

— First image example: resize and convert¶

**Code**:

```
from PIL import Image
filename = "chipmunk.jpg"
im = Image.open(filename)
print '\n' '********************'
print "Here's the information about", filename
print im.format, im.size, im.mode
im.show()
gray_im = im.convert('L')
scaled = gray_im.resize( (128,128) )
print "After converting to gray scale and resizing,"
print "the image information has changed to"
print scaled.format, scaled.size, scaled.mode
scaled.show()
scaled.save(filename + "_scaled.jpg")
```

**Module:** `lec07_ex2`

— Second image example: crop and paste¶

**Code**:

```
from PIL import Image
im = Image.open("lego_movie.jpg")
w,h = im.size
## Crop out three columns from the image
## Note: the crop function returns a new image
part1 = im.crop((0,0,w/3,h))
part2 = im.crop((w/3,0,2*w/3,h))
part3 = im.crop((2*w/3,0,w,h))
## Create a new image
newim = Image.new("RGB",(w,h))
## Paste the image in different order
## Note: the paste function changes the image it is applied to
newim.paste(part3, (0,0))
newim.paste(part1, (w/3,0))
newim.paste(part2, (2*w/3,0))
newim.show()
```

## Lecture 9¶

**Module:** `lec09_overview`

— Some basic while loop constructs¶

**Code**:

```
"""
This is a general program for practicing different loop
methods. The following are examples of:
1. Loops that count up or down, loops that end
Loop block
Printing (print all on one line)
Changing a list (make upper case)
Accumulate a value
Count by 1, 3 (print three in a line, check
for three letters in a word, ending conditions?)
Is it true that there are two consecutive repeated letters?
Count all farmer's markets in Albany
2. Loops that are undeterministic
Depends on an external condition
(while user does not say stop)
------ WE will continue with these the next time
Depends on a complex condition
(while found or end of list, farmer's market)
3. Double loops
Find all possible pairs of agents
Find pairs of agents with the same first letter in their name
"""
months = ['jan', 'feb', 'mar', 'apr', 'may', 'jun', \
'jul', 'aug', 'sep', 'oct', 'nov', 'dec']
agents = ['skye','may','fitz','simmons','caulson',\
'hunter', 'mack', 'morse', 'triplett', \
'hartley', 'deathlok', 'koenig', \
'gonzales', 'fury']
word = 'bookkeeper'
i=0
while i< len(months):
print "Month: %d is %s" %(i+1, months[i].capitalize() )
i += 1
print months
print
print agents
## Capitalize the values in list "agents"
i=0
while i < len(agents):
agents[i] = agents[i].capitalize()
i += 1
## Check if capitalized
print
print agents
##Count how many agents have first names that start with S
##Accumulation of values
i = 0
cnt = 0
while i < len(agents):
if agents[i][0] == 'S':
cnt += 1
i += 1
print "%d agents with first name starts with 'S'" %cnt
##Find if there any agents who name starts with F
##Print Yes if any agent with such name, No otherwise
i = 0
found = False
while i < len(agents):
if agents[i][0] == 'F':
found = True
i += 1
if found:
print 'Yes'
else:
print 'No'
print
print "This is a loop that counts up to 7"
i = 0
while i < 7:
i += 1
print i
print
print "This is a loop that counts 10 down to 1"
i=10
while i > 0:
print i
i -= 1
print
print "This is loop that counts by 2, starting with 1 and ending with 19"
i = 1
while i <= 20:
print i
i += 2
```

**Module:** `lec09_user_stop`

— Stop a while loop based on user input¶

**Code**:

```
""" This program shows how to write a loop that ends
on a given user input. So, we must make sure that
while loop executes once initially and also that we
set the conditions that would stop the loop manually
when the correct input is given.
"""
### write a loop that reads user input, until the
### user types stop
finished = False
while not finished:
cmd = raw_input("Enter a command (stop to stop) => ")
if cmd == 'stop':
finished = True
```

**Module:** `lec09_co2`

Use a while loop to process a list¶

**Code**:

```
"""
Illustrating while loops with the CO2 example
"""
co2_levels = [ (2001, 320.03), (2003, 322.16), (2004, 328.07),\
(2006, 323.91), (2008, 341.47), (2009, 348.92),\
(2010, 357.29), (2011, 363.77), (2012, 361.51),\
(2013, 382.47) ]
"""
First example, sum
"""
i=0
sum=0
while i< len(co2_levels):
sum += co2_levels[i][1]
i += 1
print
print "Total co2_levels is", sum
"""
Reverse order
"""
i=len(co2_levels)
while i > 0:
i -= 1
print "Year", co2_levels[i][0], \
"CO2 levels:", co2_levels[i][1]
"""
Levels above 350
"""
print
i=0
num = 0
while i < len(co2_levels):
if co2_levels[i][1] > 350:
num += 1
i += 1
print "%d years had CO2 levels greater than 350" % num
"""
Percent change
"""
print
i=1
num = 0
while i < len(co2_levels):
percent = 100 * (co2_levels[i][1] - co2_levels[i-1][1]) / co2_levels[i-1][1]
print "Percent change from %d to %d was %.2f" % (co2_levels[i-1][0], co2_levels[i][0], percent)
i+=1
"""
Levels that went down
"""
print
i=1
num = 0
while i < len(co2_levels):
if co2_levels[i][1] < co2_levels[i-1][1]:
print "From %d to %d CO2 levels went down" % (co2_levels[i-1][0], co2_levels[i][0])
i+=1
```

## Lecture 10 (carry over from Lecture 9)¶

**Module:** `lec10-closest`

Find the two closest values in a list¶

**Code**:

```
'''
Purpose: Demonstrate the use of nested loops to find the two closest values in a list.
This could also be implemented - probably better - using for loops. The values
are stored in a list L, but in practice it would be better to input them from the user.
Author: Chuck Stewart
Date: March 3, 2016
'''
L = [34, 21, 12, 78, 28, 61 ]
# Initialize two variables to hold information about the minimum. The
# first is a tuple holding the indices of the two closest values. The
# second is the minimum distance. These values are initialized from the
# first two values in the list.
min_pair = (0,1)
min_dist = abs( L[0] - L[1] )
# In order to test each possible pair of indices, the index of the first
# component of the pair must start out 0.
i = 0
while i<len(L):
# The second index starts out at i+1 and runs through the end of
# the list.
j=i+1
while j < len(L):
dist = abs(L[i]-L[j])
# If the distance between the current pair of points is less than
# the current minimum, we have a new minimum pair
if dist < min_dist:
min_pair = (i,j)
min_dist = dist
j += 1
# This is outside the inner while loop so that i is incremented after
# the inner while loop ends.
i += 1
closest_i = min_pair[0]
closest_j = min_pair[1]
print "Closest values are %d and %d at indices %d and %d."\
%(L[closest_i], L[closest_j], closest_i, closest_j)
```

## Lecture 11¶

**Module:** `lec11_walk.py`

Turtle performs a random walk¶

**Code**:

```
'''
Lecture 11 Example of a Random Walk
This code was started in class on March 7 and completed on March 10.
It simulates a random walk by turtle who in each time unit randomly
takes a step to the left or a step to the right until it falls off.
This is represented by creating a board of n spaces and starting the
turtle in space n/2. A step to the left decreases the turtle
position. A step to the right increases the turtle position.
The simulation is run with a delay between each step so we can watch
what is happening. Without this delay, the board would print too
fast.
'''
import random
import sys
import time # so that we can delay
def print_board( steps, n, turtle_pos):
'''
Print the board with the current turtle position on it. This assumes the turtle
position is at least 0 and less than n.
'''
board = '_' * turtle_pos + 'T' + '_'*(n-1-turtle_pos)
print "%4d: %s" %(steps, board)
def take_step( n, turtle_pos ):
'''
Take a step, return turtle tuple with the new position, and False if
turtle fell off
'''
ran_value = random.random()
if ran_value < 0.5:
''' Step to the left '''
turtle_pos -= 1
else:
''' Step to the right '''
turtle_pos += 1
fell_off = turtle_pos < 0 or turtle_pos >= n
return (turtle_pos, fell_off)
if __name__ == '__main__':
''' Read the input and check to make sure it is a positive integer '''
n = raw_input('Enter the board size for the turtle walk => ')
if not n.isdigit():
print 'Need a positive number'
sys.exit()
n = int(n)
print n
''' Initialize the turtle position in the middle and print the board. '''
turtle_pos = (n-1)/2
print_board( 0, n, turtle_pos )
''' Run one step at a time until the turtle falls off the board. '''
fell_off = False
steps = 0
while not fell_off:
(turtle_pos, fell_off) = take_step( n, turtle_pos )
steps += 1
if not fell_off:
print_board( steps, n, turtle_pos )
time.sleep(0.1) # delay by the given number of seconds so we can see what is happening
print 'The turtle fell off after', steps, ' steps.'
```

## Lecture 13¶

**Module:** `lec13_scores`

Read scores and output them in decreasing order¶

**Code**:

```
'''
Read a file of scores, with one score per line, and output them
in order from greatest to smallest.
'''
f = open('scores.txt')
scores_list = []
for line in f:
score = int(line)
scores_list.append( score )
scores_list.sort()
# Reverse the list and then output it
scores_list = scores_list[::-1]
for i in range(len(scores_list)):
print "%d: %3d" %(i,scores_list[i])
'''
# As an alternative to reversing the list we can
# index from the end of the list.
for i in range(len(scores_list)):
print "%d: %3d" %(i, scores_list[-1-i])
'''
```

**Module:** `lec13_legos`

Read and format a legos file¶

**Code**:

```
'''
Exercise from Lecture 13 on parsing a legos file and putting it into the form
we expected from HW 4.
For example, if legos.txt has the following three lines:
2x1, 2
2x2, 6
4x2 , 3
Then at the end of the following, the legos list will be
['2x1', '2x1', '2x2', '2x2', '2x2', '2x2', '2x2', '2x2', '4x2', '4x2', '4x2']
When we developed this in class, we added a bit of complexity and tested it as
we went. This included making some mistakes. At the end we have the following
completed solution. Notice that the legos += ... statement can be replaced
by the for loop that is commented out...
'''
lego_f = open('legos.txt')
legos = []
for line in lego_f:
line = line.split(',')
block = line[0].strip()
count = int(line[1])
'''
for i in range(count):
legos.append(block)
'''
legos += [block]*count
print legos
```

## Lecture 14¶

**Module:** `lec14_yelp`

Read and parse Yelp data¶

**Code**:

**Module:** `lec14_counts`

Two different approaches to counting scores¶

**Code**:

```
'''
Lecture 14
Spring 2016
Prof. Chuck Stewart
Here are two different solutions to the problem of counting the number
of occurrences of each integer in an input sequence of integers. These
are the implementations of two of the four solutions we came up with
in class.
I have rearranged the code into functions, with one function
implementing one solution. Of course, if you were in class you noted
(and in many cases participated in) the development of the solutions,
involving several steps of writing the code, testing it, and refining
it. What you see here is just the final product.
'''
def print_scores_v1( scores ):
'''
The first solution finds the minimum and maximum scores, and then
counts each score in this range, only outputting the scores with
non-zero counts. This is short and easy to write, but it only
works well when the scores are not widely distributed. For
example, if there were only two scores, 0 and 1,000,000, this
would be a very slow solution.
'''
''' Preliminary output. Not necessary for the solution. '''
print 'Min score', min(scores)
print 'Max score', max(scores)
print 'Length', len(scores)
''' Generate and print a count for each score '''
print '\nVersion 1 output:'
for score in range(min(scores), max(scores)+1 ):
count = scores.count(score)
if count > 0:
print "%3d: %2d" %(score,count)
def print_scores_v2( scores ):
'''
The second solution is based on sorting. In doing so, all values
that are the same are adjacent to each other in the sorted list,
making them much easier to count. We start by making a copy of
the list in case the user wanted to work with the original list.
'''
scores_c = scores[::]
scores_c.sort()
count = 1
print '\nVersion 2 output:'
for i in range(1,len(scores_c)):
if scores_c[i-1] == scores_c[i]: # seeing same score as the previous
count += 1
else:
''' The current score is not the same as the previous, so
output the previous along with its count. '''
print "%3d: %2d" %(scores_c[i-1],count)
count = 1
# Print count for last item in the list
print "%3d: %2d" %(scores_c[-1],count)
if __name__ == "__main__":
''' Read in the scores, storing them in a list '''
in_file = open('scores.txt')
scores = []
for line in in_file:
scores.append( int(line) )
print_scores_v1(scores)
print_scores_v2(scores)
```

## Lecture 15¶

**Module:** `lec15_find_names_start`

Starting point for an actor find routine¶

**Code**:

```
imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
name_list = []
for line in open(imdb_file):
words = line.strip().split('|')
name = words[0].strip()
```

## Lecture 16¶

**Module:** `lec16_imdb_list.py`

Find the busiest person (slowly) in the IMDB using a list¶

**Code**:

```
'''
Author: Chuck Stewart
Purpose: Using a list that keeps track of actors and the number of
movies they have been in, find the person who was in the most movies
listed in our data from the Internet Movie Database. This
demonstrates a very slow --- O(N^2) --- solution to this problem. A
dictionary-based solution and a solution based on sorting are both
faster.
'''
def insert_name_and_count( count_list, name ):
i=0
while i<len(count_list) and count_list[i][0] != name:
i += 1
if i == len(count_list):
# name is not already in the list
count_list.append( [name,1] )
else:
count_list[i][1] += 1
if __name__ == "__main__":
imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
''' Do the counting '''
count_list = []
for line in open(imdb_file):
words = line.strip().split('|')
name = words[0].strip()
insert_name_and_count( count_list, name )
''' Find the max '''
max_movies = count_list[0][1]
max_name = count_list[0][0]
for i in range(1,len(count_list)):
if count_list[i][1] > max_movies:
max_name = count_list[i][0]
max_movies = count_list[i][1]
''' Print our answer '''
print '%s was involved in the most movies, %d' %(max_name, max_movies)
```

**Module:** `lec16_imdb_dict.py`

Find the busiest person (quickly) in the IMDB using a dictionary¶

**Code**:

```
'''
Author: Chuck Stewart
Purpose: Using a dictionary that associates names with the number of
movies, find the person who was in the most movies listed in our data
from the Internet Movie Database.
'''
import time
if __name__ == "__main__":
imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
start_time = time.time()
''' Do the counting '''
counts = {}
for line in open(imdb_file):
words = line.strip().split('|')
name = words[0].strip()
if name in counts:
counts[name] += 1
else:
counts[name] = 1
''' Find the max '''
max_movies = 0
max_name = ''
for name in counts.keys():
if counts[name] > max_movies:
max_name = name
max_movies = counts[name]
end_time = time.time()
''' Print our answer '''
print '%s was involved in the most movies, %d' %(max_name, max_movies)
print 'Dictionary version took %1.2f seconds' %(end_time-start_time)
```

**Module:** `lec16_imdb_list_sort.py`

Find the busiest person (quickly) in the IMDB using sorting¶

**Code**:

```
'''
Author: Chuck Stewart
Purpose: Here is a fast, list-based solution to our problem of finding
the busiest person in the internet movie database. It takes a
different approach, one involving sorting.
'''
import time
if __name__ == "__main__":
imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
start_time = time.time()
''' Append each name '''
names = []
for line in open(imdb_file):
words = line.strip().split('|')
names.append( words[0].strip() )
names.sort()
'''
Scan through the list, adding to a running counter when the name
is the same as the previous. When they are different check to see
if a new max has been reached. If so, then update the max and
reset the counter to 1. If not, just reset the counter.
'''
max_movies = 0
max_name = ''
current_count = 1
for i in range(1,len(names)):
if names[i] == names[i-1]:
current_count += 1
elif current_count > max_movies:
max_movies = current_count
max_name = names[i-1]
current_count = 1
else:
current_count = 1
'''
Check the special case of the last actor being the busiest.
'''
if current_count > max_movies:
max_movies = current_count
max_name = names[-1]
end_time = time.time()
''' Print our answer '''
print '%s was involved in the most movies, %d' %(max_name, max_movies)
print 'List and sorting version took %1.2f seconds' %(end_time-start_time)
```

## Lecture 17¶

**Module:** `lec17_years_to_movies.py`

Find the year in the IMDB using a dictionary¶

**Code**:

```
'''
Author: Chuck Stewart
Purpose: Lecture 17 IDMB example of a dictionary associating a year
with the set of movies from that year and then using the dictionary to
find the year with the most movies.
'''
if __name__ == "__main__":
## Form the dictionary
imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
years_to_movies = {}
for line in open(imdb_file):
words = line.strip().split('|')
movie_name = words[1].strip()
year = int(words[2])
# Create an empty set entry if the year is new
if year not in years_to_movies:
years_to_movies[year] = set()
# Add the movie to the year
years_to_movies[year].add(movie_name)
# A little bit of extra printed information
print 'Earliest year is', min(years_to_movies.keys())
print 'Last year is', max(years_to_movies.keys())
# Find the busiest year by keeping track of the maximum size set from
# the dictionary and the year that had that maximum size.
max_year = 0
max_count = 0
for y in years_to_movies.keys():
count = len(years_to_movies[y])
if count > max_count:
max_year = y
max_count = count
print 'Year %d had max movies: %d' %(max_year, max_count)
```

**Module:** `lec17_actors_and_movies.py`

Find all movies for an actor and actors in the same movie¶

**Code**:

```
'''
Author: Chuck Stewart
Purpose: Lecture 17 IDMB example where two dictionaries are built, one
associating an actor with the set of movies they appear in and the
other associating a movie with the set of actors. We can use this to
find actors that appeared together in a movie.
'''
if __name__ == "__main__":
imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
actor_name = raw_input("Enter the name of an actor (last, first) ==> ").strip()
# Form the two dictionaries.
actors_to_movies = {}
movies_to_actors = {}
for line in open(imdb_file):
words = line.strip().split('|')
actor = words[0].strip()
movie = words[1].strip()
# Additions to the first dictionary
if not actor in actors_to_movies:
actors_to_movies[actor] = set()
actors_to_movies[actor].add(movie)
# Additions to the second dictionary
if not movie in movies_to_actors:
movies_to_actors[movie] = set()
movies_to_actors[movie].add(actor)
# Let's evaluate the movies
print "\n%s has been in %d movies" %(actor_name, len(actors_to_movies[actor]))
print "Here they are:"
movie_list = sorted(list(actors_to_movies[actor_name]))
for i in range(len(movie_list)):
print "\t%3d: %s" %(i+1, movie_list[i])
# Find other actors that this actor appeared with
other_actors = set()
for movie in actors_to_movies[actor_name]:
other_actors |= movies_to_actors[movie]
print '\n%d other actors appeared with %s' %(len(other_actors), actor_name)
print 'Here they are:'
actor_list = sorted(list(other_actors))
for i in range(len(actor_list)):
print "\t%3d: %s" %(i+1, actor_list[i])
```

## Lecture 18¶

**Module:** `lec18_points.py`

A simple implementation of a point class¶

**Code**:

```
""" Class example, a simple class of 2d objects
"""
class Point2d(object):
def __init__(self, x0, y0):
"""Initialize to make sure each point has an x, y value. """
self.x = x0
self.y = y0
def length(self):
""" Return the length of a point. """
return (self.x**2 + self.y**2)**(0.5)
def __str__(self):
""" Returns the string representation of object.
Call as:
str(x)
print x ##calls this function and prints the result string
"""
return "(%d, %d)" %(self.x, self.y)
def distance(self, other):
""" Returns the distance between two points. """
d = (self.x-other.x)**2 + (self.y-other.y)**2
return d**(0.5)
def __add__(self, other):
""" Adds two points and returns a new point with the
addition of values. You can call this as:
pt1.__add__(pt2)
pt1+pt2
"""
new = Point2d(self.x, self.y)
new.x += other.x
new.y += other.y
return new
def __sub__(self, other):
""" Subtracts other from self, and returns a new point
containing the result. You can call this as:
pt1.__sub__(pt2)
pt1-pt2
"""
new = Point2d(self.x, self.y)
new.x -= other.x
new.y -= other.y
return new
if __name__ == "__main__":
##Test code here
pt1 = Point2d(10, 20)
pt2 = Point2d(3, 4)
print pt1.x, pt1.y
print pt2.x, pt2.y
print pt1 ## calls the __str__ method
print str(pt1) ## this is identical to the above call
print "Length of pt1 is", pt1.length()
print "Length of pt2 is", pt2.length()
print "Distance between", pt1, "and", pt2, "is:", pt1.distance(pt2)
print pt1 ##calls str
pt3 = pt1+pt2
print pt3
print "Subtraction:", pt1-pt2
print "Pt1:", pt1, "Pt2:", pt2
print "Add/Subtract do not change the input objects"
```

## Lecture 19¶

**Module:** `lec19_time_skeleton.py`

A framework for the time class¶

**Code**:

```
""" Class for storing time. Time is reported on a military (24 hour) clock
"""
class Time(object):
def __init__(self, hr, min, sec):
pass
def convert(self):
pass
def __str__(self):
pass
def __add__(self, other):
pass
def __sub__(self, other):
pass
if __name__ == '__main__':
pass
```

**Module:** `lec19_time.py`

Completed time class¶

**Code**:

```
""" Class for storing time.
"""
class Time(object):
def __init__(self, hr, min, sec):
if hr > 24:
hr = hr%24
self.seconds = hr*60*60 + min*60 + sec
def convert(self):
hr = self.seconds/3600
min = (self.seconds - hr*3600)/60
sec = self.seconds - hr*3600 - min*60
return hr, min, sec
def __str__(self):
hr, min, sec = self.convert()
return '%02d:%02d:%02d' \
%(hr, min, sec)
def __add__(self, other):
total = self.seconds + other.seconds
hr = total/3600
min = (total - hr*3600)/60
sec = total - hr*3600 - min*60
return Time(hr, min, sec)
def __sub__(self, other):
total = self.seconds - other.seconds
if total < 0:
total += 24*3600
hr = total/3600
min = (total - hr*3600)/60
sec = total - hr*3600 - min*60
return Time(hr, min, sec)
```

**Module:** `lec19_restaurant_exercise.py`

Main routine for the yelp data¶

**Code**:

```
'''
Use the business class to manage a set of restaurants
and get user inputs on how to proceed.
'''
from lec19_business_class import Business
import webbrowser
def convert_input_to_restaurant(line):
m = line.strip().split("|")
return Business(m[0],m[1],m[2],m[3],m[4],m[5],m[6:])
def build_restaurant_list():
restaurants = []
f = open('yelp.txt')
restaurants = []
for line in f:
restaurants.append(convert_input_to_restaurant(line))
return restaurants
if __name__ == "__main__":
restaurants = build_restaurant_list()
num_restaurants = len(restaurants)
while (True):
# Get the index of the restaurant and check it.
print "Enter the index of the restaurant from 1 to %d or stop to end ==> " %num_restaurants,
index = raw_input()
print index
if index == 'stop':
break
index = int(index)
if index < 1 or index > num_restaurants:
print "The index is out of range. Sorry."
else:
print(restaurants[index-1])
```

**Module:** `lec19_business_class.py`

Code for the business class¶

**Code**:

```
###import points
from lec18_points import Point2d
class Business(object):
def __init__(self, name, lat, lon, address, url, category, scores):
self.name = name
self.loc = Point2d(float(lon), float(lat))
self.address = address
self.url = url
self.category = category
## convert scores into integer
for i in range(len(scores)):
scores[i] = int(scores[i])
self.scores = scores
def avgscore(self):
if len(self.scores) < 3:
return sum(self.scores)/float(len(self.scores))
else:
s = list(self.scores)
s.sort() ## we do not want to change the actual ordering of scores
return ( sum(s[1:-1])/float(len(s)-2) )
def minscore(self):
return min(self.scores)
def maxscore(self):
return max(self.scores)
def __str__(self):
return "%s (%s)\n\t%s\n\tLocation: %s\nAvg Score: %.1f (%d - %d)" \
%(self.name, self.category, self.address, self.loc, self.avgscore(), self.minscore(), self.maxscore())
```

## Lecture 20¶

**Module:** `lec20_smallest_two.py`

Find the smallest two values in a list¶

**Code**:

```
"""
Problem: Find the index of the two smallest values
We will also learn how to time running time of algorithms
using the time module
Algorithm:
Idea 1:
Make a copy of list
Sort the copy
Find the two smallest values (index 0,1)
Find the index of these values**
Idea 2:
Initialize two smallest values to 0,1
Then, iterate through list
and remember the smallest two values
and their index
Idea 3:
Make a list of value, index
Sort the list
Return the index for the first two
Idea 4: (implement this yourself)
Make a copy of list
find min in copy
find index of min in copy
remove min from list copy
find next min in copy
find index of min in the next copy
"""
import random
import time
def smallest_two1(L):
""" Assume n items in List L.
Complexity: O(nlogn + 3n) =mostly costly element= O(nlogn)
"""
L1 = list(L) ### O(n): read and append to new list for n elements
L1.sort() ### O(nlogn): sorting: we will see this in sorting lecture
min1,min2 = L1[0], L1[1] ## O(1)
i1 = L.index(min1) ### O(n): compare against every element in worst case
i2 = L.index(min2) ### O(n): compare against every element in worst case
if i2 == i1:
i2 = L.index(min2, i1+1)
return i1, i2
def smallest_two2(L):
""" Assume n items in List L.
Complexity: O(n)
"""
if L[0] < L[1]:
i1, i2 = 0,1
else:
i1, i2 = 1,0
for i in range(2,len(L)): ### O(n)
if L[i] < L[i1]:
i1, i2 = i, i1
elif L[i] < L[i2]:
i2 = i
return i1, i2
def smallest_two3(L):
""" Assume n items in List L.
Complexity: O(n+nlog n) =mostly costly element= O(nlogn)
Note: Compared
to smallest_two3, we are sorting a more complex list
(list of 2-tuples). So efficiency will depend on the implementation
of that sort
"""
L1 = []
for (i,val) in enumerate(L): ## O(n): read and append each element
L1.append( (val, i) )
L1.sort() ## O(nlogn): sorting, we will see why
return L1[0][1], L1[1][1]
if __name__ == "__main__":
print "Test cases"
L = range(100000)
random.shuffle(L)
start = time.time()
a,b = smallest_two1(L)
end = time.time()
print "smallest_two1 took %f seconds" %(end-start)
start = time.time()
a,b = smallest_two2(L)
end = time.time()
print "smallest_two2 took %f seconds" %(end-start)
start = time.time()
a,b = smallest_two3(L)
end = time.time()
print "smallest_two3 took %f seconds" %(end-start)
```

**Module:** `lec20_searching.py`

Find a specific value in a sorted list¶

**Code**:

```
"""
Input: a sorted list and a value
Find the index of value if value is in list
of if it is not, return the index of where
value would be inserted to keep the list sorted.
"""
import random
import time
def search(L,val):
""" Linear search, each item has to be searched. """
for i in range(len(L)): ## O(n)
if L[i] >= val:
return i
return len(L)-1
def binsearch(L, val):
""" Binary search: always look at the middle value
of a list, then look at the middle value of the remaining
list. You can do this at most O(log n) times, where
log is base 2.
"""
low = 0
high = len(L)-1
while low != high:
mid = (low+high)/2
#print low, high, mid
#raw_input()
if L[mid] < val:
low = mid+1
else:
high = mid
return low
if __name__ == "__main__":
print "Time tests"
k = 500000
L = range(k)
loops = 100
start = time.time()
for i in range(loops):
val = L[random.randrange(500000)] + 0.5
val = k+1
a = search(L, val)
end = time.time()
total = end-start
print "Linear search took", total/loops, "seconds, value found at", a
start = time.time()
for i in range(1000*loops):
val = L[random.randrange(500000)] + 0.5
val = k+1
a = binsearch(L,val)
end = time.time()
total = end-start
print "Binary search took", total/(1000*loops), "seconds, value found at", a
```

## Lecture 21¶

**Module:** `test_sort.py`

Module and code to test the sorting functions¶

**Code**:

```
'''
Testing code for Computer Science 1, Lecture 21 on sorting. This
assumes that the sort functions are all in file sorts.py, each taking
one list as its only argument, and that their names are sel_sort
ins_sort merge_sort
All tests are based on random permutations of integers.
. In most of our tests, these permutations are completely random,
meaning that a value is equally likely to end up anywhere in the
list.
. In the final test we will explore the implications of working
with lists that are "almost sorted" by only moving values a small
distance from the correct location. You can see that insertion sort
is very fast in this case by removing the # char in front of
generate_local_perm
'''
import sorts_sol
import time
import random
def run_and_time(name, sort_fcn, v, known_v):
'''
Run the function passed as sort_fcn, timing its performance and
double-checking if it correct. The correctness check is probably
not necessary.
'''
print "Testing " + name
t0 = time.time()
sort_fcn(v)
t1 = time.time()
print "Time: %.4f seconds" %(t1-t0)
# print "Is correct?", v==known_v
print
def run_and_time_python_sort(v):
'''
Run and time the Python list sort function on the list.
'''
print "Running Python's list sort function"
t0 = time.time()
v.sort()
t1 = time.time()
print "Time: %.4f seconds" %(t1-t0)
print
def generate_local_perm(v,max_shift):
'''
Generate a local permutation by randomly moving each value up to
max_shift locations in the list
'''
for i in range(len(v)):
min_i = max(0,i-max_shift)
max_i = min(len(v)-1, i+max_shift)
new_i = random.randint( min_i, max_i )
v[i], v[new_i] = v[new_i], v[i]
####################################################
if __name__ == '__main__':
n = int(raw_input("Enter the number of values ==> "))
print "----------"
print "Running on %d values" %n
print "----------"
v = range(n)
v1 = v[:]
random.shuffle(v1)
# generate_local_perm(v1, 10)
v2 = v1[:]
v3 = v1[:]
v4 = v1[:]
run_and_time("merge sort", sorts_sol.merge_sort, v3, v ) # passing functions as an arg to a fcn
run_and_time_python_sort(v4 )
run_and_time("selection sort", sorts_sol.sel_sort, v1, v )
run_and_time("insertion sort", sorts_sol.ins_sort, v2, v )
```

**Module:** `sorts_start.py`

Start of sorting algorithm implementations¶

**Code**:

```
'''
CS 1, Lecture 21
Implementation of a variety of sorting algorithms, including
. Selection Sort,
. Insertion Sort
. Merge Sort
Details will be filled in during lecture.
The main code gives tests for these functions.
'''
def sel_sort( v ):
'''
Sort based on teh O(N^2) selection sort algorithm. The ideas is
discussed in the text book. Students are not responsible for
knowing this algorithm.
'''
for i in range(0, len(v)-1):
k = i
for j in range(i+1,len(v)):
if v[j] < v[k]:
k = j
v[i],v[k] = v[k],v[i]
def ins_sort( v ):
'''
The Insertion Sort algorithm
'''
# Fill in here
for i in range(1,len(v)):
x = v[i]
j = i-1
while j >= 0 and v[j] > x:
v[j+1] = v[j]
j -= 1
v[j+1] = x
def merge(L1,L2):
'''
Merge the contents of two lists, each of which is already sorted
into a single sorted list.
'''
i1 = 0
i2 = 0
L = []
'''
Repeated choose the smallest remaining item from the lists until one
list has no more items that have not been merged.
'''
while i1 < len(L1) and i2 < len(L2):
if L1[i1] < L2[i2]:
L.append( L1[i1] )
i1 += 1
else:
L.append( L2[i2] )
i2 += 1
L.extend(L1[i1:]) # copy remaining items from L1, if any
L.extend(L2[i2:]) # copy remaining items from L2, if any
return L
def merge_sort(v):
'''
Implementation of the merge sort algorithm.
'''
if len(v) <= 1:
return
'''
Start by creating the list of singleton lists '''
lists = []
for item in v:
lists.append( [item] )
# print 'Before', lists
'''
Merge the lists in pairs until there is one unmerged list remaining.
A number of print statements, used to see what is happening, are here
in the code but have been commented out.
'''
i = 0
while i < len(lists)-1:
# print '****** i =', i
# print 'input', lists[i]
# print 'input', lists[i+1]
new_list = merge(lists[i], lists[i+1])
lists.append( new_list )
# print 'merged', new_list
i += 2
'''
This is where I made a mistake in class. I had v = lists[-1], but
that makes v refer to a new list, and the reference is gone when the
function ends. Instead, by writing v[::], v still refers to the original
list, but it is copied over.
'''
v[::] = lists[-1]
if __name__ == "__main__":
'''
v = [ 10, 5, 3, 2, -4 ]
ins_sort(v)
print v
v = []
ins_sort(v)
print v
v = [ 5, 6, 7, 6, 5, 5]
ins_sort(v)
print v
'''
'''
v1 = [ 26, 35, 145]
v0 = [ 0, 0, 9, 9, 9.4, 9.6, 15, 21 ]
print v0
print v1
print merge(v0,v1)
'''
v = [ 9.1, 17.5, 9.8, 6.3, 12.4, 1.7 ]
merge_sort(v)
print v
```

**Module:** `sorts_sol.py`

Solved sorting algorithm implementations (including one fix)¶

**Code**:

```
'''
CS 1, Lecture 21
Implementation of a variety of sorting algorithms, including
. Selection Sort,
. Insertion Sort
. Merge Sort
Details will be filled in during lecture.
The main code gives tests for these functions.
'''
def sel_sort( v ):
'''
Sort based on teh O(N^2) selection sort algorithm. The ideas is
discussed in the text book. Students are not responsible for
knowing this algorithm.
'''
for i in range(0, len(v)-1):
k = i
for j in range(i+1,len(v)):
if v[j] < v[k]:
k = j
v[i],v[k] = v[k],v[i]
def ins_sort( v ):
'''
The Insertion Sort algorithm
'''
# Fill in here
for i in range(1,len(v)):
x = v[i]
j = i-1
while j >= 0 and v[j] > x:
v[j+1] = v[j]
j -= 1
v[j+1] = x
def merge(L1,L2):
'''
Merge the contents of two lists, each of which is already sorted
into a single sorted list.
'''
i1 = 0
i2 = 0
L = []
'''
Repeated choose the smallest remaining item from the lists until one
list has no more items that have not been merged.
'''
while i1 < len(L1) and i2 < len(L2):
if L1[i1] < L2[i2]:
L.append( L1[i1] )
i1 += 1
else:
L.append( L2[i2] )
i2 += 1
L.extend(L1[i1:]) # copy remaining items from L1, if any
L.extend(L2[i2:]) # copy remaining items from L2, if any
return L
def merge_sort(v):
'''
Implementation of the merge sort algorithm.
'''
if len(v) <= 1:
return
'''
Start by creating the list of singleton lists '''
lists = []
for item in v:
lists.append( [item] )
# print 'Before', lists
'''
Merge the lists in pairs until there is one unmerged list remaining.
A number of print statements, used to see what is happening, are here
in the code but have been commented out.
'''
i = 0
while i < len(lists)-1:
# print '****** i =', i
# print 'input', lists[i]
# print 'input', lists[i+1]
new_list = merge(lists[i], lists[i+1])
lists.append( new_list )
# print 'merged', new_list
i += 2
'''
This is where I made a mistake in class. I had v = lists[-1], but
that makes v refer to a new list, and the reference is gone when the
function ends. Instead, by writing v[::], v still refers to the original
list, but it is copied over.
'''
v[::] = lists[-1]
if __name__ == "__main__":
'''
v = [ 10, 5, 3, 2, -4 ]
ins_sort(v)
print v
v = []
ins_sort(v)
print v
v = [ 5, 6, 7, 6, 5, 5]
ins_sort(v)
print v
'''
'''
v1 = [ 26, 35, 145]
v0 = [ 0, 0, 9, 9, 9.4, 9.6, 15, 21 ]
print v0
print v1
print merge(v0,v1)
'''
v = [ 9.1, 17.5, 9.8, 6.3, 12.4, 1.7 ]
merge_sort(v)
print v
```

## Lecture 24¶

**Module:** `lec24_examples.py`

Some simple examples of recursion¶

**Code**:

```
"""
Recursion: Example functions
Basis/Stopping condition:
Define when your function should stop
calling itself recursively
Inductive/Recursive step:
Define how the function can compute its
output by calling itself recursively and then
use the result.
Example:
Recursive step:
factorial(n) = factorial(n-1)*n
If you had the correct output for factorial(n-1),
you can multiply it with n to find the correct output.
"""
def blast(n):
if n <= 0: ##basis step
print "Blast off!"
else: ## recursive step
print n
blast(n-1)
print n
def factorial(n):
if n == 1:
return 1
else:
x = factorial(n-1)
return x*n
def factorial_iterative(n):
"""Many recursive functions can be written without recursion. """
x = 1
for i in range(n+1):
x *= i
return x
def fib(n):
"""Fibonacci sequence: Even though it is defined recursively
this function would be much more efficient to write without
recursion.
"""
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
if __name__ == "__main__":
##Testing code here.
val = int(raw_input("Number => "))
print "Factorial of %d is %d" %(val, factorial(val))
for i in range(10):
print "fib(%d) = %d" %(i, fib(i))
```

**Module:** `lec24_sierpinksi.py`

Module and code to demonstrate recursion to create a fractal¶

**Code**:

```
"""
Example program shows the use of recursion to create fractals,
in this case, the Sierpinski Triangle. See function:
draw_triangles
for the recursion. The rest is TkInter program allowing the
user to change properties of the Sierpinski triangle drawn.
"""
from Tkinter import *
import math
class MyApp(object):
def __init__(self, parent):
##Function local to init to simplify repetitive button creation process
def put_button(parent, name, functionname, placement):
newbutton = Button(parent, text=name, command=functionname)
newbutton.pack(side=placement)
newbutton.configure(width=button_width,\
padx=button_padx, pady=button_pady )
return newbutton
## constants used in the initialization
button_width = 10
button_padx = "3m"
button_pady = "3m"
## variables used in the program
self.maxlevel = 6
self.size = 600 #3**self.maxlevel
self.maxy = int(self.size*math.sqrt(3)/2)
self.stopped = False
self.depth = 2
self.wait_time = 1
self.parent = parent
## interface elements
## all frames
self.main_frame = Frame(parent)
self.main_frame.pack()
self.top_frame = Frame(self.main_frame)
self.top_frame.pack(side=TOP)
self.bottom_frame = Frame(self.main_frame)
self.bottom_frame.pack(side=BOTTOM)
## canvases: top for info, buttom for drawing Triangles
self.infocanvas = Canvas(self.top_frame, \
width=self.size, height=30)
self.infocanvas.pack(side=TOP)
self.text_area = self.infocanvas.create_text(30,10,anchor='nw')
self.canvas = Canvas(self.top_frame, \
width=self.size, height=self.maxy)
self.canvas.pack(side=BOTTOM)
## buttons: for controlling the program
self.drawbutton = put_button(self.bottom_frame, 'Draw', self.draw, LEFT)
self.clearbutton = put_button(self.bottom_frame, 'Clear', self.clear, LEFT)
self.fasterbutton = put_button(self.bottom_frame, \
"Faster", self.faster, LEFT)
self.slowerbutton = put_button(self.bottom_frame, \
"Slower", self.slower, LEFT)
self.increasebutton = put_button(self.bottom_frame, \
"Depth+1", self.increase, LEFT)
self.decreasebutton = put_button(self.bottom_frame, \
"Depth-1", self.decrease, LEFT)
self.quitbutton = put_button(self.bottom_frame, \
"Quit", self.quit, RIGHT)
## display settings for the program on the info canvas
self.put_info()
def put_info(self):
""" Function for displaying the settings for the program,
depth and wait time for the animation effect.
"""
info = "Wait time: %d ms" %(self.wait_time)
if self.depth == self.maxlevel+3:
info += " "*10+ "Depth: %d (max level reached)" %self.depth
elif self.depth <= 2:
info += " "*10+ "Depth: 2 (min level reached)"
else:
info += " "*10+ "Depth: %d" %self.depth
self.infocanvas.itemconfigure(self.text_area, text=info)
def clear(self):
""" Clear the drawing (used in self.clearbutton). """
self.canvas.delete("all")
def faster(self):
""" Make the animation faster (used in self.fasterbutton). """
self.wait_time /= 2
if self.wait_time <= 0:
self.wait_time = 1
self.put_info()
def slower(self):
""" Make the animation slower (used in self.slowerbutton). """
self.wait_time *= 2
self.put_info()
def increase(self):
""" Increases the depth for recursion (used in self.fasterbutton). """
if self.depth < self.maxlevel+3:
self.depth += 1
self.put_info()
def decrease(self):
""" Decreases the depth for recursion (used in self.slowerbutton). """
if self.depth > 2:
self.depth -= 1
self.put_info()
def draw(self):
""" Clear the canvas and draws the Sierpinksi triangles (used in self.drawbutton). """
padding = 20 ##just leave some space off the corners
if not self.stopped:
self.clear()
self.draw_triangles(0+padding,self.maxy-padding,self.size-2*padding, 1)
def draw_triangles(self, x, y, length, depth):
""" Draws two triangles: one with x,y as the bottom left corner,
in red and a second inverted one inside between the midpoints
of the outside triangle, in white.
"""
if depth <= self.depth:
## Triangle 1: Outside Triangle
mid = length/2
self.canvas.create_polygon(x, y, \
x+length, y, \
x+mid, y-math.sqrt(3)*mid,\
fill = "red")
## Triangle 2: Inside Triangle
leftmid = ( x+(mid)/2, y-(math.sqrt(3)*mid)/2 )
rightmid = ( x+(length+mid)/2, y-(math.sqrt(3)*mid)/2 )
bottommid = ( x+mid, y )
self.canvas.create_polygon( leftmid[0], leftmid[1], \
rightmid[0], rightmid[1], \
bottommid[0], bottommid[1], \
fill = "white" )
self.draw_triangles(x, y, length/2, depth+1)
self.draw_triangles(leftmid[0], leftmid[1], length/2, depth)
self.draw_triangles(x+length/2, y, length/2, depth+1)
## Add animation effect
self.canvas.update()
self.canvas.after(self.wait_time)
def quit(self):
self.stopped = True
self.parent.destroy()
if __name__ == "__main__":
root = Tk()
root.title("Recursion Example with Sierpinski Triangles")
myApp = MyApp(root)
root.mainloop()
```

**Module:** `lec24_merge_sort.rec.py`

Recursive definition for the merge sort¶

**Code**:

```
"""
We rewrite merge_sort using recursion and compare to the
iterative version. The recursive version is natural to write
and does not require a list/loop to maintain sublists. As a
result, it is slightly more efficient.
"""
import time
import random
def time_function(L, func):
""" Illustrates how you can send a function as an argument
to another function as well. Runs the function called func,
and returns the time.
"""
L1 = list(L)
start = time.time()
func(L1)
end = time.time()
print "Method: %s took %f seconds" \
%((func.__name__).ljust(20), end-start)
def merge(L1, L2):
""" Assume L1 and L2 are sorted.
Create a new list L that is the merged
version of L1&L2.
This is the efficient version of merge
that does not modify the input lists, as pop
is costly, even though it is a constant time operation.
"""
L = []
i = 0
j = 0
while i < len(L1) and j < len(L2):
if L1[i] < L2[j]:
val = L1[i]
L.append( val )
i += 1
else:
val = L2[j]
L.append( val )
j += 1
## at this point, either L1 or L2 has run out of values
## add all the remaining values to the end of L.
L.extend(L1[i:])
L.extend(L2[j:])
return L
def merge_sort_iterative(L):
""" Complexity: O(n* log n)
See earlier version of this code for explanation.
"""
L1 = []
for val in L:
L1.append( [val] )
while len(L1) > 1:
L2 = []
for i in range(0, len(L1)-1, 2):
Lmerged = merge( L1[i], L1[i+1] )
L2.append( Lmerged )
if len(L1)%2 == 1:
L2.append( L1[-1] )
L1 = L2
return L1[0]
def merge_sort_recursive(L):
""" Complexity: O(n logn)
The function calls itself recursively logn times,
and each time about n elements are merged.
"""
numitems = len(L)
if numitems <= 1:
return L
else:
mid = numitems/2
L1 = merge_sort_recursive( L[:mid] )
L2 = merge_sort_recursive( L[mid:] )
return merge(L1, L2)
if __name__ == "__main__":
##Testing code
k = 100000
L = range(k)
random.shuffle(L)
time_function( L, merge_sort_iterative )
time_function( L, merge_sort_recursive )
time_function( L, list.sort )
```