Exercises

Available under Creative Commons-NonCommercial-ShareAlike 4.0 International License.

Exercise 10.6.Write a function called is_sortedthat takes a list as a parameter and returns Trueif the list is sorted in ascending order and Falseotherwise. You can assume (as a precondition) that the elements of the list can be compared with the relational operators <, », etc.

For example, is_sorted([1,2,2])should return Trueandis_sorted(['b','a'])should return False.

Exercise 10.7.Two words are anagrams if you can rearrange the letters from one to spell the other. Write a function called is_anagram that takes two strings and returns True if they are anagrams. Exercise 10.8.The (so-called) Birthday Paradox:

You can read about this problem at http://en.wikipedia.org/wiki/Birthday paradox , and you can download my solution from http://thinkpython.com/code/birthday.py.

Exercise 10.9.Write a function called remove_duplicatesthat takes a list and returns a new list with only the unique elements from the original. Hint: they don’t have to be in the same order.

Exercise 10.10. Write a function that reads the file words.txt and builds a list with one element per word. Write two versions of this function, one using the appendmethod and the other using the idiom t = t + [x]. Which one takes longer to run? Why?

Hint: use the time module to measure elapsed time. Solution: http://thinkpython.com/ code/wordList.py .

Exercise 10.11.To check whether a word is in the word list, you could use the inoperator, but it would be slow because it searches through the words in order.

Because the words are in alphabetical order, we can speed things up with a bisection search (also known as binary search), which is similar to what you do when you look a word up in the dictionary.

You start in the middle and check to see whether the word you are looking for comes before the word in the middle of the list. If so, then you search the first half of the list the same way. Otherwise you search the second half.

Either way, you cut the remaining search space in half. If the word list has 113,809 words, it will take about 17 steps to find the word or conclude that it’s not there.

Write a function called bisectthat takes a sorted list and a target value and returns the index of the value in the list, if it’s there, or None if it’s not.

Or you could read the documentation of the bisectmodule and use that! Solution: http://thinkpython.com/code/inList.py.

Exercise 10.12.Two words are a “reverse pair” if each is the reverse of the other. Write a program that finds all the reverse pairs in the word list. Solution: http://thinkpython.com/code/reverse_pair.py. 
Exercise 10.13.Two words “interlock” if taking alternating letters from each forms a new word. For example, “shoe” and “cold” interlock to form “schooled.” Solution: http://thinkpython.com/code/interLock.py. Credit: This exercise is inspired by an example at http://puzzLers.org.