Assignment Problems for Cohort 2¶

Problem 4-1¶

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']
}

Problem 4-2¶

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.

Problem 4-3¶

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

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.

Problem 3-1¶

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

Problem 3-2¶

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']
  }
}

Problem 3-3¶

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']

Problem 2-1¶

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']

Problem 2-2¶

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}

Problem 2-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

Problem 1-1¶

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".

Problem 1-2¶

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

Problem 1-3¶

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

Problem 1-4¶

(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