Exercise: bisection method

Exercise: apply the bisection method to solve an equation of the form
f(x) = 0
1) Define a function f(x) with «def»
2) solve the equation «with pen and paper», and write down the solution
3) define three constants: the two extremes of an interval that contains the
solution and a «TOL» (tolerance) constant (max error tolerated)
4) use a while loop, and implement the bisection method

optional:

5) insert the while loop in an external for loop, where you run the TOL over several
values, smaller and smaller.
6) For each step, record the TOL in a list (or array) and the «difference between the
analitic solution (computed with pen-and-paper) and the solution obtained with
the bisection method
7) make a plot of the «differencese vs tolerances»

Exercise: Newton’s method

Implement the Newton’s method to solve a simple equation (e.g. a quadratic equation).

The method is described in the book (Sauer), but in this case no pseudo-code is given, so you may need to search online for some examples.

Netown’s method can be implemented in two different ways.
The first way is to execute a fixed number of steps.
The second is to define a «tolerance» constant, at each step compute the difference between the solution of the present step and the solution of the previous step, and stop the process when this difference is smaller than the tolerance.
With this second method, the initial estimate of the solution can be a random value in the interval, or its central point.

Optional (additional): compute the number of steps needed, for a given tolerance.

Exercise: comparison of the two methods

Using an equation with a known solution, plot the number of steps versus the tolerance.

Exercise: Numerical integration with trapezoidal rule

Let’s use the trapezoid rule.

Exercise: Compare text files with lists of names

Using a text editor, create two text files with names and surnames, one person in each line, with no spaces at the end and a space in the middle.
— Case 1 — there is a longer file, with around 15/20 people, and a shorter file with around 10 people, chosen out of the list in the first file. The task is to find the missing people in the second file. Create a third file, called «missing people» and write the missing names and surnames in it.
— Case 2 — the two files have lists of similar length, only few people are present in both files. The task is to find the people present in both files, and write them in a third file.
— Case 3 — in comparing the people, consider the possibility that the same person is written with «name surname» order in one file, and «surname name» in another file.

Hints:
It is useful to use the commands string.split() and string.strip() (if you don’t remember the use of those commands, search on the book (Lutz) or on the internet).
One possible method is to use two nested «for loops», one inside the other, the first going through the first list, the second going through the second list.

An alternative to the use of two loops is this: use only one loop, on the «longer list», and use the structure «if element not in short_list:»

Exercise: anagrams 1

An anagram is a type of word play, the result of rearranging the letters
of a word or phrase to produce a new word or phrase, using all the original
letters exactly once; e.g., orchestra = carthorse.
Using the word list at http://www.puzzlers.org/pub/wordlists/unixdict.txt, write a program that finds the sets of words that share the same characters that contain the most words in them.

Exercise: anagrams 2

An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; e.g., orchestra = carthorse. The new word has to be a word existing in the language (english, in our case).
Given a word, find all the anagrams.

hints:
• use the command input(«please insert a word: «) to insert a word. To avoid problems, use a short word, max 6 letters;
• use the library «itertools», and use the command itertools.permutations() to find all the permutations of the letter in the initial word (permutation = a re-ordering of the same elements);
• use the dictionary at http://www.puzzlers.org/pub/wordlists/unixdict.txt to check if a random combination of letters is an english word or not. To use the dictionary:
— open the link above, select all the text, copy it and paste it in a text file. Save the text file and use it in your python script.
— from python, open the file, read it and put the content into a variable (called e.g. «all_words_string»).
— transform this big string into a list of all the words using words_list = all_words_string.split(«\n»)