Week 6: Exercises

1. Sort

Write a program sort.py that takes a filename on the command line. The program should sort the file's lines in alphabetical order and print the result to standard output. For example,

$ cat text
one two
three four
five six
seven eight
$ py sort.py
usage: sort.py <filename>
$ py sort.py text
five six
one two
seven eight
three four
$

2. Unique Word Count

Write a program that reads text from standard input until it ends, and prints the number of unique words in the input.

3. Same Values

Write a function same_values(l, m) that returns True if the lists l and m contain the same values, i.e. every element of l is in m and every element of m is in l. You may assume that all list elements are immutable.

4. Words in Both Lists

Write a program that reads input as follows. The first line of standard input will contain an integer N. The next N lines will contain a list of words, one per line. The next line will contain an integer M. The next M lines will contain a second list of words, one per line. The program should print out all words that are contained in both lists. Write each word on a separate line. You may write the output words in any order.

Sample input:

3
donut
cookie
cake
4
cake
bread
jam
donut

Possible output:

cake
donut

5. Most Common Characters

Write a program that reads a string and print out the five most common characters in the string along with their occurrence counts, e.g.

e 23

t 20

o 18

n 15

i 14

Write the characters in decreasing order of frequency. The string may contain any Unicode characters.

6. Combining Dictionaries

Write a function combine(d, e) that takes two dictionaries. It should return a dictionary that maps x to z if d maps x to some y, and e maps y to z. For example, suppose that d is a dictionary that maps Czech words to English words, and e maps English words to Spanish words:

>>> d = { 'žába' : 'frog', 'kočka' : 'cat', 'kráva' : 'cow' }
>>> e = { 'cow' : 'vaca', 'cat' : 'gato', 'dog' : 'perro' }

Then combine(d, e) will map Czech to Spanish:

>>> combine(d, e)
{'kočka': 'gato', 'kráva': 'vaca'}

Notice that 'žába' is not a key in the resulting dictionary, since e doesn't map 'frog' to anything. Similarly, 'perro' is not a value in the resulting dictionary, since d doesn't map anything to 'dog'.

7. Duplicate Values

  1. Write a function that takes a list of integers and returns True if there are any duplicate values in the list. Use sorting to accomplish this task. Do not modify the original list.

  2. Write a function with the same behavior, using a set to accomplish the task.

  3. Which implementation do you think will be faster on a large list in the best case? In the worst case?

  4. As an experiment, generate a list of random 1,000,000 integers in the range from 1 to 1,000,000,000, then call both of the above functions on your list. How does the exection time compare?

  5. Modify the experiment so that all the integers your generated list are unique. Now run both functions on your list. How does the execution time compare?

8. Random Intersection

Write a program that creates two sets of 10,000 random numbers from 1 to 1,000,000, then computes and prints their intersection. How many values do you expect that the intersection will contain, approximately?

9. Comparing Dictionaries

Write a function same_dict(d1, d2) that returns true if two dictionaries have the same key-value pairs. You may not use the == method to compare the dictionaries directly (though you may use == on other types in your solution). For example:

>>> same_dict({ 10 : 20, 30 : 40 }, { 30 : 40, 10 : 20 })
True

If the two dictionaries have a total of N elements, what will be your function's expected big-O running time?

10. No Zeroes, Recursively

Write a function no_zeroes(n) that takes an integer n and returns an integer formed by removing all zeroes from the end of n's decimal representation. For example:

>>> no_zeroes(54000)
54
>>> no_zeroes(2256)
2256

As a special case, no_zeroes(0) = 0.

You may not use any loops in your solution, so you will need to write the function recursively.

11. Recursive Power

a) Write a recursive function is_pow_of_2(n) that returns True if n is a power of 2.

b) Generalize the function: write a recursive function is_pow_of_k(k, n) that returns True if n is a power of k.

12. Recursive Sum

Write a function sum(a, i, j) that computes the sum of the values in the range a[i:j]. You may not use any loops or call the built-in sum() function, so you will need to use recursion.

13. Recursive Max

Write a function max(a, i, j) that computes the maximum value in the range a[i:j]. You may not use any loops or call the built-in max() function, so you will need to use recursion.

14. Recursive Binary Search

Write a function search(a, x) that takes a sorted array a and a value x to search for in the array. It should return True if x is present in the array, otherwise false. Use a binary search. Do not use any loops; instead, write a recursive helper function.

15. Recursive Multiplication

Write a recursive function mul(a, b) that returns the product (a * b) for positive integers a and b. You may use the built-in addition operator (+), but not the multiplication operator (*).

16. Same as the First

Use recursion to write a function same_as_first(a) that returns the number of integers in an array a that are equal to its first element.

17. Cycle

Write a function cycle that takes a list of length N representing a permutation of the integers 0, …, N – 1. The function should return True if the permutation is a single cycle. For example: