<![CDATA[
# CS 101 Lab: Week # 7
<ul class="pager">
<li><a href="../w06/">← Previous lab (First Mid Term Exam week)</a></li>
<li><a href="../w08/">Next lab →</a></li>
</ul>
The following has been covered during the 7th week of CS101 labs.
The syllabus is the same as <a href="../w05/">week 5</a>, with emphasis on Problems 2 and 1.
For the A1 group, you missed two labs, so try to work on your own.
---
## Outline:
1. At first: short sum-up of the *last lab*, and of have been covered in the *last 2 lectures* by Prof. Arya,
2. (if needed) quick reminder about boolean values, testing, and `if`, `elif`, `else` construction,
3. Looping with a **While** loop, reminder of the concept and syntax of a while loop. Quickly say which exercises will need `while` loops (*[ass.#1,2,3]*). One example, printing the first $n$ odd numbers (from Prof. Dhande homework, Pb 5), *[ass.#1]*:
<pre><code class="language-python" style="font-size:145%;"># While loop:
n = 0
while n < 100:
print n
n = n + 2
</code></pre>
4. Introducing the **For** loop, with syntax the basic syntax `for element in list`. Right now, a list will be used only for storing values, and looping through them (an entire lecture and lab will be focused on lists). Quickly say which exercises will need `for` loops (*[ass.#1,2,3,5]* and *[pb.1,2]*). One example (doing the same thing as the previous example):
<pre><code class="language-python" style="font-size:145%;"># For loop:
for n in xrange(0, 100, 2):
print n
</code></pre>
5. Mathematical problem solving with Python : 1h30 of problem solving, with `if`, `while` and `for` loops (in the part **"Problems to be solved today:"**).
### Bonus (if the time allows it)
1. *Bonus:* Explanations about how to write Python *blocks* with the proper *indentation*,
2. *Bonus:* Use a **While** (`while`) loop for checking that an input is valid, by looping (and asking with `input`) as long as necessary. Go back to week #4 assignment sheet, and solve the *bonus* question.
3. *Bonus:* Remarks on [the coding style](https://docs.python.org/2/tutorial/controlflow.html#intermezzo-coding-style). Try to understand what Python tells you when you do `import this`.
---
## Problems to be solved today:
1. Ask the user the value of $n$, then print the first $n$ odd numbers (from Prof. Dhande's homework, Pb 5),
2. Ask the user the value of $n$, then compute and print the first $n$ *"triangular numbers"* : $t\_n = n\*(n+1)/2$ (*question:* do we need to be cautious about that division ? because you know that the behaviour of Python's `/` division operator can be *surprising*),
3. (again) Write an interactive program to ask the user a temperature in °C, a choice between `"K"` or `"F"`, and convert the temperature the the chosen unit ([Kelvin degrees](https://en.wikipedia.org/wiki/Kelvin) or [Fahrenheit degrees](https://en.wikipedia.org/wiki/Fahrenheit)). (You can use the conversion formula **F = (9/5) * C + 32**, and **K = C + 273.15**). While one `while` and one `if-elif-else` loop, check that the choice of the user is either `"K"` or `"F"`, and if it is not, ask the question as many time as necessary.
4. Compute a certain approximation of the value of $\frac{\pi^2}{6}$ by computing partial ($S\_N = \sum\_{n=1}^N \frac{1}{n^2}$) sum of the series studied in the **MA101 Final Exam**: $$\frac{\pi^2}{6} = \lim\_{N \to +\infty} \sum\_{n=1}^N \frac{1}{n^2}.$$ Change the value for the number of terms in the partial sum ($N$), and see how the resulting approximation is getting modify.
5. *Bonus:* improve that last program by testing if the computed apprixmation of $\frac{\pi^2}{6}$ is *"close enough"* of the real value. *Hint:* you can use the [`math`](https://docs.python.org/2/library/math.html) module to have access to the [`math.pi` constant](https://docs.python.org/2/library/math.html#math.pi).
6. About list, min and max of a list:
- Use a list to store some numbers (like `l = [12, 1, 1993]`), and learn what the *built-in* functions `len`, `max` and `min` are used for. What happens if the list is empty?
- As discussed in class (on the 2nd of February), try to use a `for` loop over the elements of your list `l` to find *by yourself* both the minimum and maximum values of that list. The syntax is as simple as `for element in mylist: ...` (go to a new line, start an indented block).
- Compare your result by using `max` and `min`.
- *Bonus:* write your own function `mymax` that compute the max value of a list. How to deal with `l = []`, the *empty* list?
7. $\longrightarrow$ Start working on problems 1 and 2 below.
---
## Problem 1: the [Babylonian method](https://en.wikipedia.org/wiki/Babylonian_method):
This method has been presented in the first lecture on functions. We study it once more, with two different approaches (a fixed number of steps, and another more subtle strategy).
> You will write a program that compute iteratively an approximation for $\sqrt{K}$ (for some $K > 0$), by using only `for`/`while` loop, additions and divisions, and testing (`>`, `<` etc), and not the *built-in* `math.sqrt` function nor the `K ** 0.5` trick.
1. Ask a value for $K$, with $K > 0$,
2. Then use the Babylonian method, that *has been studied* in the **MA101** tutorial sheet on real sequences:
- define the first value as $x\_0 = K$,
- and then compute the next value *"as many times as needed"* (ie, as long as the precision of the approximation is not *good enough*), by $x\_{n+1} = \frac{x\_n + K/x\_n }{2}$.
3. For that second point when you update $x$, *you* can *choose* the number of steps to be executed (try with $4$ or $5$).
4. Try to execute that program with $K=2$. How many steps are needed to have an approximation of $\sqrt{2}$ up-to the $8^{\text{th}}$ digit? (*Hint:* $\sqrt{2} \simeq 1.41421356$ gives you the 8 first digits). Do you think that is not a lot, or a lot?
5. *Bonus:* transform your program of the last question 4. so that it now **defines a function** `mysqrt`, accepting **one** argument `K` and returning a *"not too bad"* approximation for $\sqrt{K}$ (with the *keyword* `return`).
6. *Bonus:* (harder) Do not ask the number of steps to the user, but a precision threshold $\varepsilon$ from which we will stop. The iterative method will run *as long as* $|x\_n - x\_{n+1}| \ge \varepsilon$.
---
## Problem 2: about prime numbers
> (**Definition:**) We recall that an *integer* number $n > 1$ is said to be **prime** if it has no divisor $k$ in the set $\\{2, 3, \dots, n-2, n-1 \\}$.
### 1) Checking for a number to be prime
1. First, create a simple program that ask the user the value of an input $n$ (an integer), and then check if $n$ is a prime numer of not, by the method of your choice,
2. Test your program with some numbers that you know are primes ($2, 3, 5, 7$ etc), and not primes ($4, 10, 2015, 10000$ etc). Which of $2011$, $2013$ or $2017$ is prime?
3. Define a function called `isPrime` that take *one* integer $n$ as argument, use your method from question 1.1), and `return` either `True` if $n$ **is prime** or `False` otherwise.
### 2) Printing the first $2015$ prime numbers (*harder*)
Now, try to use your function from question 1.3) and a `for` or `while` loop to print the first $2015$ prime numbers. Your output should look like:
<pre><code class="language-python" style="font-size:145%;">The 1th prime number is 2.
The 2th prime number is 3.
The 3th prime number is 5.
[....]
The 20th prime number is 71.
The 21th prime number is 73.
</code></pre>
#### 3) Optimizing our strategy ? (*Bonus*)
1. Update a little bit your function from question 1.3) to count the number of steps (how many times does the loop(s) get executed), and by printing it at the end.
2. Execute your program from qu.1) with different values of $n$. Can you guess how are linked $n$ and the number of steps of your function?
3. This is an informal approach to something called the **complexity** of a function (or of a program). This concept will be studied *just a little bit* in CS101, but will be one of the main focus of the *next* CS course (CS202, "Data structures and Algorithms").
---
## *Bonus* problem 3: introduction to modularity
1. First, use your program (Qu.3) that compute an approximation of $\frac{\pi^2}{6}$ to compute an approximation of $\pi^2$.
2. Then, use your other program (Problem 1) to compute an approximation of $\sqrt{\pi^2} = \pi$.
3. Can you compare that approx. value of $\pi$ with some other approximations that you know (e.g. $\frac{22}{7}$), or with `math.pi`? Does it seem good?
4. Change the two parameters (size of the partial sum for $\frac{\pi^2}{6}$, number of steps for the $\sqrt{\pi^2}$)), and observe how the precision of the approximation of $\pi$ is modified.
---
## Corrected problems
### Exercise 2
<pre><code class="language-python" style="font-size:145%;">n = int(raw_input("n = ? "))
# This xrange([start, ] end[, step]) create a list of regularly spaced integers.
# Default start is 0, default step is 1:
for i in xrange(1, n):
print "The", i, "th triangular number is", int(i*(i+1) / 2)
</code></pre>
---
### Exercise 3
<pre><code class="language-python" style="font-size:145%;">N = int(raw_input("For (pi**2)/6, size of the partial sum N = ? "))
partial_sum = 0
for n in xrange(1, N):
partial_sum += 1.0 / (n**2)
print "With", N, "terms in the partial sum, pi**2/6 is computated as", partial_sum
</code></pre>
---
### Problem 1 : Babylonian method
<pre><code class="language-python" style="font-size:145%;">k = 2.0 # goal. Question: does it has to be a float?
N = input("For the Babylonian method to approximate", K, "how much iterations to do : N = ")
x = k # x == x_0
for n in xrange(N): # here x == x_n
print "For the", n, "th step, x =", x
x = (x + k/x) / 2.0 # so now x == x_n+1
print "With", N, "steps of the iterative method, sqrt(", K, ") is computated as x =", x
# Bonus: checking the difference between x**2 and k
print "The difference abs(x**2 - ", k, ") = ", abs(x**2 - k),": is it not too big ?"
</code></pre>
---
### Problem 2 : Prime numbers
> This first example show you that a Python program can be correctly executed and produce a good output but can be ugly as *hell* and not readable:
<pre><code class="language-python" style="font-size:120%;"># A very ugly and unreadable solution in one line
# We use Pierre Dusart's formula for the upper bound
# Reference: https://fr.wikipedia.org/wiki/Formules_pour_les_nombres_premiers#cite_note-3
import math;l=lambda p:math.log(p,2);x=xrange;print(lambda n:"\n".join(map(lambda(i,m):"The {}th prime number is {}.".format(i+1,m),enumerate(filter(lambda n:all(map(lambda k:((n%k)!=0),x(2,int(1+n**.5)))),x(2,int(n*(l(n)+l(l(n))-.5))))[:n]))))(2015)
</code></pre>
> Therefore, not only you need to learn how to solve problems by programming, but you should be careful to do so *elegantly* !
> You (and us, and other people) need to be able to read again your programs, and **understand** them easily!
<pre><code class="language-python" style="font-size:145%;"># A simpler solution !
n = input("n = ?")
if n < 2:
result = False
else:
result = True
for k in xrange(2, n): # k from 2 to n-1 !
if (n % k) == 0:
# k is a divisor of n ==> n is not prime!
result = False
break # Exit the for loop RIGHT NOW!
if result:
print n, "is a prime number !"
else:
print n, "is NOT a prime number !"
</code></pre>
> That's all for this week!
---
<ul class="pager">
<li class="previous"><a href="../w06/">← Previous lab (First Mid Term Exam week)</a></li>
<li class="next"><a href="../w08/">Next lab →</a></li>
</ul>
]]>