# May 11th

## Algorithms v.0.0.1

An algorithm is a process/recipe which takes some inputs and generates a desired output.

• You have some building atomic building blocks: integers, boolean values, strings
• You have some molecular building blocks: lists, arrays, dictionaries, matrices
• You have some flow control elements: for loops, if statements, while loops
• By mastering these you can accomplish huge tasks.

### Example algorithms

Goal:Add a list of integers $$[a_1, \ldots, a_n]$$.

    
#this is python code
the_sum = 0
for a_i in input_list:
the_sum = the_sum + a_i
return the_sum



Goal:Find the distinct values in a list.

    
def distinct_elements(input_list):
if len(input_list) == 0:
return input_list
for i in range(1, len(input_list)):
candidate_value = input_list[i]
seen_before = False
if candidate_value == old_value:
seen_before = True
break
if not seen_before:


1. Write an algorithm for computing greatest common divisor of $$a$$ and $$b$$.
3. Use Horner's method to evaluate $$f(-1)$$ where $$f = -4x^3 + 6x^2 +5x -4$$. Count the number of multiplications.
4. Write an algorithm which, when given a list of $$n$$ distinct values $$a_1, \ldots, a_n$$, outputs all subsets of $$\{a_1, \ldots, a_n \}$$. How many operations are done when given a list of 5 items? $$n$$ items?
5. Describe an algorithm which is given a value $$x$$, a power $$p$$, and a modulus $$M$$ and calculates $$x^p \mod{M}$$. How many arithmetic operations do you need?