# Algorithms

Definition: An algorithm is a concrete way (think a concrete recipe) to implement a function, i.e, to link a given input to a desired output.

Remark: You may have different algorithms implementing the same function. Some may be better than other in terms of the the output precision, execution speed, easiness of implementation, readability, etc...

In programming, you have essentially two main tools to implement an algorithms:

• branching mechanisms, which constitute the logical brain of the algorithm
• looping mechanisms, which constitute the algorithm muscles

## Branching mechanisms (Brain)

### Implementing a simple choice depending on a logical condition



In [ ]:

def guessWhatIamThinking(x):
if x > 8:
print 'You win!'
else:
print 'you loose'




In [ ]:

guessWhatIamThinking(10)



### Implementing a cascading series of options



In [ ]:

def parseOptions(option):

if option == 'a':
print 'the option a has been chosen'
elif option == 'b':
print 'the chosen option is b'
elif option == 'c':
print 'the chosen option is c'
else:
print 'No options has been choosen'

parseOptions('c')



## Looping mechanisms (Muscles)

### Looping over the integers



In [ ]:

tdef startGame(numberOfPlay):
for i in range(numberOfPlay):
userInput = float(raw_input('What I am thinking? '))
guessWhatIamThinking(userInput)
print 'Game Over'




In [ ]:

startGame(5)



### Looping over string letters



In [ ]:

def nucleotideCount(DNA):
numA = 0; numC = 0; numG = 0; numT =0
for nucleotide in DNA:
if nucleotide == 'A':
numA = numA + 1
elif nucleotide == 'C':
numC = numC + 1
elif nucleotide == 'T':
numT = numT + 1
elif nucleotide == 'G':
numG = numG + 1
else:
print """An unfortunate mutation has occurred,
or this DNA is not of terrestrial origin"""

print 'Number of A is ', numA
print 'Number of C is ', numC
print 'Number of G is ', numG
print 'Number of T is ', numT




In [ ]:

dna = 'AACCGGTT'
nucleotideCount(dna)



### Looping over lists



In [ ]:

myList = ['hello', 34, 8.34, True, True and False]




In [ ]:

def listType(aList):

for item in aList:
print(type(item))




In [ ]:

listType(myList)



### Conditinal looping



In [ ]:

def sumFirstInteger(n):
counter = 0; result = 0

while counter <= n:
result  = result + counter
counter = counter + 1

return result




In [ ]:

mySum = sumFirstInteger(13)
mySum




In [10]:

def greetMe():

while True:

userInput = raw_input("What's your name? \n>")

if userInput == 'quit':
break
else:
print 'Hello ', userInput




In [11]:

greetMe()




>Antoine
Hello  Antoine
>quit



## Data structures and algorithms

### Lists

Definition: A list is a ordered sequence of possibly inhomogeneous elements. Python lists are the programmatic embodiement of the mathematical notion of $n$-tuple:

$$a = (a_1, a_2, \dots, a_n)\in A_1 \times A_2 \times \cdots \times A_n,$$

where the $i^{th}$ element belongs to the set $A_i$ (the sets being $A_i$s potentially disticts).

In Python, one can use the same notation as in math, in which case the list elements won't be able to be modified after having been assigned. In the Python lingo, these constant lists are also called tuples.



In [4]:

a = ('Bob', 32, True)
a




Out[4]:

('Bob', 32, True)



To create mutable list (i.e. a list whose elements can be further modified), Python uses square brackets instead of parenthesis:



In [3]:

b = ['Marcel', 12, False]
b




Out[3]:

['Marcel', 12, False]



In math, one uses the subscript notation $a_i$ to denote the $i^{th}$ element of a list $a$. Instead of that notation, Python uses the square bracket operator (caution: in Python indices start at zero):



In [9]:

a[2]




Out[9]:

True




In [10]:

b[3]




---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-10-0a402005bccb> in <module>()
----> 1 b[3]

IndexError: list index out of range



Observed that elements from a Python tuple can be retrived but not reassigned, as opposed to Python lists, which is why Python list are called mutable and Python tuples are called immutable:



In [8]:

b[2] = False




In [ ]:




In [ ]:



Algorithmically, one may be interseted in lists for various reasons:

• looping over elements (as we have already seen)

• retrieving sublists of a given lists

• sorting the list elements according to a particular criterium

Sublists

One retrieves from a given Python's list, say my_list, a sublist of consecutive indices by indicating the sublist range or "slice":

my_list[3:6]
returns the sublist
[my_list[3], my_list[4], my_list[5]]


In [ ]:



The function len(my_list) returns the length of my_list



In [ ]:


• The range $[m:n]$ is open-ended: element $m$ is included but not the element $n$
• $[:n]$ is a shorthand for $[0:n]$
• $[m:]$ is a shorthand for $[m:n]$ where $n$ is the list lenght
• Negative numbers can also be used to indicate positions and ranges:
•  my_list[-1]  is the last element of the list
•  my_list[-2]  is the element before the last element, etc.
• etc.

Sorting

### Dictionaries



In [ ]:



### Sets



In [ ]: