## Attachment 'introduction_to_imperative_programming.rst'

Download# First step in imperative programming

### Conditional jump, function and loop

- In python, conditional jumps can be written with the following syntax :

sage: a = 30 ....: if( a % 2 == 0 ): ....: print( "a est even." ) ....: else: ....: print( "a est odd." )

### Exercise :

Let "a" be the age of an human, give an algorithm that returns :

- "child", if it's age is lesser than 13
- "teenager", if it's age is greater that 13 and lesser than 18
- "adult", if it's age is greater or equal to 18
- "Alien", otherwise ;).

sage: a = -3 ....: if a > 0 and a < 13: ....: print('child') ....: elif a >= 13 and a< 18: ....: print('teenager') ....: elif a>=18: ....: print('adult') ....: else: ....: print('alien')

### Function :

A function can be declared with the keyword **def**. Come back to the
last exercise and create a function characteristic(age) that takes as parameter
the age of an human and returns the previous characteristic.

sage: def characteristic(age): ....: if a > 0 and a < 13: ....: return('child') ....: elif a >= 13 and a< 18: ....: return('teenager') ....: elif a>=18: ....: return('adult') ....: else: ....: return('alien') sage: characteristic(12)

**Exercise**: Write a function that takes, in parameter, a real x
and then returns the maximum between x^2 and 2x+1

sage:

### The Loops

Find in the documentation how to use the function *range()*.

sage: range?

**Exercise** : List, by using the function *range*, all the even values
running from -5 to 21.

sage:

### The loop For :

In python, we can repeat the execution of some code. We call a loop each run of that code.

Writing loop can be done in the following way :

sage: i=2 ....: n=10 ....: for i in range(n): ....: print(i) ....: print("C est la fin") ....: print(i) sage: for e in Subsets(4): ....: print( e )

**Exercise**: Write a function f that takes an integer n and
then returns the value u_n defined by u_n=u_{n-1}+u_{n-1} with
u_{0}=0 and u_1=1.

sage:

### The loop WHILE :

Loops can be written with the following format:

sage: n=10 ....: i=2 ....: while i < n: ....: print(i) ....: i = i+1 ....: print("sortie i : " + str(i))

**Exercise**: Give a function that takes an integer n as parameter and return
the integer part of log_2(n).

sage:

### The lists

- In python, lists are written by using with brackets. For example, the list

[1, 2, 3, 4] can be coded with those lines :

sage: l = [1,2,3,4] sage: l sage: l.append(10) sage: l

- We can write some lists by using loops :

sage: l = [] ....: for i in range(10): ....: l.append(i) ....: l

- We can also make it in one line :

sage: [i^2 for i in range(10)]

- We can create list of different objects. For example, the following code generate all the permutations of size 4:

sage: [p for p in Permutations(4)]

- In fact it is possible to write :

sage: P = Permutations(4) sage: P

- It is possible to use loops and conditional jumps inside lists. In the next example, we select all the permutations that finish on a descent. We recall that i is a descent in a permutation p if p(i) ge p(i+1).

sage: [p for p in Permutations(5) if p(4)>p(5) ]

- It is possible to obtain the size of a list :

sage: l = [p for p in Permutations(5) if p(4)>p(5)] sage: len( l )

**Exercise**: Write a function to list all fixed points of a given permutation.
Then, write another function that lists all permutations without fixed point.

sage:

- We can generate the generating function of all permutations that have no fixed points. We will assume that x counts the size of the permutations.

sage: def nb_without_fp(n): ....: return len( ....: [ ....: p ....: for p in Permutations(n) ....: if len(fixed_points(p))==0 ....: ] ....: ) sage: S = sum( nb_without_fp(n)*x^n for n in range(8) ) sage: S

- We can collect the sequence and obtain information about that sequence with OEIS.

sage: oeis([ nb_sans_pf(n) for n in range(8) ])

### Exercises

- By using the previous examples, write a program that gives the list of all even integers that are lesser than 30.

sage:

- Propose an algorithm that computes the binomial binom{n}{k} by using the Pascal triangle : binom{n+1}{k}=binom{n}{k}+binom{n}{k-1}.

sage:

- In fact, the function
*binomial*exists in Sage. Find that function.

sage:

### The dictionaries

- Dictionaries are data structures that allow to associate an object called key

to another object called value. In a dictionary, all keys are different. In fact a dictionary is a map with finite support.

sage: D = {1:4, 2:6, 3:6, 8:6} sage: D {1: 4, 2: 6, 3: 6, 8: 6}

sage: D.keys()

**Question**: How do you proceed to :

- determine if a dictionary contains a particular key;
- get a value associated to a key;
- get the number of keys.

sage:

**Exercise** Write a function that takes as parameter a list of integers and
then returns a dictionary where

- keys are all the integers present inside the list
- values, associated with the key, are the number of key repetitions inside the list.

sage:

### The generators

- Generators are programs that are useful to enumerate objects on demand. For example, Permutations(3) contains a generator of permutations of size 3. We obtain that generator by typing :

sage: generator = iter( Permutations(3) )

- We can enumerate those permutations by writing :

sage: print( next( generator ) ) sage: print( next( generator ) ) sage: print( next( generator ) ) sage: print( next( generator ) ) sage: print( next( generator ) ) sage: print( next( generator ) )

- An error is raised when iterator reach the end of the iterator function.

sage: print( next( generator ) )

- Generators allow to obtain object one by one without computing a list of all the elements. This is useful when the list is big or infinite. For example, we can compute a generator for all the permutations:

sage: generator = iter(Permutations()) sage: print( next(generator) ) sage: print( next(generator) ) sage: print( next(generator) ) sage: print( next(generator) ) sage: print( next(generator) ) sage: print( next(generator) ) sage: print( next(generator) ) sage: print( next(generator) )

- It is possible to use iterators inside a loop :

sage: gen = iter( Permutations(3) ) ....: for p in gen: ....: print( p )

- You can implement your own generator. It suffices, during the enumeration,
to return the current value by using the keyword
*yield*. At the first use of yield, python will create a generator that stores in memory all the states of the calculus. At each*next*the generator will continue the calculus and will return the next value of the enumeration.

sage: def generator( n ): ....: for i in range(n): ....: yield i**2 sage: gen = generator( 30 ) ....: print( next(gen) ) ....: print( next(gen) ) ....: print( next(gen) ) ....: print( next(gen) ) ....: print( next(gen) ) ....: print( next(gen) )

### Exercises :

- Write a generator that enumerates all permutations of size n (without using
the Sage generator of
*Permutations*).

sage:

- Write a generator that enumerates all the compositions of an integer. A composition of n is a list l_1, l_2, ldots, l_k of integers such that l_1 + l_2 + ldots + l_n = n.

sage:

- Find in the Sage documentation a composition generator.

sage:

### Euler project

- Train yourself by solving problems from the Euler Project Website :

## Attached Files

To refer to attachments on a page, use**, as shown below in the list of files. Do**

`attachment:filename`**NOT**use the URL of the

`[get]`link, since this is subject to change and can break easily.

- [get | view] (2016-12-03 14:31:55, 316.9 KB) [[attachment:First steps in Sage--Solution.ipynb]]
- [get | view] (2016-11-21 20:41:01, 18.1 KB) [[attachment:First steps in Sage.ipynb]]
- [get | view] (2016-11-22 10:07:49, 802.7 KB) [[attachment:Polytope playground.ipynb]]
- [get | view] (2016-11-22 09:18:53, 440.8 KB) [[attachment:VincentDelecroix-beamer_jerusalem_2016.pdf]]
- [get | view] (2016-11-22 09:23:40, 512.6 KB) [[attachment:VincentDelecroix-notebook_Jerusalem_2016.ipynb]]
- [get | view] (2016-11-22 09:23:55, 551.0 KB) [[attachment:VincentDelecroix-notebook_Jerusalem_2016.pdf]]
- [get | view] (2016-11-23 07:48:46, 11.4 KB) [[attachment:graphs_and_lp.ipynb]]
- [get | view] (2016-11-23 07:48:54, 119.6 KB) [[attachment:graphs_and_lp.pdf]]
- [get | view] (2016-12-03 16:29:31, 26.9 KB) [[attachment:introduction_to_imperative_programming--Solution.ipynb]]
- [get | view] (2016-11-22 01:04:56, 14.6 KB) [[attachment:introduction_to_imperative_programming.ipynb]]
- [get | view] (2016-11-22 01:04:13, 8.2 KB) [[attachment:introduction_to_imperative_programming.rst]]
- [get | view] (2016-12-03 15:41:46, 27.6 KB) [[attachment:object_oriented_python--Solution.ipynb]]
- [get | view] (2016-11-21 21:42:57, 21.3 KB) [[attachment:python_object_oriented.ipynb]]
- [get | view] (2016-11-21 13:12:56, 14.9 KB) [[attachment:repr_theory_tutorial.ipynb]]
- [get | view] (2016-11-21 13:11:10, 609.7 KB) [[attachment:scrimshaw_talk.pdf]]

You are not allowed to attach a file to this page.