Skip to main content

Problem Set 2: Data Structures

Homework for Module 2

Introduction

Use these exercises to practise the concepts from this module. I recommend deactivating Gemini first, along with any other AI helper, and attempting the exercises on your own.

Mandatory exercises are highlighted in red boxes. These are the exercises you must complete to receive your participation points. You may use AI help, but remember that you may be asked to explain your code in class.

The remaining exercises are optional. Try each one before opening its collapsed solution.

When an exercise asks you to predict an output or error, explain your reasoning before checking the answer. For programming exercises, test your solution with additional inputs.

Lists

NotePrepending Values

After running the code, what will ls_numbers contain?

ls_numbers = []

for number in [1, 2, 3]:
    ls_numbers = [number] + ls_numbers

print(ls_numbers)
[3, 2, 1]

Each new number is added to the beginning of the list.

NoteCharacters from a String

After running the code, what will ls_characters contain?

ls_characters = []

for character in "one, two, three":
    ls_characters.append(character)

print(ls_characters)
['o', 'n', 'e', ',', ' ', 't', 'w', 'o', ',', ' ', 't', 'h', 'r', 'e', 'e']

A loop over a string visits one character at a time, including commas and spaces.

NoteSkipping a Value

After running the code, what will ls_numbers contain?

ls_numbers = []

for number in range(2, 11, 2):
    if number == 6:
        continue
    ls_numbers.append(number)

print(ls_numbers)
[2, 4, 8, 10]

The continue statement skips the append operation when number is 6.

NoteClearing Inside a Loop

After running the code, what will ls_numbers contain?

ls_numbers = []

for number in range(10):
    ls_numbers.clear()
    ls_numbers.append(number)

print(ls_numbers)
[9]

Every iteration clears the previous value. Only the value added during the final iteration remains.

NoteIndexing Twice

What will the code print?

boardgames = ["Monopoly", "Catan", "UNO"]

print(boardgames[1][0])
C

boardgames[1] is "Catan". Index 0 of that string is "C".

NoteSorting Before Inserting

What will names contain?

names = ["Lucy", "Jack", "Alberto"]

names.sort()
names.insert(2, "Ben")

print(names)
['Alberto', 'Jack', 'Ben', 'Lucy']

The original names are sorted first. "Ben" is then inserted at index 2, so the final list is not fully alphabetical.

NoteInserting Before Sorting

What will names contain?

names = ["Lucy", "Jack", "Alberto"]

names.insert(2, "Ben")
names.sort()

print(names)
['Alberto', 'Ben', 'Jack', 'Lucy']

The final sort() call orders all four names.

NoteThe Return Value of append()

What will the code print?

numbers = [0, 1, 2, 3]
numbers = numbers.append(4)

print(numbers)
None

append() changes the list in place and returns None. The assignment then stores None in numbers.

NoteChaining sort()

What happens when this code runs?

names = ["Lucy", "Jack", "Alberto"]
names.insert(2, "Ben")

first_name = names.sort()[0]

print(first_name)

Python raises a TypeError because sort() returns None. The expression tries to access index 0 of None.

names.sort()
first_name = names[0]

print(first_name)
NoteFilter Even Numbers

Write a function named filter_even(numbers) that returns a new list containing only the even numbers.

Sample input: filter_even([1, 2, 3, 4, 5, 6])
Expected result: [2, 4, 6]

def filter_even(numbers: list[int]) -> list[int]:
    """
    Return a new list with only the even numbers.

    Parameters
    ----------
    numbers : list[int]
        The integers to filter.

    Returns
    -------
    list[int]
        The even numbers, in their original order.
    """
    even_numbers = []
    for number in numbers:
        if number % 2 == 0:
            even_numbers.append(number)
    return even_numbers

print(filter_even([1, 2, 3, 4, 5, 6]))
NoteList Reversal

Write a function named my_reverse(values) that returns the elements of a list in reverse order without using the reverse() method.

Sample input: my_reverse([1, 2, 3, 4, 5])
Expected result: [5, 4, 3, 2, 1]

def my_reverse(values: list) -> list:
    """
    Return a new list with the elements in reverse order.

    Parameters
    ----------
    values : list
        The list to reverse. It is not modified.

    Returns
    -------
    list
        A new list with the same elements, from last to first.
    """
    return values[::-1]

print(my_reverse([1, 2, 3, 4, 5]))
NoteAverage, Variance, and Standard Deviation

Write a function named statistics(numbers) that returns the average, population variance, and standard deviation of a list as [average, variance, standard_deviation].

Sample input 1: statistics([1, 1])
Expected result 1: [1.0, 0.0, 0.0]

Sample input 2: statistics([4, 9, 16, 25, 36])
Expected result 2: [18.0, 130.8, 11.4368]

def statistics(numbers: list[float]) -> list[float]:
    """
    Return the average, population variance and standard deviation.

    Parameters
    ----------
    numbers : list[float]
        A non-empty list of numbers.

    Returns
    -------
    list[float]
        The values ``[average, variance, standard_deviation]``,
        each rounded to 4 decimal places.
    """
    average = sum(numbers) / len(numbers)

    squared_differences = []
    for number in numbers:
        squared_differences.append((number - average) ** 2)

    variance = sum(squared_differences) / len(numbers)
    standard_deviation = variance ** 0.5

    return [
        round(average, 4),
        round(variance, 4),
        round(standard_deviation, 4),
    ]

print(statistics([4, 9, 16, 25, 36]))
NoteElement-by-Element Multiplication

Write a function named vecmul(first, second) that multiplies two lists element by element. If the lists have different lengths, return "Lists are not the same size".

Sample input 1: vecmul([1, 2], [1, 2, 3])
Expected result 1: "Lists are not the same size"

Sample input 2: vecmul([1, 2, 3], [4, 5, 6])
Expected result 2: [4, 10, 18]

def vecmul(
    first: list[float], second: list[float]
) -> list[float] | str:
    """
    Multiply two lists element by element.

    Parameters
    ----------
    first : list[float]
        The first list of numbers.
    second : list[float]
        The second list of numbers.

    Returns
    -------
    list[float] | str
        The element-wise products, or the message
        ``"Lists are not the same size"`` if the lengths differ.
    """
    if len(first) != len(second):
        return "Lists are not the same size"

    products = []
    for index in range(len(first)):
        products.append(first[index] * second[index])
    return products

print(vecmul([1, 2, 3], [4, 5, 6]))
NoteList Intersection

Write a function named intersection(first, second) that returns a new list containing the elements found in both input lists.

Sample input 1: intersection([1, 2, 3, 4, 5], [3, 4, 5, 6, 7])
Expected result 1: [3, 4, 5]

Sample input 2: intersection([1, 2, 3], [4, 5, 6])
Expected result 2: []

def intersection(first: list, second: list) -> list:
    """
    Return the elements found in both lists, without repetitions.

    Parameters
    ----------
    first : list
        The first list.
    second : list
        The second list.

    Returns
    -------
    list
        The common elements, in the order they appear in ``first``.
    """
    common = []
    for value in first:
        if value in second and value not in common:
            common.append(value)
    return common

print(intersection([1, 2, 3, 4, 5], [3, 4, 5, 6, 7]))
WarningFunction as a List Transformer

Write a function named transform_list(numbers, transformation) that receives a list of numbers and a function. Apply the function to each number and return the transformed list.

Sample input: transform_list([1, 2, 3, 4, 5], lambda x: x**2)
Expected result: [1, 4, 9, 16, 25]

NoteThree Consecutive Equal Numbers

Write a function named has_three_equal(numbers) that checks whether a list contains the same number in three consecutive positions.

Sample input 1: has_three_equal([1, 2, 2, 2, 6])
Expected result 1: True

Sample input 2: has_three_equal([1, 3, 4, 6])
Expected result 2: False

def has_three_equal(numbers: list[int]) -> bool:
    """
    Check whether a list has the same number in three consecutive positions.

    Parameters
    ----------
    numbers : list[int]
        The numbers to check.

    Returns
    -------
    bool
        True if three consecutive elements are equal, False otherwise.
    """
    for index in range(len(numbers) - 2):
        if numbers[index] == numbers[index + 1] == numbers[index + 2]:
            return True
    return False

print(has_three_equal([1, 2, 2, 2, 6]))
NoteStrongest Neighbours

Write a function named strongest_neighbours(numbers) that returns the maximum value from every pair of adjacent numbers.

Sample input 1: strongest_neighbours([1, 2, 3, 4, 5])
Expected result 1: [2, 3, 4, 5]

Sample input 2: strongest_neighbours([3, 1, 3, 5, 2])
Expected result 2: [3, 3, 5, 5]

def strongest_neighbours(numbers: list[int]) -> list[int]:
    """
    Return the maximum of every pair of adjacent numbers.

    Parameters
    ----------
    numbers : list[int]
        The numbers to compare.

    Returns
    -------
    list[int]
        One maximum per adjacent pair, so it has one element fewer
        than ``numbers``.
    """
    result = []
    for index in range(len(numbers) - 1):
        result.append(max(numbers[index], numbers[index + 1]))
    return result

print(strongest_neighbours([3, 1, 3, 5, 2]))
NoteSort by Number of Divisors

Write a function named sort_by_divisors(numbers) that sorts positive integers from the greatest number of divisors to the least. Keep their original order when two numbers have the same number of divisors.

Sample input: sort_by_divisors([10, 6, 8, 7])
Expected result: [10, 6, 8, 7]

def count_divisors(number: int) -> int:
    """
    Count the positive divisors of a positive integer.

    Parameters
    ----------
    number : int
        A positive integer.

    Returns
    -------
    int
        How many integers from 1 to ``number`` divide it exactly.
    """
    count = 0
    for divisor in range(1, number + 1):
        if number % divisor == 0:
            count += 1
    return count

def sort_by_divisors(numbers: list[int]) -> list[int]:
    """
    Sort numbers from the most divisors to the fewest.

    Numbers with the same number of divisors keep their original order.

    Parameters
    ----------
    numbers : list[int]
        The positive integers to sort.

    Returns
    -------
    list[int]
        A new sorted list.
    """
    return sorted(numbers, key=count_divisors, reverse=True)

print(sort_by_divisors([10, 6, 8, 7]))
WarningSort Bus Lines by Mean Time

Given a list containing bus-line names and route times:

  1. Calculate the average route time.
  2. Sort the lines by their distance from the average.
  3. If two lines are equally distant from the average, place the faster line first.

Sample input: [["Line 1", 50], ["Line 2", 30], ["Line 3", 40]]
Expected result: [["Line 3", 40], ["Line 2", 30], ["Line 1", 50]]

NoteSort Square Roots

Write a function named sort_square_roots(groups) that:

  1. Creates a new list containing the square roots of the non-negative values in each sublist.
  2. Sorts the sublists from the greatest number of roots to the least.
  3. When two sublists contain the same number of roots, places the one with the largest root first.

Sample input: [[4, 1, -3, 9], [16, -9], [1, 25, 36]]
Expected result: [[1.0, 5.0, 6.0], [2.0, 1.0, 3.0], [4.0]]

def sort_square_roots(groups: list[list[float]]) -> list[list[float]]:
    """
    Take the square roots of each sublist and sort the results.

    Negative values are skipped. Sublists with more roots come first; ties
    are broken by the largest root.

    Parameters
    ----------
    groups : list[list[float]]
        The sublists of numbers.

    Returns
    -------
    list[list[float]]
        The lists of square roots, sorted.
    """
    roots = []

    for group in groups:
        group_roots = []
        for number in group:
            if number >= 0:
                group_roots.append(number ** 0.5)
        roots.append(group_roots)

    roots.sort(
        key=lambda group: (len(group), max(group, default=float("-inf"))),
        reverse=True,
    )
    return roots

print(sort_square_roots([[4, 1, -3, 9], [16, -9], [1, 25, 36]]))
NoteClassify Words by Syllables

Write a function named classify_words(sentence) that places words into three lists: monosyllabic, bisyllabic, and polysyllabic. For this exercise, treat each group of consecutive vowels as one syllable.

Sample input: "She enjoys colorful paintings."
Expected result: mono = ["She"], bi = ["enjoys", "paintings"], poly = ["colorful"]

def count_syllables(word: str) -> int:
    """
    Count the syllables in a word as groups of consecutive vowels.

    Parameters
    ----------
    word : str
        The word to analyse.

    Returns
    -------
    int
        The number of vowel groups in ``word``.
    """
    vowels = "aeiouAEIOU"
    count = 0
    previous_was_vowel = False

    for character in word:
        is_vowel = character in vowels
        if is_vowel and not previous_was_vowel:
            count += 1
        previous_was_vowel = is_vowel

    return count

def classify_words(sentence: str) -> tuple[list[str], list[str], list[str]]:
    """
    Split the words of a sentence by their number of syllables.

    Parameters
    ----------
    sentence : str
        The sentence to classify. Punctuation at the ends of each word is
        removed.

    Returns
    -------
    tuple[list[str], list[str], list[str]]
        The monosyllabic, bisyllabic and polysyllabic words, in that order.
    """
    mono = []
    bi = []
    poly = []

    for word in sentence.split():
        clean_word = word.strip(".,!?;:")
        syllables = count_syllables(clean_word)

        if syllables == 1:
            mono.append(clean_word)
        elif syllables == 2:
            bi.append(clean_word)
        elif syllables >= 3:
            poly.append(clean_word)

    return mono, bi, poly

print(classify_words("She enjoys colorful paintings."))

Tuples

NoteSlice Then Index

What will the code print?

videogames = ("Pokemon", "Candy Crush", "FIFA", "Outer Wilds")

print(videogames[1:3][1])
FIFA

The slice videogames[1:3] produces ("Candy Crush", "FIFA"). Index 1 of that tuple is "FIFA".

NoteInvalid Nested Index

What happens when this code runs? How would you correct it if the goal were to extract characters 1 through 3 from "Superman"?

superheroes = ("Batman", "Ironman", "Superman")

print(superheroes[2[1:4]])

The code raises a TypeError because it tries to slice the integer 2.

print(superheroes[2][1:4])

The corrected code prints upe.

NoteRepair the Tuple Code

The following code contains three errors. Identify and correct all of them.

colors = ("Blue",)
colors = ("Green",) + colors
colors += ("Red,")
colors.append("Yellow")

print(aliens)

("Red,") is a string rather than a one-item tuple, tuples do not have append(), and aliens is undefined.

colors = ("Blue",)
colors = ("Green",) + colors
colors += ("Red",)
colors += ("Yellow",)

print(colors)
NoteDisplaying a Tuple

What will the code print?

numbers = (4, 2, 3)

print(numbers)
(4, 2, 3)
NoteChanging a Tuple

What happens when this code runs?

numbers = (4, 2, 3)
numbers[0] = 0

print(numbers[0])

Python raises a TypeError because tuples are immutable. Their items cannot be replaced.

NoteRepeating a Tuple

What will the code print?

numbers = (4, 2, 3)

print(2 * numbers)
(4, 2, 3, 4, 2, 3)
NoteList to Tuple

What will the code print?

names_list = ["Raul", "Ana", "Oscar"]
names_tuple = tuple(names_list)

print(names_tuple[2])
Oscar
NoteConcatenating Tuples

What will the code print?

numbers = (5, 2)
names = ("Raul", "Ana", "Oscar")

print(numbers + names)
(5, 2, 'Raul', 'Ana', 'Oscar')

Tuples can contain mixed data types.

NoteCombining a List and a Tuple

What happens when this code runs?

names_list = ["Raul", "Ana", "Oscar"]
names_tuple = ("Raul", "Ana", "Oscar")

print(names_list + names_tuple)

Python raises a TypeError. The + operator cannot directly concatenate a list and a tuple.

print(names_list + list(names_tuple))
NoteTuple Unpacking

Write a function named sentence(person) that receives a tuple containing (name, age, gender). Unpack the tuple and return a sentence in the format "Name is X years old and is a Y."

Sample input: sentence(("Alice", 30, "female"))
Expected result: "Alice is 30 years old and is a female."

def sentence(person: tuple[str, int, str]) -> str:
    """
    Build a sentence describing a person.

    Parameters
    ----------
    person : tuple[str, int, str]
        The person's name, age and gender.

    Returns
    -------
    str
        A sentence such as ``"Alice is 30 years old and is a female."``.
    """
    name, age, gender = person
    return f"{name} is {age} years old and is a {gender}."

print(sentence(("Alice", 30, "female")))
NoteImmutable Tuple

Write a function named replace_zeros(values) that replaces every zero in a list with 1.

Sample input 1: replace_zeros([1, 0, 3, 0, 4])
Expected result 1: [1, 1, 3, 1, 4]

What happens when you pass the tuple (1, 0, 3, 0, 4) to the same function? Explain why.

def replace_zeros(values: list[int]) -> list[int]:
    """
    Replace every zero with 1, modifying the list in place.

    Parameters
    ----------
    values : list[int]
        The numbers to update. This list is changed.

    Returns
    -------
    list[int]
        The same list, after the replacement.
    """
    for index in range(len(values)):
        if values[index] == 0:
            values[index] = 1
    return values

print(replace_zeros([1, 0, 3, 0, 4]))

The function works with a list because lists are mutable. Passing a tuple raises a TypeError when the function attempts item assignment because tuples are immutable.

WarningSort Tuples by Age

Write a function named sort_age(people) that receives a list of (name, age) tuples and returns them sorted by age in ascending order.

Sample input: sort_age([("Alice", 25), ("Bob", 30), ("Charlie", 20)])
Expected result: [("Charlie", 20), ("Alice", 25), ("Bob", 30)]

NoteErasmus Board

Write a function named erasmus_board(entries) that receives a list of (student, destination, status) tuples.

  1. Sort the entries alphabetically by student name, then by destination.
  2. Include only entries whose status is True.
  3. Return a numbered board as a single string.

Sample input: [("Alice", "Paris", True), ("Charlie", "Berlin", False)]
Expected result: "1. Alice: Paris"

def erasmus_board(entries: list[tuple[str, str, bool]]) -> str:
    """
    Build a numbered board with the confirmed Erasmus destinations.

    Parameters
    ----------
    entries : list[tuple[str, str, bool]]
        Tuples of ``(student, destination, status)``. Only entries whose
        status is True are included.

    Returns
    -------
    str
        One line per confirmed entry, sorted by student and destination.
    """
    sorted_entries = sorted(entries, key=lambda entry: (entry[0], entry[1]))
    lines = []

    for student, destination, status in sorted_entries:
        if status:
            lines.append(f"{len(lines) + 1}. {student}: {destination}")

    return "\n".join(lines)

entries = [
    ("Alice", "Paris", True),
    ("Charlie", "Berlin", False),
]

print(erasmus_board(entries))

Sets

NoteCombining Collections into a Set

What values will names contain after the code runs?

names_list = ["Alberto", "Carol"]
names_tuple = ("Alberto", "Lucia", "Ramon")
names = set(names_list + list(names_tuple))

print(names)

The set contains "Alberto", "Carol", "Lucia", and "Ramon". The displayed order may vary, and the duplicate "Alberto" appears only once.

NoteLength of a Union

What will the code print?

comedy = {"Airplane!", "Shrek"}
fantasy = {"Harry Potter", "Shrek", "The Lord of the Rings"}
movies = comedy | fantasy

print(len(movies))
4

"Shrek" belongs to both sets but appears only once in the union.

NoteBoolean and with Sets

What will the code print? Does and calculate a set intersection?

comedy = {"Airplane!", "Shrek"}
fantasy = {"Harry Potter", "Shrek", "The Lord of the Rings"}
movies = comedy and fantasy

print(len(movies))

The code prints 3. Both sets are non-empty, so the Boolean operator and returns the second set, fantasy.

Use & for intersection:

movies = comedy & fantasy

print(len(movies))

The corrected code prints 1.

NoteComparing Lengths

Which two structures have the same length?

message = "A B C"
even_numbers = [2, 2, 4, 6]
pairs = ((1, 3), (3, 5), (5, 7))
squares = {4, 4, 9, 16}

pairs and squares both have length 3.

  • message has length 5, including the spaces.
  • even_numbers has length 4, including the duplicate value.
  • squares removes the duplicate 4.
NoteWhich Block Runs?

Only one block runs without an error. Which one?

# Option A
numbers = [1, 2, 3]
numbers[0] = "0"
# Option B
numbers = [1, 2, 3]
numbers = numbers + 4
# Option C
numbers = tuple([1, 2, 3])
numbers[0] = 0
# Option D
numbers = set([1, 2, 3])
numbers[0] = 2

Option A runs. Lists are mutable and may contain mixed data types.

Option B tries to concatenate a list and an integer. Option C tries to modify a tuple. Option D tries to index a set.

NoteA Plan Everyone Likes

Write a function named find_common_plans() that receives three lists and returns the plans present in all three.

laura = ["beach", "cinema", "mountain", "museum", "shopping"]
jose = ["gym", "mountain", "park", "soccer", "shopping"]
ana = ["beach", "cinema", "mountain", "park", "party"]
def find_common_plans(
    list_1: list[str], list_2: list[str], list_3: list[str]
) -> set[str]:
    """
    Return the plans that appear in all three lists.

    Parameters
    ----------
    list_1 : list[str]
        The first person's plans.
    list_2 : list[str]
        The second person's plans.
    list_3 : list[str]
        The third person's plans.

    Returns
    -------
    set[str]
        The plans liked by all three people.
    """
    set_1 = set(list_1)
    set_2 = set(list_2)
    set_3 = set(list_3)
    return set_1 & set_2 & set_3
print(find_common_plans(laura, jose, ana))

The result is {"mountain"}.

NoteExclusive Plans

Write a function named find_exclusive_plans() that receives three lists and returns a tuple containing the plans liked exclusively by each person.

Use the laura, jose, and ana lists from the previous exercise.

Expected structure:

(laura_only, jose_only, ana_only)
def find_exclusive_plans(
    list_1: list[str], list_2: list[str], list_3: list[str]
) -> tuple[set[str], set[str], set[str]]:
    """
    Return the plans liked by only one of three people.

    Parameters
    ----------
    list_1 : list[str]
        The first person's plans.
    list_2 : list[str]
        The second person's plans.
    list_3 : list[str]
        The third person's plans.

    Returns
    -------
    tuple[set[str], set[str], set[str]]
        The plans exclusive to the first, second and third person.
    """
    set_1 = set(list_1)
    set_2 = set(list_2)
    set_3 = set(list_3)

    only_1 = set_1 - set_2 - set_3
    only_2 = set_2 - set_1 - set_3
    only_3 = set_3 - set_1 - set_2

    return only_1, only_2, only_3
print(find_exclusive_plans(laura, jose, ana))
NoteDisplaying a Set

Can you predict the exact order of the output?

names = {"Raul", "Ana", "Oscar"}

print(names)

You can predict the contents but not the exact displayed order. The set contains "Raul", "Ana", and "Oscar".

NoteIndexing a Set

What happens when the code runs?

names_list = ["Raul", "Ana", "Oscar"]
names = set(names_list)

print(names[0])

Python raises a TypeError because sets do not support indexing.

NoteCase-Sensitive Intersection

What does the first cell print? Then modify the code so matching words are found regardless of capitalization.

animals_upper = {"DOG", "CAT", "MOUSE"}
animals_lower = {"dog", "cat", "mouse"}

print(animals_upper & animals_lower)

The original code prints an empty set because string comparison is case-sensitive.

normalized_upper = {animal.lower() for animal in animals_upper}
common_animals = normalized_upper & animals_lower

print(common_animals)

The corrected result contains "dog", "cat", and "mouse".

NoteEquivalent Numeric Values

What values will the union contain?

set_1 = {1, 2, 3}
set_2 = {1.0, 2.5, 3.0}

print(set_1 | set_2)

The union contains 1, 2, 2.5, and 3. Python treats 1 and 1.0 as equal, and it also treats 3 and 3.0 as equal.

NoteNumbers and Numeric Strings

What will the code print?

numbers = {1, 2, 3}
numeric_strings = {"1", "2", "3"}

print(numbers - numeric_strings)

The result is {1, 2, 3}. An integer such as 1 is different from the string "1".

NoteDuplicates and Union

What values will the union contain?

set_1 = {1, 1, 2, 2, 3, 3}
set_2 = set([5, 4])

print(set_1 | set_2)

The union contains 1, 2, 3, 4, and 5. The displayed order may vary.

NoteSet Union Function

Write a function named union(first, second) that returns the union of two sets.

Sample input: union({1, 2, 3, 4}, {3, 4, 5, 6})
Expected result: {1, 2, 3, 4, 5, 6}

def union(first: set, second: set) -> set:
    """
    Return the union of two sets.

    Parameters
    ----------
    first : set
        The first set.
    second : set
        The second set.

    Returns
    -------
    set
        The elements that are in either set.
    """
    return first | second

print(union({1, 2, 3, 4}, {3, 4, 5, 6}))
NoteSet Intersection Function

Write a function named intersection(first, second) that returns the intersection of two sets.

Sample input: intersection({1, 2, 3, 4}, {3, 4, 5, 6})
Expected result: {3, 4}

def intersection(first: set, second: set) -> set:
    """
    Return the intersection of two sets.

    Parameters
    ----------
    first : set
        The first set.
    second : set
        The second set.

    Returns
    -------
    set
        The elements that are in both sets.
    """
    return first & second

print(intersection({1, 2, 3, 4}, {3, 4, 5, 6}))
NoteSet Difference Function

Write a function named difference(first, second) that returns the elements in first that are not in second.

Sample input 1: difference({1, 2, 3, 4}, {3, 4, 5, 6})
Expected result 1: {1, 2}

Sample input 2: difference({3, 4, 5, 6}, {1, 2, 3, 4})
Expected result 2: {5, 6}

def difference(first: set, second: set) -> set:
    """
    Return the elements of the first set that are not in the second.

    Parameters
    ----------
    first : set
        The set to take elements from.
    second : set
        The set of elements to remove.

    Returns
    -------
    set
        The elements in ``first`` but not in ``second``.
    """
    return first - second

print(difference({1, 2, 3, 4}, {3, 4, 5, 6}))
NoteCommon Letters and Counts

Write a function named common_letters(first, second) that returns tuples containing each common letter, its count in the first string, and its count in the second string.

Sort the tuples by the total number of occurrences, from greatest to least. Break ties alphabetically.

Sample input: common_letters("apple", "peach")
Expected result: [("p", 2, 1), ("a", 1, 1), ("e", 1, 1)]

def common_letters(
    first: str, second: str
) -> list[tuple[str, int, int]]:
    """
    Count the letters that two strings have in common.

    Parameters
    ----------
    first : str
        The first string.
    second : str
        The second string.

    Returns
    -------
    list[tuple[str, int, int]]
        Tuples of ``(letter, count_in_first, count_in_second)``, sorted by
        total count from greatest to least, then alphabetically.
    """
    common = set(first) & set(second)
    result = []

    for letter in common:
        result.append((letter, first.count(letter), second.count(letter)))

    result.sort(key=lambda item: (-(item[1] + item[2]), item[0]))
    return result

print(common_letters("apple", "peach"))
WarningClass Sets

Write a function named list_students(math, biology) that receives the student lists for two classes and returns:

  1. All students enrolled in either class.
  2. Students enrolled in both classes.
  3. Students enrolled only in Mathematics.
  4. Students enrolled only in Biology.

Sample input: math = ["John", "Luca", "Greta"], biology = ["John", "Mary"]

Expected results:
Total: ["John", "Luca", "Greta", "Mary"]
Common: ["John"]
Math only: ["Luca", "Greta"]
Biology only: ["Mary"]

WarningSecond Largest Distinct Number

Write a function that returns the second largest distinct number in a list.

Sample input: [1, 1, 1, 2, 3, 4, 4, 5, 5]
Expected result: 4

WarningFind Pairs with a Target Sum

Write a function that finds all distinct pairs of values in a list whose sum equals a given target. Return the pairs as a set of tuples, with the smaller number first in each tuple.

Sample input: numbers = [1, 2, 3, 4, 5], target = 6
Expected result: {(1, 5), (2, 4)}

NoteMaximum Product Pair

Write a function named maximum_product_pair(numbers) that uses the distinct values in a list and returns the pair whose product is greatest.

Sample input: maximum_product_pair([1, 7, 3, 9, 5])
Expected result: (7, 9)

def maximum_product_pair(numbers: list[int]) -> tuple[int, int] | None:
    """
    Return the pair of distinct values with the greatest product.

    Parameters
    ----------
    numbers : list[int]
        The numbers to search. Repeated values are counted once.

    Returns
    -------
    tuple[int, int] | None
        The pair, smaller number first, or None if there are fewer than
        two distinct values.
    """
    unique_numbers = list(set(numbers))

    if len(unique_numbers) < 2:
        return None

    best_pair = None
    best_product = None

    for first_index in range(len(unique_numbers)):
        for second_index in range(first_index + 1, len(unique_numbers)):
            first = unique_numbers[first_index]
            second = unique_numbers[second_index]
            product = first * second

            if best_product is None or product > best_product:
                best_product = product
                best_pair = tuple(sorted((first, second)))

    return best_pair

print(maximum_product_pair([1, 7, 3, 9, 5]))

Dictionaries

NoteKeys Created from Variables

What are the keys of fruits?

name = "orange"

fruits = {
    name: 7,
    "pear": 8,
    "apple": 9,
}

print(fruits.keys())

The keys are "orange", "pear", and "apple". Python evaluates the variable name when creating the dictionary.

NoteDuplicate Keys

What will the code print?

name = "orange"

fruits = {
    name: 7,
    "pear": 8,
    "apple": 9,
    "orange": 10,
}

print(fruits[name])
10

Both name and "orange" create the same key. The last value assigned to that key remains.

NoteLength with a Repeated Key

What is the length of fruits?

name = "orange"

fruits = {
    name: 7,
    "pear": 8,
    "apple": 9,
    "orange": 7,
}

print(len(fruits))

The length is 3. Dictionary keys must be unique.

NoteDuplicate Values

What is the length of fruits?

fruits = {
    "pear": 8,
    "apple": 8,
    "orange": 8,
}

print(len(fruits))

The length is 3. Values may be duplicated because the three keys are different.

NoteLength of a Nested Dictionary

What is the length of foods?

fruits = {
    "pear": 8,
    "apple": 8,
    "orange": 8,
}

foods = {
    "fruits": fruits,
    "vegetables": ["carrot", "broccoli"],
}

print(len(foods))

The length is 2. len() counts only the keys in the outer dictionary.

NoteReassigning a Dictionary

What is the final length of fruits?

fruits = {
    "pear": 8,
    "apple": 8,
    "orange": 8,
}

fruits = {
    "fruits": fruits,
}

print(len(fruits))

The final length is 1. The new outer dictionary has one key, "fruits", whose value is the original dictionary.

NoteBuilding a Score Dictionary

What will scores contain after the loop?

students = ["A", "B", "C"]
student_scores = [9, 10, 8.5]
scores = {}

for index in range(len(students)):
    scores[students[index]] = student_scores[index]

print(scores)
{'A': 9, 'B': 10, 'C': 8.5}

The values at matching list positions are paired together.

NoteCounting Crop Types

What will the code print?

number_of_parsnips = 20

crops = {
    "parsnip": number_of_parsnips,
    "potato": 5,
    "cauliflower": 10,
    "kale": 5,
}

print(len(crops))

The code prints 4, one for each key.

NoteAdding a Key

What will the final length of person be?

person = {
    "name": "Trisha",
    "children": ["Edward", "Alphonse"],
    "age": 26,
}

person["gender"] = "female"

print(len(person))

The final length is 4. Assigning a value to the new key "gender" adds a key-value pair.

NoteUpdating and Deleting Keys

What is the value associated with "area" after the code runs?

farm = {
    "length": 10,
    "width": 5,
    "missing": "area",
}

farm["area"] = farm["length"] * farm["width"]
del farm["missing"]

print(farm["area"])

The value is 50. Deleting "missing" does not affect the calculated area.

NoteAccessing a Nested Value

What will the code print?

animal_sounds = {
    "mammal": {
        "dog": "woof",
        "cat": "meow",
    },
    "fish": {
        "tuna": "blub",
        "salmon": "blub blub",
    },
}

print(animal_sounds["mammal"]["dog"])
woof
NoteMissing Outer Key

What happens when the code runs?

animal_sounds = {
    "mammal": {
        "dog": "woof",
        "cat": "meow",
    },
    "fish": {
        "tuna": "blub",
        "salmon": "blub blub",
    },
}

print(animal_sounds["tuna"])

Python raises a KeyError. The outer dictionary has only the keys "mammal" and "fish".

The nested value is available through:

print(animal_sounds["fish"]["tuna"])
NoteKey or Value?

What happens when the code runs?

animal_sounds = {
    "mammal": {
        "dog": "woof",
        "cat": "meow",
    },
    "fish": {
        "tuna": "blub",
        "salmon": "blub blub",
    },
}

print(animal_sounds["fish"]["blub"])

Python raises a KeyError. "blub" is a value, not a key. The valid nested key is "tuna".

NoteA List of Dictionaries

What will the code print?

people = [
    {"name": "Manuel", "country": "Spain"},
    {"name": "Louis", "country": "Canada"},
]

print(people[-1])
{'name': 'Louis', 'country': 'Canada'}

Index -1 selects the final dictionary in the list.

NoteIncorrect List Index

What happens when the code runs? Correct it so that it prints Manuel’s country.

people = [
    {"name": "Manuel", "country": "Spain"},
    {"name": "Louis", "country": "Canada"},
]

print(people["Manuel"]["country"])

Python raises a TypeError because list indices must be integers or slices.

print(people[0]["country"])

The corrected code prints Spain.

NoteLooping Through Dictionary Values

Write the four lines produced by the code.

people = [
    {"name": "Manuel", "country": "Spain"},
    {"name": "Louis", "country": "Canada"},
]

for person in people:
    for value in person.values():
        print(value)
Manuel
Spain
Louis
Canada

Dictionaries preserve insertion order, so each "name" value appears before its "country" value.

NotePrint a Dictionary Line by Line

Write a function named print_dictionary(dictionary) that prints every key-value pair on a separate line.

Sample input: {"Spain": "Madrid", "Portugal": "Lisbon"}

Expected output:

Key is Spain, value is Madrid
Key is Portugal, value is Lisbon
def print_dictionary(dictionary: dict) -> None:
    """
    Print every key-value pair of a dictionary on its own line.

    Parameters
    ----------
    dictionary : dict
        The dictionary to print.
    """
    for key, value in dictionary.items():
        print(f"Key is {key}, value is {value}")

capitals = {
    "Spain": "Madrid",
    "Portugal": "Lisbon",
}

print_dictionary(capitals)
NoteSum Collection Values

Write a function named sum_collection_values(dictionary) that replaces each dictionary value with its sum when that value is a list, tuple, or set of numbers. Leave other values unchanged.

Sample input:

gradebook = {
    "Alice": [90, 85, 88],
    "Bob": {78, 92, 87},
    "Charlie": "Not graded",
}

Expected result:

{
    "Alice": 263,
    "Bob": 257,
    "Charlie": "Not graded",
}
def sum_collection_values(
    dictionary: dict[str, object]
) -> dict[str, object]:
    """
    Replace list, tuple and set values with their sum, in place.

    Other values are left unchanged.

    Parameters
    ----------
    dictionary : dict[str, object]
        The dictionary to update. This dictionary is changed.

    Returns
    -------
    dict[str, object]
        The same dictionary, after the replacement.
    """
    for key, value in dictionary.items():
        if isinstance(value, (list, tuple, set)):
            dictionary[key] = sum(value)
    return dictionary

gradebook = {
    "Alice": [90, 85, 88],
    "Bob": {78, 92, 87},
    "Charlie": "Not graded",
}

print(sum_collection_values(gradebook))
NoteCompetition Points

Write a function named score_range(scores) that receives a dictionary of players and scores, then reports the maximum and minimum score.

Sample input: score_range({"Homer": 10, "Marge": 25, "Bart": 5})
Expected result: "Max = 25, Min = 5"

def score_range(scores: dict[str, int]) -> str:
    """
    Report the maximum and minimum score.

    Parameters
    ----------
    scores : dict[str, int]
        Each player's score.

    Returns
    -------
    str
        A message such as ``"Max = 25, Min = 5"``.
    """
    maximum = max(scores.values())
    minimum = min(scores.values())
    return f"Max = {maximum}, Min = {minimum}"

print(score_range({"Homer": 10, "Marge": 25, "Bart": 5}))
NoteUnique Dictionary Values

Write a function named unique_values(dictionary) that returns a set containing the distinct values in a dictionary.

Sample input: unique_values({"a": 1, "b": 2, "c": 1, "d": 3})
Expected result: {1, 2, 3}

def unique_values(dictionary: dict) -> set:
    """
    Return the distinct values of a dictionary.

    Parameters
    ----------
    dictionary : dict
        The dictionary to inspect. Its values must be hashable.

    Returns
    -------
    set
        The values, without repetitions.
    """
    return set(dictionary.values())

print(unique_values({"a": 1, "b": 2, "c": 1, "d": 3}))
WarningEncrypted Code

Write a function named decrypt(message, rules) that decodes a message using a dictionary of substitution rules.

Sample input:

message = "jimmq yqtmf"
rules = {
    "j": "h",
    "i": "e",
    "m": "l",
    "q": "o",
    "y": "w",
    "t": "r",
    "f": "d",
    " ": " ",
}

Expected result: "hello world"

NoteAnagrams

Write a function named are_anagrams(first, second) that uses dictionaries to determine whether two strings are anagrams. Ignore spaces, punctuation, and capitalization.

Sample input: are_anagrams("listen", "silent")
Expected result: True

def letter_counts(text: str) -> dict[str, int]:
    """
    Count each letter and digit in a text, ignoring case.

    Spaces and punctuation are not counted.

    Parameters
    ----------
    text : str
        The text to analyse.

    Returns
    -------
    dict[str, int]
        How many times each lowercase character appears.
    """
    counts = {}

    for character in text.lower():
        if character.isalnum():
            counts[character] = counts.get(character, 0) + 1

    return counts

def are_anagrams(first: str, second: str) -> bool:
    """
    Check whether two strings are anagrams.

    Spaces, punctuation and capitalization are ignored.

    Parameters
    ----------
    first : str
        The first string.
    second : str
        The second string.

    Returns
    -------
    bool
        True if both strings use the same letters the same number of times.
    """
    return letter_counts(first) == letter_counts(second)

print(are_anagrams("listen", "silent"))
WarningStudent Gradebook

Create a dictionary whose keys are student names and whose values are lists of test scores. Write functions that calculate each student’s average and the overall class average.

Sample input:

gradebook = {
    "Alice": [90, 85, 88],
    "Bob": [78, 92, 87],
    "Charlie": [95, 89, 91],
}

Expected results:

Alice's average: 87.67
Bob's average: 85.67
Charlie's average: 91.67
Class average: 88.33
WarningWord Frequency Counter

Write a function named word_frequencies(text) that returns a dictionary whose keys are words and whose values are their frequencies. Ignore punctuation at the beginning or end of each word.

Sample input: "This is a sample sentence. This sentence is a sample."

Expected result:

{
    "This": 2,
    "is": 2,
    "a": 2,
    "sample": 2,
    "sentence": 2,
}
WarningMerge Dictionaries

Write a function named merge_dictionaries(first, second) that returns a new dictionary containing the key-value pairs from both inputs. When a key appears in both dictionaries, sum its values.

Sample input:

first = {"a": 10, "b": 20, "c": 30}
second = {"b": 5, "c": 15, "d": 25}

Expected result: {"a": 10, "b": 25, "c": 45, "d": 25}

Mathematical Applications

These exercises apply data structures to problems from calculus, discrete mathematics, geometry, and linear algebra.

NoteNumerical Continuity Check

Write a function named is_continuous(f, c) that performs a numerical check of whether f appears continuous at c.

Use these tests:

f = lambda x: x**2

print(is_continuous(f, 1))

Expected result: True.

f = lambda x: abs(x)

print(is_continuous(f, 0))

Expected result: True.

def f(x):
    if x < 0:
        return x - 1
    return x

print(is_continuous(f, 0))

Expected result: False.

from collections.abc import Callable


def is_continuous(f: Callable[[float], float], c: float) -> bool:
    """
    Check numerically whether a function looks continuous at a point.

    Parameters
    ----------
    f : Callable[[float], float]
        The function to test.
    c : float
        The point where continuity is checked.

    Returns
    -------
    bool
        True if ``f`` just to the left and right of ``c`` is close to
        ``f(c)``, False otherwise (also if ``f`` cannot be evaluated).
    """
    epsilon = 1e-4
    delta = 1e-6

    try:
        value = f(c)
        left_value = f(c - delta)
        right_value = f(c + delta)
    except (TypeError, ValueError, ZeroDivisionError):
        return False

    left_is_close = abs(left_value - value) < epsilon
    right_is_close = abs(right_value - value) < epsilon

    return left_is_close and right_is_close

This is a numerical heuristic, not a mathematical proof of continuity.

NoteContinuity with Custom Precision

Extend is_continuous() with optional keyword arguments named epsilon and delta. Both should have positive default values. Raise a ValueError if either argument is not positive.

from collections.abc import Callable


def is_continuous(
    f: Callable[[float], float],
    c: float,
    epsilon: float = 1e-4,
    delta: float = 1e-6,
) -> bool:
    """
    Check numerically whether a function looks continuous at a point.

    Parameters
    ----------
    f : Callable[[float], float]
        The function to test.
    c : float
        The point where continuity is checked.
    epsilon : float, optional
        Maximum allowed difference between function values.
        Default is 1e-4.
    delta : float, optional
        Distance from ``c`` of the points evaluated on each side.
        Default is 1e-6.

    Returns
    -------
    bool
        True if ``f(c - delta)`` and ``f(c + delta)`` are both within
        ``epsilon`` of ``f(c)``, False otherwise (also if ``f`` cannot be
        evaluated).

    Raises
    ------
    ValueError
        If ``epsilon`` or ``delta`` is not positive.
    """
    if epsilon <= 0 or delta <= 0:
        raise ValueError("epsilon and delta must be positive")

    try:
        value = f(c)
        left_value = f(c - delta)
        right_value = f(c + delta)
    except (TypeError, ValueError, ZeroDivisionError):
        return False

    return (
        abs(left_value - value) < epsilon
        and abs(right_value - value) < epsilon
    )
NoteCounting Three-Element Subsets

Define a function named count_subsets(sample, size=3) that returns the number of different subsets of the requested size. The order of the elements does not matter.

sample = {1, 2, 3, 4, 5}

print(count_subsets(sample))

Expected result: 10.

from math import comb


def count_subsets(sample: set, size: int = 3) -> int:
    """
    Count the subsets of a given size, ignoring order.

    Parameters
    ----------
    sample : set
        The elements to choose from.
    size : int, optional
        The number of elements in each subset. Default is 3.

    Returns
    -------
    int
        The number of subsets, or 0 if ``size`` is negative or larger
        than ``sample``.
    """
    if size < 0 or size > len(sample):
        return 0

    return comb(len(sample), size)

The source review called these ordered subsets, but the expected value 10 corresponds to unordered combinations. Five elements would produce 60 ordered arrangements of length three.

NoteShowing the Subsets

Extend the previous function with a keyword argument named show_subsets, which should default to False.

  • If show_subsets is False, return only the count.
  • If show_subsets is True, return a tuple containing the count and a list of the subsets.
from itertools import combinations


def count_subsets(
    sample: set, size: int = 3, show_subsets: bool = False
) -> int | tuple[int, list[tuple]]:
    """
    Count the subsets of a given size, and optionally return them.

    Parameters
    ----------
    sample : set
        The elements to choose from.
    size : int, optional
        The number of elements in each subset. Default is 3.
    show_subsets : bool, optional
        Whether to also return the subsets. Default is False.

    Returns
    -------
    int | tuple[int, list[tuple]]
        The number of subsets, or ``(count, subsets)`` if ``show_subsets``
        is True. Each subset is a tuple.
    """
    subsets = list(combinations(sample, size))

    if show_subsets:
        return len(subsets), subsets

    return len(subsets)
NoteVector Projection

Write a function named projection(u, v) that returns the orthogonal projection of vector u onto vector v.

Use the formula:

\[ \operatorname{proj}_{v}(u) = \frac{u \cdot v}{v \cdot v}v \]

u = [2, 2]
v = [1, 0]

print(projection(u, v))

Expected result: [2.0, 0.0].

u = [3, 1, 2]
v = [1, 0, 1]

print(projection(u, v))

Expected result: [2.5, 0.0, 2.5].

def dot_product(vector_1: list[float], vector_2: list[float]) -> float:
    """
    Return the dot product of two vectors.

    Parameters
    ----------
    vector_1 : list[float]
        The first vector.
    vector_2 : list[float]
        The second vector.

    Returns
    -------
    float
        The sum of the products of matching coordinates.

    Raises
    ------
    ValueError
        If the vectors have different lengths.
    """
    if len(vector_1) != len(vector_2):
        raise ValueError("Vectors must have the same length")

    return sum(
        value_1 * value_2
        for value_1, value_2 in zip(vector_1, vector_2)
    )


def projection(u: list[float], v: list[float]) -> list[float]:
    """
    Return the orthogonal projection of ``u`` onto ``v``.

    Parameters
    ----------
    u : list[float]
        The vector to project.
    v : list[float]
        The vector to project onto.

    Returns
    -------
    list[float]
        The projection of ``u`` onto ``v``.

    Raises
    ------
    ValueError
        If ``v`` is the zero vector or the vectors have different lengths.
    """
    denominator = dot_product(v, v)

    if denominator == 0:
        raise ValueError("Cannot project onto the zero vector")

    scale = dot_product(u, v) / denominator
    return [scale * coordinate for coordinate in v]
NoteLinear Independence

Implement a function named is_independent(vectors) that determines whether a list of vectors is linearly independent.

v1 = [1, 0, 0]
v2 = [0, 1, 0]
v3 = [1, 1, 0]

print(is_independent([v1, v2, v3]))

Expected result: False.

v1 = [1, 0, 0]
v2 = [0, 1, 0]
v3 = [1, 0, 1]

print(is_independent([v1, v2, v3]))

Expected result: True.

def matrix_rank(
    matrix: list[list[float]], tolerance: float = 1e-10
) -> int:
    """
    Return the rank of a matrix using Gaussian elimination.

    Parameters
    ----------
    matrix : list[list[float]]
        The matrix, given as a list of rows. It is not modified.
    tolerance : float, optional
        Values with absolute value at or below this are treated as zero.
        Default is 1e-10.

    Returns
    -------
    int
        The rank of the matrix (0 for an empty matrix).

    Raises
    ------
    ValueError
        If the rows have different lengths.
    """
    if not matrix:
        return 0

    column_count = len(matrix[0])

    if any(len(row) != column_count for row in matrix):
        raise ValueError("All vectors must have the same length")

    work = [list(map(float, row)) for row in matrix]
    row_count = len(work)
    rank = 0

    for column in range(column_count):
        pivot_row = None

        for row in range(rank, row_count):
            if abs(work[row][column]) > tolerance:
                pivot_row = row
                break

        if pivot_row is None:
            continue

        work[rank], work[pivot_row] = work[pivot_row], work[rank]
        pivot = work[rank][column]

        for current_column in range(column, column_count):
            work[rank][current_column] /= pivot

        for row in range(row_count):
            if row == rank:
                continue

            factor = work[row][column]

            for current_column in range(column, column_count):
                work[row][current_column] -= (
                    factor * work[rank][current_column]
                )

        rank += 1

        if rank == row_count:
            break

    return rank


def is_independent(vectors: list[list[float]]) -> bool:
    """
    Check whether a list of vectors is linearly independent.

    Parameters
    ----------
    vectors : list[list[float]]
        The vectors to check, all with the same length.

    Returns
    -------
    bool
        True if the vectors are linearly independent, False otherwise.

    Raises
    ------
    ValueError
        If the vectors have different lengths.
    """
    return matrix_rank(vectors) == len(vectors)
NoteFind an Independent Subset

Write a function named independent_indices(vectors) that returns the positions of a linearly independent subset. Number the vectors starting at 1.

v1 = [1, 0, 0]
v2 = [0, 1, 0]
v3 = [2, 0, 0]

print(independent_indices([v1, v2, v3]))

Expected result: [1, 2].

This solution uses matrix_rank() from the previous exercise.

def independent_indices(vectors: list[list[float]]) -> list[int]:
    """
    Return the positions of a linearly independent subset of vectors.

    Each vector is kept if it is independent of the ones kept before it.

    Parameters
    ----------
    vectors : list[list[float]]
        The vectors to choose from, all with the same length.

    Returns
    -------
    list[int]
        The positions of the selected vectors, starting at 1.

    Raises
    ------
    ValueError
        If the vectors have different lengths.
    """
    basis = []
    selected_indices = []

    for index, vector in enumerate(vectors, 1):
        previous_rank = matrix_rank(basis)
        candidate_rank = matrix_rank(basis + [vector])

        if candidate_rank > previous_rank:
            basis.append(vector)
            selected_indices.append(index)

    return selected_indices