Quiz Review Questions

Conceptual Questions

Dictionaries

1. Dictionaries in Python can have duplicate keys. (T/F)
2. Dictionaries in Python can be nested, meaning a dictionary can contain another dictionary as a value. (T/F)

Unit Tests

1. All pytest test function names must begin with test_. (T/F)
2. If a unit test does NOT pass, this means that one of the assertions in the test is False. (T/F)
3. Test functions should be written in a file with a name followed by _test.py. (T/F)
4. Pytest is the only unit testing framework available for Python. (T/F)
5. Unit tests in Pytest are written in separate files from the code they are testing. (T/F)

Runtime Analysis

1. A function with a big-O notation of O(n) will always run faster than a function with a big-O notation of O(n^2) for all input sizes. (T/F)
2. Big-O notation considers the constants and lower-order terms when analyzing the runtime of an algorithm. (T/F)
3. Big-O notation can be used to analyze both time complexity and space complexity of algorithms. (T/F)
4. Big-O notation provides a precise measurement of the actual runtime of an algorithm on a specific machine. (T/F)
5. Big-O notation accounts for variations in performance due to factors like hardware and compiler optimizations. (T/F)
6. If an algorithm has a time complexity of O(1), it means its runtime is constant and independent of the input size. (T/F)
7. What does it mean for an input to be a “worst case” input?
8. What is a worst-case input for a search function?
9. What is a worst-case input for a sort function?

Solutions

Unit Tests Short Response

1. This function finds the first word in a list of str with an evenlength.

    def find_even(words: list[str]) -> str:
        idx: int = 0
        while idx < len(words):
            if len(words[idx]) % 2 == 0:
                return words[idx]
            idx += 1
        return ""

Fill in this unit test with a use case.

    def test_find_even_use_case() -> None:
            """ Put code here. """

2. This function removes the first word in a list of str with an even length.

    def remove_first_even(words: list[str]) -> None:
        idx: int = 0
        condition: bool = True
        while (idx < len(words)) and condition:
            if len(words[idx]) % 2 == 0:
                words.pop(idx)
                condition = False
            idx += 1

Fill in this unit test with a use case.

    def test_remove_first_even_use_case() -> None:
            """ Put code here. """

Solutions

Function Writing

1. value_exists:

• The function name is value_exists and is called with a dict[str,int] and an int as an argument.
• The function should return a bool.
• The function should return True if the int exists as a value in the dictionary, and False otherwise.
• The function should not mutate (modify) the input dict.
• Explicitly type variables, parameters, and return types.
• The following REPL examples demonstrate expected functionality of your value\_exists function:

>>> test_dict: dict[str,int] = {"a": 2, "b": 4, "c": 7, "d": 1}
>>> test_val: int = 4
>>> value_exists(test_dict, test_val)
True
>>> value_exists(test_dict, 5)
False

2. plus_or_minus_n:

• The function name is plus_or_minus_n and is called with inp: dict[str,int] and n: int as an argument.
• The function should return None. It instead mutates the input dictionary inp.
• The function should check if each value in inp is even or odd. If it is even, add n to that value. If it is odd, subtract n.
• Explicitly type variables, parameters, and return types.
• The following REPL examples demonstrate expected functionality of your function:

>>> test_dict: dict[str,int] = {"a": 2, "b": 4, "c": 7, "d": 1}
>>> test_val: int = 4
>>> plus_or_minus_n(test_dict, test_val)
>>> test_dict
{"a": 6, "b": 8, "c": 3, "d": -3}

Solutions

Memory Diagrams

Focus on the Dictionary memory diagrams on the practice memory diagram page.

Quiz Review Solutions

Conceptual Questions Solutions

Dictionaries

1. False. It can have duplicate values, but the keys must be unique.
2. True. E.g. example: dict[str, dict[str, str]] = {"a": {"Hello": "World"}}

Unit Tests

1. True
2. True
3. True
4. False. It is the one we use for this class, but there are other frameworks!
5. True

Runtime Analysis

1. False. n IS faster that n², but given that this is Big-O notation, it’s only considering the worst case input. In other words, it’ll run faster for a worst-case input, but not necessarily for every possible input.

2. False. For example if a runtime is computed to be O(n² + 2n + 3), that’ll simply be represented as O(n²).

3. True

4. False. It’s a general performance approximation in terms of input size.

5. False.

6. True.

7. This is an input that will result in the longest possible runtime of the algorithm. In other words, this is the input that will reflect the Big-O runtime.

8. Searching for an element that is not in the list. This means you’ll have to look at the entire list before realizing that it’s not there.

9. A descending list. This means every element is in the wrong location and will need to be moved. (This is what you do in the runtime exercise.)

Unit Tests Short Response Solutions

These can have many possible answers! Here is just one example.

    def test_find_even_use_case() -> None:
            test_input: list[str] = ["Hello", "Hi", "Howdy", "Hiya"]
            assert find_even(test_input) == "Hi"

    def test_remove_first_even_use_case() -> None:
        test_input: list[str] = ["Hello", "Hi", "Howdy", "Hiya"]
        remove_first_even(test_input)
        assert test_input == ["Hello", "Howdy", "Hiya"]

Function Writing Solutions

1. value_exists:

    def value_exists(d: dict[str, int], num: int) -> bool:
        for key in d:
            if d[key] == num:
                return True
        return False

    def value_exists(d: dict[str, int], num: int) -> bool:
        exists: bool = False
        for key in d:
            if d[key] == num:
                exists = True
        return exists

2. plus_or_minus_n:

    def plus_or_minus_n(inp: dict[str, int], n: int) -> None:
        for key in inp:
            if inp[key] % 2 == 0:
                inp[key] = inp[key] + n
            else: # element is odd
                inp[key] = inp[key] - n

    def plus_or_minus_n(inp: dict[str, int], n: int) -> None:
        for key in inp:
            if inp[key] % 2 == 0:
                inp[key] += n
            else: # element is odd
                inp[key] -= n