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
def add_list(input_list):
    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
    answer_list = [input_list[0]]
    for i in range(1, len(input_list)):
        candidate_value = input_list[i]
        seen_before = False
        for old_value in answer_list:
            if candidate_value == old_value:
                seen_before = True
                break
        if not seen_before:
            answer_list.append(candidate_value)
    return answer_list
    
    

We'll do polynomial evaluation in two ways on the board (see pages 250-251)

Problems

1. Write an algorithm for computing greatest common divisor of \(a\) and \(b\).
2. Do the same for least common multiple.
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?