MAS2008 Scientific Computing: Lab 1
Revision, and VS Code

Instructions

This document first explains how to get started using VS Code, and then invites you to review some revision material. After that, it describes three tasks. You should complete these tasks by Wednesday evening of Week 2, and paste your code into the Moodle online test system. You should start working on these tasks during the lab session, and continue afterwards if necessary.

Getting started

After logging in, you should first create a folder somewhere where you will keep your work for MAS2008. Then start VS Code (for example, by typing code in the search window at the bottom of the screen, which should cause a clickable icon to appear). Open the folder that you created (by selecting File and Open Folder from the top menu). Next, install the Pylance and Jupyter extensions. You should remember how to do this from the first lecture, but there are also instructions. Create a new Jupyter notebook called hello.ipynb. (For example, you could select File and then New File... from the top menu.) In the cell at the top of the notebook, enter


print("Six slippery snakes slowly slithered south.")

(or some other message of your choice). Press SHIFT-ENTER and check that the message is printed. (There is more about basic interaction with VS Code in this video.)

Review

Download the multi-pangrams notebook from the table below, save it in your MAS2008 folder or an appropriate subfolder, and open it in VS Code. Read through it, execute all the code cells by clicking them and typing SHIFT-ENTER, and make sure that you understand what is going on. Guided by the comments in the multi-pangrams notebook, download open any other notebooks that will help you to consolidate your understanding. Edit the code in various ways to add extra functionality or try different approaches or improve the documentation.


Introduction to Python	View	Download
List comprehension	View	Download
Control structures	View	Download
Data Types	View	Download
String formatting	View	Download
Defining functions	View	Download
Lists	View	Download
Multi-pangrams	View	Download
Mutability and equality	View	Download
Scope of variables	View	Download
Strings	View	Download

Task 1: square roots

The task here is to write a function SQRT(x) which returns the square root of a given positive number $x$. Of course there are built-in functions math.sqrt and numpy.sqrt for this in the math and numpy libraries, and in practice you would use those. However, the aim here is to write your own function as an exercise, and enter in the online test system. Some questions in that system will allow you to import libraries, but this one will not.

The basic approach is as follows. Suppose that we have a number $u$ which we think is close to $\sqrt{x}$. If $u$ is actually equal to $\sqrt{x}$, then $x/u$ will be the same as $u$. If $u$ is smaller than $\sqrt{x}$, then $x/u$ will be bigger than $\sqrt{x}$. If $u$ is bigger than $\sqrt{x}$, then $x/u$ will be smaller than $\sqrt{x}$. In both cases, the average of $u$ and $x/u$ will be closer to $\sqrt{x}$ than $u$ is. Thus, we can replace $u$ by that average, and we will have an improved approximation. If we do this replacement repeatedly, we will eventually get a good approximation. Of course we have to start somewhere, but we can just take $u$ to be one at the beginning of the process. We also need to decide when to stop. As this is just a crude warm-up exercise, you could just do the replacement process a reasonably large, fixed number of times, after some initial experimentation to check how many iterations are usually needed to give an accurate result. By translating this verbal description into Python code, you can write a (short and simple) function that finds square roots. You should test it by calculating the square roots of various numbers and comparing the answers with what you get from your calculator or np.sqrt().

You should then paste your code into the online test on Moodle.

In these online tests, your code must follow the specification precisely. In particular, in this question your function must be called SQRT (not sqrt or square_root or anything else) and it must accept a single argument called x and not have any other arguments. It is very common when programming that you need to follow specifications like this, to ensure that your code will interact correctly with other code.
Your code should not print anything. It should just define a function SQRT(x) with a return statement to return the final answer.
While developing your code you might include lines like SQRT(100) in your notebook to check that your function works correctly. You should remove such lines before entering your code in the online test; just enter the function definition.

Task 2: doubled words

By a doubled word we mean a word like pompom or couscous that consists of a string repeated twice. Write a function filter_doubled(words) which accepts a list words of words, and returns the sublist containing only the doubled words from the original list. For example, if words=["bonbon","aardvark","yoyo"] then filter_doubled(words) should return ["bonbon","yoyo"]. You might or might not want to start by defining a separate function is_doubled(word) which checks whether a single word is doubled; the online test system will accept your work either way. With the right approach, you can make your code very short.

The file sample_words.txt contains a selection of words which you could use for testing.

You should again paste your code into the online test on Moodle. The test system will check your function filter_doubled(words), so that counts as the "external interface" of your code and must follow the specified naming conventions. If you chose to define any auxilary functions, those will not be part of the external interface so you can name them however you like. As in the previous task, the code that you submit should not contain any print statements or test cases.

Task 3: Pisano periods

The Fibonacci numbers are defined as follows: we start with $F_0=0$ and $F_1=1$, then each subsequent Fibonacci number is the sum of the previous two. For example we have $$ \begin{eqnarray} F_0 &=& 0 \\ F_1 &=& 1 \\ F_2 &=& 0+ 1 = 1 \\ F_3 &=& 1+ 1 = 2 \\ F_4 &=& 1+ 2 = 3 \\ F_5 &=& 2+ 3 = 5 \\ F_6 &=& 3+ 5 = 8 \\ F_7 &=& 5+ 8 = 13 \\ F_8 &=& 8+13 = 21 \\ F_9 &=& 13+21 = 34 \end{eqnarray} $$ and so on. If we reduce these numbers modulo $3$ (for example) we get the sequence $(0,1,1,2,0,2,2,1,0,1,1,\dotsc)$.

Write functions pisano_sequence(N,n) and pisano_period(N) as follows.

The function pisano_sequence(N,n) should return a list containing the first $n$ Fibonacci numbers, reduced modulo $N$. If $n$ and $N$ are not both strictly positive integers, then your function should return False. You should include a docstring in your function definition.
When $n$ is sufficiently large, the sequence pisano_sequence(N,n) will start to repeat. For example, when $N=2$ the sequence is $0,1,1,0,1,1,0,1,1,0,\dotsb$, repeating with period $3$. The function pisano_period(N) should return the period for the Pisano sequence modulo $N$. It should return False if $N$ is not a strictly positive integer. You should include a docstring in your function definition.

You should work out a few examples by hand and check that your code gives the right answer. When you are sure that your code is correct and satisfies all the requirements listed above, you should again paste it into the online test on Moodle. Both functions pisano_sequence(N,n) and pisano_period(N) are part of your external interface and so must follow the specified naming conventions. Again, your code should not print anything or contain any test cases.