**Location:** `assignment-problems/flatten.py`

**Grading:** 1 point for passing test, and then (assuming it passes the test) 1 point for code quality

Write a function `flatten`

which takes a nested dictionary and converts it into a flat dictionary based on the key names. You can assume that the nested dictionary only has one level of nesting, meaning that in the output, each key will have exactly one underscore.

Assert that your function passes the following test:

```
>>> colors = {
'animal': {
'bumblebee': ['yellow', 'black'],
'elephant': ['gray'],
'fox': ['orange', 'white']
},
'food': {
'apple': ['red', 'green', 'yellow'],
'cheese': ['white', 'orange']
}
}
>>> flatten(colors)
{
'animal_bumblebee': ['yellow', 'black'],
'animal_elephant': ['gray'],
'animal_fox': ['orange', 'white'],
'food_apple': ['red', 'green', 'yellow'],
'food_cheese': ['white', 'orange']
}
```

**Location:** `assignment-problems/convert_to_base_2.py`

**Grading:** 1 point for passing test, and then (assuming it passes the test) 1 point for code quality

Write a function `convert_to_base_2`

that converts a number from base-10 to base-2. Assert that it passes the following test:

```
>>> convert_to_base_2(19)
10011
```

Hint: use $\log_2$ to figure out how many digits there will be in the binary number. Then, fill up the binary number, repeatedly subtracting off the next-largest power of 2 if possible.

**Location:** `assignment-problems/linear_encoding_cryptography.py`

**Grading:** for each part, you get 1 point for passing test, and then (assuming it passes the test) 1 point for code quality

In Assignment 1, we encountered the trivial encoding function which maps

`' '`

$\rightarrow 0,$`'a'`

$\rightarrow 1,$`'b'`

$\rightarrow 2,$

and so on.

Using a linear encoding function $s(x) = 2x+3,$ the message `'a cat'`

can be encoded as follows:

Original message:

`'a cat'`

Trivial encoding:

`[1, 0, 3, 1, 20]`

Linear encoding:

`[5, 3, 9, 5, 43]`

**a.** Create a function `encode(string,a,b)`

which encodes a string using the linear encoding function $s(x) = ax+b.$ Assert that your function passes the following test:

```
>>> get_encoding('a cat', 2, 3)
[5, 3, 9, 5, 43]
```

**b.** Create a function `decode(numbers,a,b)`

which attempts to decode a given list of `numbers`

using the linear encoding function $s(x) = ax+b.$

To do this, you should apply the inverse encoding $s^{-1}(x) = \dfrac{x-b}{a},$ to all the numbers in the list and then check if they are all integers in the range from $0$ to $26$ (inclusive). If they are, then return the corresponding letters; if they are not, then return False.

Assert that your function passes the following tests:

```
>>> decode([5, 3, 9, 5, 43], 2, 3)
'a cat'
for debugging purposes, here's the scratch work for you:
[(5-3)/2, (3-3)/2, (9-3)/2, (5-3)/2, (43-3)/2]
[1, 0, 3, 1, 20]
'a cat'
>>> decode([1, 3, 9, 5, 43], 2, 3)
False
for debugging purposes, here's the scratch work for you:
[(1-3)/2, (3-3)/2, (9-3)/2, (5-3)/2, (43-3)/2]
[-1, 0, 3, 1, 20]
False (because -1 does not correspond to a letter)
>>> decode([5, 3, 9, 5, 44], 2, 3)
False
for debugging purposes, here's the scratch work for you:
[(5-3)/2, (3-3)/2, (9-3)/2, (5-3)/2, (44-3)/2]
[1, 0, 3, 1, 20.5]
False (because 20.5 does not correspond to a letter)
```

**c.** Decode the message

```
[377,
717,
71,
513,
105,
921,
581,
547,
547,
105,
377,
717,
241,
71,
105,
547,
71,
377,
547,
717,
751,
683,
785,
513,
241,
547,
751],
```

given that it was encoded with a linear encoding function $s(x) = ax+b$ where $a,b \in \{ 0, 1, 2, \ldots, 100 \}.$

You should run through each combination of $a$ and $b,$ try to decode the list of numbers using that combination, and if you get a valid decoding, then print it out. Then, you can visually inspect all the decodings you printed out to find the one that makes sense.

**Location:** `assignment-problems/convert_to_base_10.py`

**Grading:** 1 point for passing test, and then (assuming it passes the test) 1 point for code quality

Write a function `convert_to_base_10`

that converts a number from base-2 (binary) to base-10 (decimal). For example, the binary number $10011$ corresponds to the decimal number
$$
1 \cdot 2^{4} + 0 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 19.
$$

Assert that your function passes the following test:

```
>>> convert_to_base_10(10011)
19
```

**Location:** `assignment-problems/make_nested.py`

**Grading:** you get 1 point for passing the test, and then (assuming it passes the test) 1 point for code quality

Write a function `make_nested`

which takes a "flat" dictionary and converts it into a nested dictionary based on underscores in the the key names. You can assume that all keys have exactly one underscore.

Assert that your function passes the following test:

```
>>> colors = {
'animal_bumblebee': ['yellow', 'black'],
'animal_elephant': ['gray'],
'animal_fox': ['orange', 'white'],
'food_apple': ['red', 'green', 'yellow'],
'food_cheese': ['white', 'orange']
}
>>> make_nested(colors)
{
'animal': {
'bumblebee': ['yellow', 'black'],
'elephant': ['gray'],
'fox': ['orange', 'white']
},
'food': {
'apple': ['red', 'green', 'yellow'],
'cheese': ['white', 'orange']
}
}
```

**Location:** `assignment-problems/stack.py`

**Grading:** you get 0.5 points for passing each test, and then (assuming your code passes all the tests) 2 points for code quality.

Implement a stack. That is, create a class `Stack`

which operates on an attribute `data`

using the following methods:

`push`

: add a new item on top of the stack`pop`

: remove the top (rightmost) item from the stack`peek`

: return the top item without modifying the stack

Assert that your class passes the following sequence of 5 tests. (You should write 5 `assert`

statements in total.)

```
>>> s = Stack()
>>> s.data
[]
>>> s.push('a')
>>> s.push('b')
>>> s.push('c')
>>> s.data
['a', 'b', 'c']
>>> s.pop()
>>> s.data
['a', 'b']
>>> s.peek()
'b'
>>> s.data
['a', 'b']
```

**Location: assignment-problems/union_intersection.py**

**a.** (1 point for code quality; 1 point for passing test)

Write a function `intersection`

that computes the intersection of two lists. Assert that it passes the following test:

```
>>> intersection([1,2,'a','b'], [2,3,'a'])
[2,'a']
```

**b.** (1 point for code quality; 1 point for passing test)

Write a function `union`

that computes the union of two lists. Assert that it passes the following test:

```
>>> union([1,2,'a','b'], [2,3,'a'])
[1,2,3,'a','b']
```

**Location: assignment-problems/count_characters.py**

(2 points for code quality; 2 points for passing test)

Write a function `count_characters`

that counts the number of each character in a string and returns the counts in a dictionary. Lowercase and uppercase letters should not be treated differently.

Assert that your function passes the following test:

```
>>> countCharacters('A cat!!!')
{'a': 2, 'c': 1, 't': 1, ' ': 1, '!': 3}
```

**Location: assignment-problems/recursive_sequence.py**

Consider the sequence defined recursively as

$$a_n = 3a_{n-1} -4, \quad a_1 = 5.$$**a.** (1 point for code quality; 1 point for passing test)

Write a function `first_n_terms`

that returns a list of the first $n$ terms of the sequence: $[a_1, a_2, a_3, \ldots, a_{n}]$

Assert that your function passes the following test:

```
>>> first_n_terms(10)
[5, 11, 29, 83, 245, 731, 2189, 6563, 19685, 59051]
```

**b.** (1 point for code quality; 1 point for passing test)

Write a function `nth_term`

that computes the $n$th term of the sequence using recursion. Here's the video that you were asked to watch before class, in case you need to refer back to it: https://www.youtube.com/watch?v=zbfRgC3kukk

Assert that your function passes the following test:

```
>>> nth_term(10)
59051
```

Getting started...

Join eurisko-us.slack.com

Sign up for repl.it

Create a bash repl named

`assignment-problems`

Create a file

`assignment-problems/test_file.py`

Sign up for github.com

On repl.it, link

`assignment-problems`

to your github and push up your work to github. Name your commit "test commit".After you complete this assignment, again push your work up to github. Name your commit "completed assignment 1".

**Location: assignment-problems/is_symmetric.py**

**Note: This problem is worth 1 point for passing both tests, plus another 1 point for code quality (if you pass the tests). So, the rubric is as follows:**

0/2 points: does not pass both tests

1/2 points: passes both tests but code is poor quality

2/2 points: passes both tests and code is high quality

Write a function `is_symmetric(input_string)`

that checks if a string reads the same forwards and backwards, and `assert`

that your function passes the following tests:

```
>>> is_symmetric('racecar')
True
>>> is_symmetric('batman')
False
```

To be clear -- when you run `is_symmetric.py`

, your code should print the following:

```
>>> python is_symmetric.py
testing is_symmetric on input 'racecar'...
PASSED
testing is_symmetric on input 'batman'...
PASSED
```

**Location: assignment-problems/letters_numbers_conversion.py**

**a.** (1 point for passing test, 1 point for code quality)

Write a function `convert_to_numbers(input_string)`

that converts a string to a list of numbers, where space = 0, a = 1, b = 2, and so on. Then, `assert`

that your function passes the following test:

```
>>> letters2numbers('a cat')
[1,0,3,1,20]
```

**b.** (1 point for code quality, 1 point for passing test)

Write a function `convert_to_letters(input_string)`

that converts a list of numbers to the corresponding string, and `assert`

that your function passes the following test:

```
>>> convert_to_letters([1,0,3,1,20])
'a cat'
```

To be clear -- when you run `letters_numbers_conversion.py`

, your code should print the following:

```
>>> python letters_numbers_conversion.py
testing convert_to_letters on input [1,0,3,1,20]...
PASSED
testing convert_to_numbers on input 'batman'...
PASSED
```

(2 points for passing tests, 2 points for code quality)

Write a function `is_prime(n)`

that checks if an integer input $n > 1$ is prime by checking whether $m | n$ for any integer $m \in \left\{ 2, 3, \ldots, \left\lfloor \dfrac{n}{2} \right\rfloor \right\}.$

$m|n$ means "$m$ divides $n$"

$\left\lfloor \dfrac{n}{2} \right\rfloor$ is called the "floor" of $\dfrac{n}{2},$ i.e. the greatest integer that is less than or equal to $\dfrac{n}{2}.$

(Hint: Check for divisibility within a for loop.)

Also, `assert`

that your function passes the following tests:

```
>>> is_prime(59)
True
>>> is_prime(51)
False
```

To be clear -- when you run `is_prime.py`

, your code should print the following:

```
>>> python is_prime.py
testing is_prime on input 59...
PASSED
testing is_prime on input 51...
PASSED
```

In [ ]:

```
```