Exercises: Lists and loops

Module 5: lists, repetition, randomness, and simulation

Name:

Student number:

Choose one answer for each multiple-choice question. Write the list-checking function in Python. For the guessing game, choose Python, pseudocode, or a flowchart. Complete the tables in the sorting trace question. Show the reasoning and checks requested in each question.

M1) Read positions in a nested list

In Listing 1, four variables named a, b, c, and d are read from a nested list. The first index selects a row and the second index selects a column.

In row[::-1], the slice [::-1] makes a new list with the items in reverse order. Python’s built-in reversed(row) visits the same items from last to first; list(reversed(row)) also makes a reversed list.

Listing 1: Reading four values from a 3-by-3 nested list (Question 1). 
# Each inner list is one row.
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

a = matrix[2][0]
b = matrix[0][2]
c = matrix[-1][-2]
d = matrix[1][::-1]

What values do a, b, c, and d contain?

  • a = 3, b = 7, c = 6, and d = [6, 5, 4].
  • a = 7, b = 3, c = 9, and d = [6, 5, 4].
  • a = 7, b = 3, c = 8, and d = [6, 5, 4].
  • a = 7, b = 3, c = 8, and d = [4, 5, 6].

M2) Conditional sum

The loop in Listing 2 adds each even value of i to total.

Listing 2: Conditional sum using a for loop (Question 2). 
total = 0  # Running total for the selected values.

for i in range(1, 5):
    if i % 2 == 0:
        total = total + i

What is total after the loop?

  1. 0
  2. 3
  3. 6
  4. 10

M3) Decreasing sequence

The function in Listing 3 builds a string from the values visited by a for loop.

Listing 3: A for loop with a step of -2 (Question 3). 
def mysterious_loop(n: int) -> str:
    result = ""  # Text to return after the loop.

    for i in range(n, 0, -2):
        result = result + str(i) + " "

    return result

What does mysterious_loop return for n = 0, n = 1, n = 5, and n = 6? Each visited number is followed by one space.

  1. n = 0: "" / n = 1: "1 " / n = 5: "5 3 1 " / n = 6: "6 4 2 ".
  2. n = 0: "0 " / n = 1: "1 " / n = 5: "5 3 1 -1 " / n = 6: "6 4 2 0 ".
  3. n = 0: "" / n = 1: "1 " / n = 5: "5 3 1 -1 " / n = 6: "6 4 2 0 ".
  4. n = 0: "" / n = 1: "1 " / n = 5: "5 4 3 2 1" / n = 6: "6 4 2 0 ".

M4) Output of a while loop

The while loop in Listing 4 prints num and then increases it by 2.

Listing 4: Printing num while it is less than 10. 
num = 5  # First value in the sequence.

while num < 10:
    print(num)
    num = num + 2

Which sequence does the loop print?

  1. 7, 9
  2. 5, 6, 7, 8, 9
  3. 5, 6, 7, 8, 9, 10
  4. 5, 7, 9

M5) Decreasing loop with continue

The loop in Listing 5 uses continue before its print statement.

Listing 5: A decreasing for loop with continue (Question 5). 
for i in range(4, 0, -2):
    # Decide whether to display the current value.
    if i % 2 == 0:
        continue

    print(i)

What does the code print?

  1. 4, 2, 0
  2. 4, 2, 0, -2
  3. Nothing is printed.
  4. 4, 2, 0, -2, -4
TipHow continue works

The continue statement skips the rest of the current loop iteration and moves to the next value.

M6) Finding a value in a list

The function in Listing 6 performs a linear search: it checks items in order and returns the zero-based index of the first match. If the value is absent, it returns -1.

Listing 6: A Python function find_first_index that receives a list and a value as arguments and returns the zero-based index of the first match, or -1 if no match exists (Question 6). 
def find_first_index(values: list[int], value: int) -> int:
    for i in range(len(values)):
        if values[i] == value:
            return i  # Stop at the first match.

    return -1  # No match was found.


def main() -> None:
    arr: list[int] = [1, 2, 0, 4, 5, 0, 0, 0, 0, 0, 0]
    print(find_first_index(arr, 5))


# Run the example when this file is executed.
if __name__ == "__main__":
    main()

What does the listing print?

  1. 4
  2. 5
  3. -1
  4. 0

M7) Finding the first even number

Each version of find_first_even in Listing 7 receives a list of integers. The function should print the first even number and stop. If the list has no even number, it should print No even number found.

Listing 7: Alternative implementations of the find_first_even function. The function finds and prints the first even number in a finite list, or prints No even number found. if the list contains no even number (Question 7).
(a) 
def find_first_even(numbers):
    for number in numbers[:4]:
        if number % 2 == 0:
            print(number)
            # Stop after printing a match.
            return

    print("No even number found.")
(b) 
def find_first_even(numbers):
    for number in numbers:
        if number % 2 == 0:
            print(number)
            # Stop after printing a match.
            return

    print("No even number found.")
(c) 
def find_first_even(numbers):
    for i in range(1, len(numbers)):
        if numbers[i] % 2 == 0:
            print(numbers[i])
            # Stop after printing a match.
            return

    print("No even number found.")
(d) 
def find_first_even(numbers):
    for number in numbers:
        if number % 2 != 0:
            print(number)
            # Stop after printing a match.
            return

    print("No even number found.")

The list can have any length. Which implementation meets the rule?

  1. Listing 7 (a)
  2. Listing 7 (b)
  3. Listing 7 (c)
  4. Listing 7 (d)

M8) Replacing negative values

The four versions of remove_negatives in Listing 8 should:

  1. Receive a list of integers.
  2. Return a new list of the same length with each negative value replaced by 0.

The input list must remain unchanged. For example, if numbers is [1, -2, 3, -4, 5], the function should return [1, 0, 3, 0, 5] while numbers remains [1, -2, 3, -4, 5].

Which implementation of the remove_negatives function in Listing 8 correctly returns the required copy without modifying the input list?

  1. Listing 8 (a)
  2. Listing 8 (b)
  3. Listing 8 (c)
  4. Listing 8 (d)
Listing 8: Alternatives for the remove_negatives function that returns a copy of a list with the negative values replaced by zero (Question 8).
(a) 
def remove_negatives(numbers):
    # Build the list to return.
    result = []

    for number in numbers:
        if number < 0:
            result.append(0)
        else:
            result.append(number)

    return result
(b) 
def remove_negatives(numbers):
    # Build the list to return.
    result = []

    for i in range(len(numbers)):
        if numbers[i] < 0:
            numbers[i] = 0

    return result
(c) 
def remove_negatives(numbers):
    # Build the list to return.
    result = []

    for i in range(len(result)):
        if numbers[i] < 0:
            result.append(0)
        else:
            result.append(numbers[i])

    return result
(d) 
def remove_negatives(numbers):
    # Build the list to return.
    result = []

    for number in numbers:
        if number < 0:
            result.append(0)

    return result

M9) Counting nested loop output

The function in Listing 9 prints two messages inside nested loops.

Listing 9: Printing messages from nested for loops (Question 9). 
def trace_nested_for_loop() -> None:
    # Report which loop is running.
    for i in range(1, 4):
        print("Outer Loop")
        for j in range(1, 3):
            print("Inner Loop")


trace_nested_for_loop()

How many times does trace_nested_for_loop print "Outer Loop" and "Inner Loop"?

  1. It prints "Outer Loop" and "Inner Loop" 3 times.
  2. It prints "Outer Loop" 3 times and "Inner Loop" 6 times.
  3. It prints "Outer Loop" 3 times and "Inner Loop" 2 times.
  4. It prints "Outer Loop" and "Inner Loop" once.

M10) Sums in a nested loop

The function in Listing 10 uses two accumulators while iterating over a rectangular nested list.

Listing 10: A Python function summing that applies two different summing methods to a rectangular nested list (Question 10). 
def summing(cell_range):
    sum1 = 0  # Keep a total for the final report.

    for row in cell_range:
        sum2 = 0
        for value in row:
            sum1 = sum1 + value
            sum2 = sum2 + value

    print(f"sum1: {sum1} - sum2: {sum2}")


cells = [
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
]

summing(cells)

What does the function print for the values in Table 1?

Table 1: Input values for the summing function (cells).
A B C
1 1 1 1
2 1 1 1
3 1 1 1
  1. sum1: 3 - sum2: 9
  2. sum1: 9 - sum2: 3
  3. sum1: 3 - sum2: 3
  4. sum1: 9 - sum2: 9

M11) Seed inside a loop

The program in Listing 11 is meant to simulate five rolls of a die, so that anyone who runs it gets the same five rolls.

random.seed(42) puts Python’s random-number generator in a fixed starting state. random.randint(1, 6) draws one integer from 1 through 6, including both endpoints. append adds each draw to rolls.

Listing 11: Simulating five die rolls with a seed (Question 11). 
import random

# Collect the die outcomes.
rolls = []

for repetition in range(5):
    random.seed(42)
    rolls.append(random.randint(1, 6))

print(rolls)

Which statement describes the list that the program prints?

  • The five values can differ, and every run prints the same list.
  • The five values are all equal, and every run prints the same list.
  • The five values are all equal, and each run prints a different list.
  • The five values can differ, and each run prints a different list.

M12) Reproducible random inputs for a simulation

A supply chain simulation can use random draws to choose uncertain demand or supplier delays. A replication is one trial of the simulation. Each replication needs a sequence of random draws, one for each decision point. The draws are inputs to the simulation; they are not its changing state or its results.

The function receives positive integers n and m. It prepares one input sequence for each of n replications, with m decision points per replication. Each sequence uses its replication number as its seed and contains m successive draws from 0 up to but not including 1.

Table 2 shows two program runs with n = 2 and m = 3. Replication 1 uses seed 1, and replication 2 uses seed 2. The second program run produces the same draws.

random.Random(seed) creates a separate random-number generator with that starting seed. Each call to rng.random() draws the next decimal value from that generator, from 0 up to but not including 1. A new generator with the same seed produces the same sequence of values.

Table 2: Random draws from two program runs. Each run prepares two replications with three decision points. Replication 1 uses seed 1, and replication 2 uses seed 2. Values are rounded to three decimal places; paired rows match across runs.
Program
run		 Replication
number		 Draw at
point 1		 Draw at
point 2		 Draw at
point 3
1 1 0.134 0.847 0.764
1 2 0.956 0.948 0.057
2 1 0.134 0.847 0.764
2 2 0.956 0.948 0.057

Listing 12 shows four versions of make_random_inputs. Each returns a list of replications. Each replication is a two-item list: [rep_no, draws], where rep_no is the replication number and draws contains its m random values in decision-point order.

Which version prepares n reproducible replications with m decision points each, using the replication number as its seed?

  1. Listing 12 (a)
  2. Listing 12 (b)
  3. Listing 12 (c)
  4. Listing 12 (d)
Listing 12: Alternative implementations of a Python function that stores m successive random draws for each of n replications in nested lists (Question 12).
(a) 
import random


def make_random_inputs(n, m):
    # Store each replication's draws together.
    inputs = []

    for rep_no in range(1, n + 1):
        rng = random.Random(n)
        draws = []
        for _ in range(m):
            draws.append(rng.random())
        inputs.append([rep_no, draws])

    return inputs
(b) 
import random


def make_random_inputs(n, m):
    # Store each replication's draws together.
    inputs = []

    for rep_no in range(1, n + 1):
        draws = []
        for point in range(1, m + 1):
            rng = random.Random(point)
            draws.append(rng.random())
        inputs.append([rep_no, draws])

    return inputs
(c) 
import random


def make_random_inputs(n, m):
    # Store each replication's draws together.
    inputs = []

    for rep_no in range(1, n + 1):
        draws = []
        for _ in range(m):
            rng = random.Random(rep_no)
            draws.append(rng.random())
        inputs.append([rep_no, draws])

    return inputs
(d) 
import random


def make_random_inputs(n, m):
    # Store each replication's draws together.
    inputs = []

    for rep_no in range(1, n + 1):
        rng = random.Random(rep_no)
        draws = []
        for _ in range(m):
            draws.append(rng.random())
        inputs.append([rep_no, draws])

    return inputs

Q1) Check whether a list is sorted

Write a Python function is_sorted(values) that returns True when a list of numbers is in ascending order, allowing equal neighboring values, and False otherwise. Do not change the list you receive. Python has a built-in sorted function, but for this exercise use a loop to compare neighboring values. Do not use sorted or the list’s sort method.

You may use the starter code in Listing 13. Run the supplied tests, then add one test case of your own and state its expected result.

Listing 13: Starter function and tests for checking whether a list is sorted. 
def is_sorted(values):
    # Add code here!
    pass


# Ascending order
got = is_sorted([1, 2, 3])
assert got is True, f"[1, 2, 3]: expected True, got {got!r}"

# Descending order
got = is_sorted([3, 2, 1])
assert got is False, f"[3, 2, 1]: expected False, got {got!r}"

# Equal neighbors still count as ascending
got = is_sorted([1, 2, 2, 3])
assert got is True, f"[1, 2, 2, 3]: expected True, got {got!r}"

# The list you receive stays as it was
numbers = [3, 1, 2]
is_sorted(numbers)
assert numbers == [3, 1, 2], f"Input changed: {numbers!r}"

# Your case: which list is most likely to break it?
# got = is_sorted(___)
# assert got is ___, f"expected ___, got {got!r}"

Q2) Build an Akinator-style guessing game

Akinator is a guessing game that asks yes-or-no questions to identify a character. The version in this question knows the five characters and four clues in Table 3.

Table 3: Clues that distinguish the five characters.
Character Can it fly? Can it breathe fire? Is it made of metal? Does it meow?
Owl Yes No No No
Dragon Yes Yes No No
Robot No No Yes No
Fox No No No No
Cat No No No Yes

Listing 14 represents the table as two lists. The questions list contains the four clue headings. In characters, each row begins with a name followed by its four clues as Boolean values, in the same order as the questions. For example, Owl can fly, cannot breathe fire, is not made of metal, and does not meow.

Listing 14: Question headings and character rows, with True for yes and False for no. 
questions = [
    "Can it fly?",
    "Can it breathe fire?",
    "Is it made of metal?",
    "Does it meow?",
]

# Each row contains a name followed by its four clues.
characters = [
    ["Owl",    True,  False, False, False],
    ["Dragon", True,  True,  False, False],
    ["Robot",  False, False, True,  False],
    ["Fox",    False, False, False, False],
    ["Cat",    False, False, False, True],
]

You may use the supplied ask(question) procedure. It displays a question and returns True for yes or False for no. For example, ask("Can it fly?") returns the player’s answer to that question.

Assume that:

  • The character list is nonempty.
  • The player’s chosen character is in the list, and the player answers truthfully.
  • The clues distinguish every character, so the game always finishes with one character remaining.

Design the game in Python, pseudocode, or a flowchart. Choose one form and follow these rules:

  1. Consider the questions in table order.
  2. Before asking a question, check whether some of the remaining characters would answer yes and others no. Skip the question if every remaining character would give the same answer.
  3. After the player answers, keep only the characters whose clue matches the answer. Give this row-filtering step its own procedure and show what it receives and returns. For example, if the remaining rows are Owl, Robot, and Fox, the answer no to “Can it fly?” keeps Robot and Fox.
  4. Stop when one character remains and report its name.

Then:

  • Show how the remaining characters change when the player thinks of Fox. Include any question the game skips and explain why.
  • Test the game with two different characters. State the questions asked and the expected guess for each.
  • Could a different fixed question order identify Dragon in fewer questions than table order? Explain.

For question position j, read the clue at position j + 1 in each row. Compare the remaining rows with the first row: if one clue differs, both answers are possible. After asking, build a new list containing only the rows whose clue matches the answer.

Q3) Trace two sorting algorithms

A youth sports club needs its members’ ages in ascending order. Sort 1 and Sort 2 both change the given list in place. Follow the algorithms in Listing 15 or their Python versions in Listing 16 for each list in the tables below.

A pass is one complete run of the outer loop on line 5 of Listing 15 (a) or line 5 of Listing 15 (b). List positions start at 0, and length(Ages) is the number of ages in the list. In both listings, from ... to ... includes both endpoints. The procedure swap(Ages, i, j) exchanges the ages at positions i and j in the same list. Sort 1 stops after a pass with no swaps. Sort 2 always makes three passes for a list of four ages.

Sort 1 in Listing 15 (a) compares neighboring ages. Sort 2 in Listing 15 (b) selects the smallest age in the part of the list that has not yet been placed in order. Both pseudocode listings use Pass to count passes, starting at 1. The variables i and j are list positions, and min is the position of the smallest age found so far. In Sort 2, pass 1 places the smallest age at position 0, pass 2 places the next smallest at position 1, and so on.

Listing 15: Two algorithms for sorting a list of ages in ascending order.
(a) Sort 1 compares adjacent ages and moves larger ages toward the end of the list. Each pass starts at the outer loop on line 5. 
Input: Ages
Output: Ages in ascending order
Start
  Set n to length(Ages)
  For Pass from 1 to n - 1
    Set Swapped to False
    For i from 0 to n - Pass - 1
      If Ages[i] > Ages[i + 1]
        Call swap(Ages, i, i + 1)
        Set Swapped to True
      End If
    End For
    # Record Ages after this pass.
    If Swapped = False
      Exit For
    End If
  End For
  Output Ages
End
(b) Sort 2 selects the smallest remaining age and moves it to the next position. Each pass starts at the outer loop on line 5. 
Input: Ages
Output: Ages in ascending order
Start
  Set n to length(Ages)
  For Pass from 1 to n - 1
    Set i to Pass - 1
    Set min to i
    For j from i + 1 to n - 1
      If Ages[j] < Ages[min]
        Set min to j
      End If
    End For
    Call swap(Ages, i, min)
    # Record Ages after this pass.
  End For
  Output Ages
End

The Python versions use range, which stops before its second argument. Both functions call swap(ages, i, j), the procedure you will write below. In Sort 2, min_i is the position of the smallest age found so far. Each function changes the original list and returns that list.

Listing 16: Python versions of Sort 1 and Sort 2 for a list of ages.
(a) Sort 1 in Python compares neighboring ages and stops after a pass with no swaps. Each pass starts at the outer loop on line 3. 
def sort_1(ages):
    n = len(ages)
    for pass_no in range(1, n):
        swapped = False
        for i in range(n - pass_no):
            if ages[i] > ages[i + 1]:
                swap(ages, i, i + 1)
                swapped = True
        # Record ages for this pass.
        if not swapped:
            break
    return ages
(b) Sort 2 in Python places the smallest remaining age at the next position. Each pass starts at the outer loop on line 3. 
def sort_2(ages):
    n = len(ages)
    for pass_no in range(1, n):
        i = pass_no - 1
        min_i = i
        for j in range(i + 1, n):
            if ages[j] < ages[min_i]:
                min_i = j
        swap(ages, i, min_i)
        # Record ages for this pass.
    return ages

Copy each list before running the second algorithm, so both start with the same ages. Record the whole list after each pass, even if no values changed. Write Stopped if an algorithm does not make that pass. Table 4 shows the first pass for [16, 14, 15, 17]. Complete that table and Table 5 and Table 6.

Table 4: Trace to complete for the ages 16, 14, 15, and 17. The first pass is worked out for both algorithms.
Pass Sort 1 list after the pass Sort 2 list after the pass
Start [16, 14, 15, 17] [16, 14, 15, 17]
1 [14, 15, 16, 17] [14, 16, 15, 17]
2
3
Table 5: Trace to complete for the ages 14, 15, 16, and 17. Record when each algorithm stops.
Pass Sort 1 list after the pass Sort 2 list after the pass
Start [14, 15, 16, 17] [14, 15, 16, 17]
1
2
3
Table 6: Trace to complete for the ages 17, 16, 15, and 14. Record the list after every pass.
Pass Sort 1 list after the pass Sort 2 list after the pass
Start [17, 16, 15, 14] [17, 16, 15, 14]
1
2
3

For each input, count the passes each algorithm makes. Did they produce the same sorted list? Which algorithm stops earlier for some inputs, and why? Name the algorithm that compares neighbors and the one that repeatedly selects the smallest remaining age. Use the first pass of the mixed list to explain why their intermediate lists differ.

Then write the Python procedure swap(ages, i, j) used by both algorithms. Assume that i and j are valid list positions. Exchange those two ages in the original list, leave every other age unchanged, and return nothing. Use simple assignments and a temporary variable rather than Python’s multiple assignment. The procedure must also work when i and j are the same position.

For Sort 1, keep track of whether any swap occurred during the pass. For Sort 2, update min while scanning; swap only after the scan ends.

To see the lists change, open the Sort 1 animation or the Sort 2 animation. In VisuAlgo, choose Exploration Mode, enter the ages under Create(A), then choose Sort. Use the playback controls to follow the comparisons and swaps one step at a time.