UMBC CMSC 671 Fall 2009
Principles of Artificial Intelligence

HOMEWORK TWO
out 9/14, due 9/21

Here are some simple problems to give you some experience with Python. You can use the Python installed on the gl servers, the CSEE servers or your own computers. For the last option, if you are running Linux or MAC OS X, you'll find it pre-installed. If you are running Windows, you can download and install a version from python.org.

Your work should be submitted as a hardcopy document in class on Monday 21 September.

(1) Hailstone sequence

Consider the following problem: Choose a positive integer and repeatedly do the following: if the number is 1, quit; if the number is even, cut it in half; and if the number is odd, multiply it by 3 and add 1. For example, if you start with the number 17, you get the sequence: 17 52 26 13 40 20 10 5 16 8 4 2 1. Generate the sequence from a starting number and you'll find the numbers go up and down like a hailstone in a cloud before it plummets to earth (e.g., one).

Does this procedure eventually reach one and stop for every choice of starting number? So far, this is an unsolved problem -- no one has yet proved that the process always results in 1, and no one has yet found a counterexample.

Write a Python function hailstone that takes a a positive number and returns a a list corresponding to it's hailstone sequence.

>>> import hw2
>>> hw2.hailstone(6)
[6, 3, 10, 5, 16, 8, 4, 2, 1]
>>> hw2.hailstone(100)
[100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17,
  52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
>>> hw2.hailstone(1)
[1]
>>> 

(2) Prime factors

Write a function factors that takes a positive integer and returns a list of its prime factors. For example:
>>> hw2.factors(5)
[1, 5]
>>> hw2.factors(10)
[1, 2, 5, 10]
>>> hw2.factors(20)
[1, 2, 2, 5, 20]
>>> 

(3) Merging lists

Write a function merge_lists that takes two lists, L1 and L2 and returns a list with all of the elements of L1 plus any elements in L2 that can not be paired up with an element of L1 of the same value, given the constraint that multiple elements of L2 can not be paired with the same element of L1. Some examples should make this clear:
>>> hw2.merge([1,2,5], [1,11])
[1, 2, 5, 11]
>>> hw2.merge([1,2,5], [1,2,5])
[1, 2, 5]
>>> hw2.merge([1,2,5], [1,2,2,5,7])
[1, 2, 5, 2, 7]
>>> hw2.merge([1,2,5], [1,2,2,2,5,5,7])
[1, 2, 5, 2, 2, 5, 7]
>>>

(4) Euler five

Write a function solve that takes an integer N and returns the smallest number that can be divided by each of the numbers from 1 to N without any remainder. For example, 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

>>> for n in range(20):
...   print "%s\t%s" % (n, hw2.solve(n))
... 
0	1
1	1
2	2
3	6
4	12
5	60
6	60
7	420
8	840
9	2520
10	2520
11	27720
12	27720
13	360360
14	360360
15	360360
16	720720
17	12252240
18	12252240
19	232792560
>>> 

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Hint: you will find the functions merge and factors to be useful in this problem.

(5) bigram frequency

A lot of text processing and information retrieval just involves counting words. Sometimes it's also important to count occurrences of short phrases. Two word phrases are usually called word bigrams or, generalizing the length, n-grams. Write a function bigrams that takes two arguments, a filename and an integer N, and prints the N most frequent two-word sequences found in the file along with their frequency. Before analyzing the text, you should (1) delete any punctuation symbols and convert everything to lowercase.
>>> hw2.bigrams('test.txt', 20)
Top 50 bigrams in test.txt
('he', 'has')	18
('of', 'the')	12
('of', 'our')	7
('in', 'the')	7
('to', 'the')	7
('for', 'the')	6
('of', 'these')	6
('to', 'be')	6
('we', 'have')	5
('on', 'the')	5
('and', 'to')	4
('his', 'assent')	4
('of', 'their')	4
('to', 'them')	3
('the', 'most')	3
('these', 'colonies')	3
('and', 'the')	3
('us', 'in')	3
('it', 'is')	3
('they', 'are')	3
>>> 

This is easier than it sounds. Here are some suggestions and hints.

  • Evaluating open('test.txt').read() will return a string consisting of all of the characters in the file test.txt
  • If S is a variable bound to a string, and you imported the library module string
    • S.translate(string.maketrans("",""),string.punctuation) will return a copy of S with punctuation characters deleted
    • S.lower() will return a copy of S with uppercase characters replaced by their lowercase equivalents
    • S.split() will return a list of the words in string S where standard whitespace characters are used to delimit words
  • You might consider writting a separate function that takes a list of things and returns a list of two-elelment tuples of adjacent elements in the list.

Evaluation

We will evaluate your program based on mainly on (1) correctness, (2) readability and (3) style with some attention to (4) reasonable efficiency (5) safety and (6) appropriate documentation. You should privilege readability over efficiency, but don't do easily avoidable, unnecessary computation. For advice on style, see Guido van Rossum's PEP8 and Code Like a Pythonista. For documentation, every function should have a document string and any other comments you think helpful.

What to hand in

Write all of your functions as a single file, hw2.py. Hand this is as well as the output captured from an interactive session showing that each of your functions work.

Background reading