Quiz 03 Practice Problems

Algorithmic Complexity

  1. True or False: A function with a big-O notation of O(n) will always run faster than a function with a big-O notation of O(n2) for all inputs.

  2. What type of input does Big-O notation consider?

    1. Best Case

    2. Worst Case

    3. Average Case

  3. True or False: Big-O notation provides a precise measurement of the actual runtime of an algorithm on a specific machine.

  4. If an algorithm has a time complexity of O(1), it means its runtime is:

    1. Linear

    2. Constant

    3. Quadratic

    4. Exponential

  5. If an algorithm has a time complexity of O(n), it means its runtime is:

    1. Linear

    2. Constant

    3. Quadratic

    4. Exponential

  6. If an algorithm has a time complexity of O(n2), it means its runtime is:

    1. Linear

    2. Constant

    3. Quadratic

    4. Exponential

  7. If an algorithm has a time complexity of O(2n), it means its runtime is:

    1. Linear

    2. Constant

    3. Quadratic

    4. Exponential

  8. Consider the following function:

    def foo(outer_input: list[str], inner_input: list[str]) -> None:
    """Nested loop!"""
    for x in outer_input:
        for y in inner_input:
            print(f"{x} and {y}!")
    return None

    8.1. Assuming outer_input and inner_input both have length n, what is the big-O runtime of the function foo?

    8.2. If outer_input has length n2 and inner_input has length n, what would be the big-O runtime of the function foo?

  9. Which of the following is true about algorithms?

    1. The result of an algorithm is only affected by its inputs.

    2. An algorithm can have side effects which affect its environment.

    3. An algorithm can take an infinite number of steps to complete.

    4. The only effect that an algorithm can have is on its result.

  10. Consider the following code snippets:

    unc_pid_range: dict[int, bool] = {730000000: False, 730000001: False, ..., 730999999: False}
prime_numbers: list[int] = [2, 3, 5, 7, ..., 1000000007]

for pid in unc_pid_range:
    if pid in prime_numbers:
        unc_pid_range[pid] = True
        print(f"Prime PID found: {pid}!")
    unc_pid_range: list[int] = [730000000, 730000001, ..., 730999999]
prime_numbers: dict[int, bool] = {2: False, 3: False, 5: False, 7: False, ..., 1000000007: False}

for pid in unc_pid_range:
    if pid in prime_numbers:
        prime_numbers[pid] = True
        print(f"Prime PID found: {pid}!")

    Let n be the size of the unc_pid_range and let m be the size of both the prime_numbers in both code snippets. What are the runtimes of the two code snippets in big-O notation in terms of m and n? Which would you choose to use if you cared the most about speed?

SOLUTIONS

  1. This is False. A function with big-O notation of O(n) will theoretically run faster than a function with a big-O notation of O(n2) on a worst case input.

  2. Worst Case.

  3. False.

  4. Constant

  5. Linear

  6. Quadratic

  7. Exponential

  8. 8.1. O(n2)

    8.2. O(n3)

  9. The answer is b, since algorithms are a finite series of steps (eliminating c) and can be affected by and have an effect on their environment (eliminating a and d, and showing that b is true).

  10. The first code snippet runs in time O(m ⋅ n) and the second runs in time O(n). This is because the lookup time (the in operator) takes constant time on a dictionary and linear time on a list, so in the first snippet you do an O(m) operation n times so $O(m n), but in the second you do an O(1) operation n times so O(n). Thus if you care about speed the most you would use the second method.

Unit Tests

  1. Testing Syntax:

    1.1. What key word do we use within a test function to ensure that a boolean expression is true?

    1.2. What does each test function’s name have to begin with?

    1.3. What does each test file’s name have to end with?

  2. If a function passes all of its associated unit tests, then the function is implemented correctly for all possible inputs (True/False).

  3. Consider the following code snippet:

def fill_list(num: int, length: int) -> list[int]:
    """Fill a list with a single value."""
    result: list[int] = []

    i: int = 0
    while i < length:
        result.append[num]
        i += 1

    return result

list_A: list[int] = fill_list(4, 19) 
list_B: list[int] = fill_list(55, -2)
list_C: list[int] = fill_list(1, 110)

Which function calls would be considered a use case of this function (list the associated variable name e.g. list_A)? Which would be considered edge cases? If there are any edge cases, what result would you get in the associated variable(s)?

  1. Write three unit tests for the following function, two testing use cases and one testing an edge case.
def divide_list(input_list: list[int], divisor: int) -> list[float]:
    """Returns a new list where each value is the value from input_list divided by divisor"""
    result: list[int] = []

    for num in input_list:
        result.append(num / divisor)

    return result

SOLUTIONS

  1. Question 1 Answers:

    1.1. assert

    1.2. test_

    1.3. _test.py

  2. This is False, as unit tests themselves can be incorrect so all tests passing is no guarantee of correctness even for the inputs the unit tests are testing for. Even if the unit tests are correct, there can still be certain inputs that they do not test for and therefore the unit tests cannot assure you that a function will always work properly. Unit tests are a helpful tool that can work well when implemented over a wide range of test inputs, but they must be accompanied by thoughtful implementation of the original function.

  3. list_A and list_C would be use cases since this is how we would expect this function to be used and list_B would be an edge case as this is essentially attempting to make a function call that would construct a list of negative length since our length argument is -2. In this edge case the result would be an empty list since we would never enter the while loop.

  4. Note: These are just some examples of what you could test for, but they will likely not be the same as what you wrote as there are many correct answers.

    The most straightforward use case test would be ensuring that on a normal input that the output is what you expect:

    def test_normal_divide_list() -> None:
    classes: list[int] = [110, 210, 301, 455]
    assert divide_list(classes, 10) == [11.0, 21.0, 30.1, 45.5]

    We could write another unit test to ensure that the original list was not mutated:

    def test_no_mutate_divide_list() -> None:
    classes: list[int] = [110, 210, 301, 455]
    divide_list(classes, 10) # We don't need to store the result
    assert classes == [110, 210, 301, 455]

    Finally, an example of an edge case for this function would be a divisor of zero, which we should expect to result in an error. We can test to ensure that an error occurs like this:

    def test_div_zero_error_divide_list() -> None:
    classes: list[int] = [110, 210, 301, 455]
    with pytest.raises(ZeroDivisionError):
        divide_list(classes, 0)

Object-Oriented Programming

Multiple Choice

  1. True or False: All instances of a class have the same attribute values.

    1. True

    2. False

  2. True or False: An object’s attribute values cannot be accessed from outside the class.

    1. True

    2. False

  3. What is the difference between a class and an object?

    1. A class is a collection of objects

    2. A class is a blueprint; an object is a specific instance of that blueprint

    3. They are the same in Python

    4. An object can contain classes, but not the other way around

  4. True or False: Because class definitions have attributes, local variables are not allowed inside method definitions.

    1. True

    2. False

  5. What does it mean to “instantiate” a class?

    1. Define the class

    2. Import a module

    3. Create an object from a class

    4. Define attributes

  6. True or False: The constructor of a class is only called once in a program, no matter how many objects of that class are constructed.

    1. True

    2. False

  7. The first parameter of any method is _____ and it is given a reference to the object the method was called on.

    1. me

    2. self

    3. init

    4. this

    5. current

  8. An instance of a class is stored in the:

    1. stack

    2. heap

    3. output

  9. True or False: Once attributes are initialized in the initializer/constructor, the values cannot be changed.

    1. True

    2. False

  10. True or False: A class definition introduces a new data type, or type of object, in your program.

    1. True

    2. False

SOLUTIONS

  1. False

  2. False

  3. A class is a blueprint; an object is a specific instance of that blueprint

  4. False

  5. Create an object from a class

  6. False

  7. self

  8. heap

  9. False

  10. True

Select All That Apply

Consider the following code listing. Select all lines on which any of the concepts below are found. Select if the concept is not in the code listing.

1 class Point:
2     x: float
3     y: float
4 
5     def __init__(self, x: float, y: float):
6         self.x = x
7         self.y = y
8 
9     def flip(self) -> None:
10        temp: float = self.x
11        self.x = self.y
12        self.y = temp
13
14    def shift_y(self, dy: float) -> None:
15        self.y += dy
16
17    def diff(self) -> float:
18        return self.x - self.y

  1. Constructor Declaration

    1. 1

    2. 2

    3. 5

    4. 9

    5. 11

  2. Attribute Declaration

    1. 2

    2. 3

    3. 6

    4. 7

    5. 10

  3. Attribute Initialization

    1. 2

    2. 3

    3. 6

    4. 7

    5. 10

  4. Method Declaration

    1. 1

    2. 9

    3. 10

    4. 14

    5. 17

  5. Local Variable Declaration

    1. 2

    2. 3

    3. 6

    4. 7

    5. 10

  6. Instantiation

    1. 1

    2. 5

    3. 9

    4. 10

    5. N/A

SOLUTIONS

  1. Line 5 only

  2. Lines 2 and 3

  3. Lines 6 and 7

  4. Lines 9, 14, and 17

  5. Line 10

  6. N/A

Short Answer

Use the following point class to answer the questions.

1 class Point:
2     x: float
3     y: float
4 
5     def __init__(self, x: float, y: float):
6         self.x = x
7         self.y = y
8 
9     def flip(self) -> None:
10        temp: float = self.x
11        self.x = self.y
12        self.y = temp
13
14    def shift_y(self, dy: float) -> None:
15        self.y += dy
16
17    def diff(self) -> float:
18        return self.x - self.y

  1. Write a line of code to create an explicitly typed instance of the Point class called my_point with an x of 3.7 and y of 2.3.

  2. Write a line of code to change the value of the my_point variable’s x attribute to 2.0.

  3. Write a line of code to cause the my_point variable’s y attribute to increase by 1.0 using a method call.

  4. Write a line of code to declare an explicitly typed variable named x. Initialize x to the result of calling the diff method on my_point.

SOLUTIONS

  1. my_point: Point = Point(x=3.7, y=2.3)

  2. my_point.x = 2.0

  3. my_point.shift_y(1.0)

  4. x: float = my_point.diff()

Memory Diagrams

  1. Complete a memory diagram for the following code listing.
1 class Dog:
2     name: str
3     age: int
4     
5     def __init__(self, n: str, a:int):
6         self.name = n
7         self.age = a
8         
9     def speak(self) -> None: 
10        print(self.name + " says woof!")
11        
12    def birthday(self) -> int:
13        self.age += 1 
14        return self.age
15        
16 class Cat:
17    name: str
18    age: int
19    
20    def __init__(self, n: str, a:int):
21        self.name = n
22        self.age = a
23        
24    def speak(self) -> None: 
25        print(self.name + " says meow!")
26        
27    def birthday(self) -> int:
28        self.age += 1 
29        return self.age
30    
31 rory: Dog = Dog(n = "Rory", a = 4)
32 print(rory.birthday())
33 miso: Cat = Cat("Miso", 2)
34 miso.speak()
  1. Complete a memory diagram for the following code listing.
1  class Concert:
2      artist: str
3      seats: dict[str, bool]
4  
5      def __init__(self, a: str, s: dict[str, bool]):
6          self.artist = a
7          self.seats = s
8  
9      def assign_seats(self, wanted_seats: list[str], name: str) -> None:
10         for seat in wanted_seats:
11             if seat in self.seats:
12                 available: bool = self.seats[seat]
13                 if available:
14                     print(f"{name} bought seat {seat} to see {self.artist}!")
15                     self.seats[seat] = False
16                 else: 
17                    print(f"Seat {seat} is unavailable :(")
18 
19 lenovo_seats: dict[str, bool] = {"K1": True, "K2": True, "K3": False}
20 show: Concert = Concert(a = "Travisty", s = lenovo_seats)
21 show.assign_seats(wanted_seats = ["K2", "K3"], name = "Kay")

SOLUTIONS

  1. Dog and Cat memory diagram solution (see the solution video here!).

Memory diagram of code listing with Dog and Cat classes.

  1. Concert memory diagram solution (see the solution video here!).

Memory diagram of code listing with Concert classes.

Contributor(s): Alyssa Lytle, Benjamin Eldridge, Izzi Hinks