Sequence Types

Abstract¶

Composite data types, like tuple and lists, allow programmers to group multiple objects together efficiently. This notebook focuses on sequence types, where objects are ordered. Readers will learn how to construct sequences using enclosure and comprehension; how to access items using subscriptions and slicing; the concept of mutation; and Methods that operate on sequences, including those that cause mutations. Understanding these concepts helps in managing collections of data more effectively, leading to cleaner, more maintainable, and scalable code.

import random
from math import isqrt
from collections.abc import Iterable

Motivation¶

The following code calculates the average of two numbers:

def average_of_two(x0, x1):
    return (x0 + x1) / 2


average_of_two(0, 1)

0.5

How to calculate the average of more numbers? For instance, the average of four numbers 1, 2, 3, 4 is:

average_of_two(average_of_two(0, 1), average_of_two(2, 3))

1.5

But what about 5 numbers 0, 1, 2, 3, 4?

average_of_two(average_of_two(average_of_two(0, 1), average_of_two(2, 3)), 4)

2.75

Repeatedly applying the function does not always work. It is also impossible to specify an arbitrary number of optional arguments:

def average(x0, x1=None, x2=None, x3=None, ...):
    ...

What is needed is a composite data type (or container):

def average(*args):
    return sum(args) / len(args)


average(0, 1, 2, 3, 4)

2.0

Recall that args is a tuple that can keep a variable number of items in a sequence.

In calculating the average, sum and len return the sum and length of an iterable. There are also other built-in functions that can apply to an iterable directly:

min, max, sorted, enumerate, reversed, zip, map, filter, slice

We can do this for average as well:

def average(seq):
    return sum(seq) / len(seq)


seq = range(100)
average(seq)

49.5

max?
seq = (0, 1, 2, 3, 4)
max(seq), max(*seq)

(4, 4)

Docstring:
max(iterable, *[, default=obj, key=func]) -> value
max(arg1, arg2, *args, *[, key=func]) -> value

With a single iterable argument, return its biggest item. The
default keyword-only argument specifies an object to return if
the provided iterable is empty.
With two or more positional arguments, return the largest argument.
Type:      builtin_function_or_method

from collections.abc import Iterable


def average(*args, **kwargs):
    ### BEGIN SOLUTION
    if len(args) == 1 and isinstance(args[0], Iterable):
        args = args[0]
        if not len(args):
            return kwargs['default']
    return sum(args) / len(args)
    ### END SOLUTION

# tests
seq = (0, 1, 2, 3, 4)
assert average(seq) == 2 == average(*seq)
assert average([], default=0) == 0

Construction¶

How to store a sequence of items?

We created objects of sequence types before:

str is used to store a sequence of characters, but the items are limited to characters.
range is used to generate a sequence of numbers, but the numbers must form an arithmetic sequence.

In order to store items of possibly different types, we can use the built-in types tuple and list:

%%pytutor
a_list = "1 2 3".split()
a_tuple = (lambda *args: args)(1, 2, 3)

How to create a tuple/list?

Mathematicians often represent a collection of items in two different ways:

Roster notation, which enumerates the elements, e.g.,
$\{0, 1, 4, 9, 16, 25, 36, 49, 64, 81\}.$
(1)
Set-builder notation, which describes the content using a rule for constructing the elements, e.g.,
$\{x^2| x\in \mathbb{N}, x< 10 \},$
(2)
namely the set of perfect squares strictly less than 100, which is the same as (1). $\mathbb{N}$ denotes the set of natural numbers (including 0).

Python also provides two corresponding ways to create a collection of items:
1. Enclosure, which uses brackets to group elements together. 2. Comprehension, which uses concise syntax similar to iterations and conditionals to generate elements.

Enclosure¶

For instance, to create a tuple, we enclose a comma separated sequence of values by parentheses:

%%pytutor
empty_tuple = ()
singleton_tuple = (0,)   # why not (0)?
heterogeneous_tuple = (
    singleton_tuple, (1, 2.0), 
    print
)
enclosed_starred_tuple = (
    *range(2), 
    *"23"
)

Note from the above code that:

2nd assignment: If the enclosed sequence has one term, there must be a comma after the term.
3rd assignment: The elements of a tuple can have different types.
4th assignment: The unpacking operator * can unpack an iterable into a sequence in an enclosure.

To create a list, we use square brackets instead of parentheses to enclose objects.

%%pytutor
empty_list = []
singleton_list = [0]  # no need to write [0,]
heterogeneous_list = [
    singleton_list, 
    (1, 2.0), 
    print
]
enclosed_starred_list = [
    *range(2), 
    *"23"
]

We can also create a tuple/list from other iterables using the constructors tuple/list as well as addition and multiplication similar to str.

%%pytutor
str2list = list("Hello")
str2tuple = tuple("Hello")
range2list = list(range(5))
range2tuple = tuple(range(5))
tuple2list = list((1, 2, 3))
list2tuple = tuple([1, 2, 3])
concatenated_tuple = (1,) + (2, 3)
concatenated_list = [1, 2] + [3]
duplicated_tuple = (1,) * 2
duplicated_list = 2 * [1]

print((1 + 2) * 2, (1 + 2,) * 2, sep="\n")

6
(3, 3)

Solution to Exercise 2

(1+2)*2 evaluates to 6 but (1+2,)*2 evaluates to (3,3).

The parentheses in (1+2) indicate the addition needs to be performed first, but
the parentheses in (1+2,) creates a tuple.

Hence, singleton tuple must have a comma after the item to differentiate these two use cases.

%%hermes --no-context
Explain in a paragraph why a singleton tuple must have a comma after the item?

↻ Session: main (ACP: cbd08506-750…)

See Also

A singleton tuple must include a comma after its single element because Python’s grammar distinguishes tuple literals from parenthesized expressions solely by the presence of a comma; otherwise (item) is interpreted as a regular expression inside parentheses, simply grouping the expression and returning its value in whatever type it originally has. The comma unambiguously signals that the value inside the parentheses is to be treated as an element of a tuple, allowing the interpreter to construct a one‑element tuple (item,) instead of just evaluating item.

Comprehension¶

How to use a rule to construct a tuple/list?

We can define the rules for constructing a sequence using a comprehension, a technique we’ve previously applied in a generator expression. For example, the following Python one-liner returns a generator for prime numbers:

def prime_sequence(stop):
    return (x for x in range(2, stop) if
            all(x % d for d in range(2, isqrt(x) + 1)))


print(*prime_sequence(100))

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

There are two comprehensions used in the return value:

(x for x in range(2, stop) if ...): The comprehension creates a generator of numbers from 2 to stop-1 that satisfy the condition of the if clause.
(x % d for d in range(2, isqrt(x) + 1)): The comprehension creates a generator of remainders to the function all, which returns True if all the remainders are non-zero else False.

Alternatively, one can also use the filter and map functions instead of comprehension:

def prime_sequence_(stop):
    return filter(
        lambda x: all(
            map(lambda d: x % d, range(2, isqrt(x) + 1))
        ),
        range(2, stop)
    )

print(*prime_sequence(100))

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

### BEGIN SOLUTION
def composite_sequence(stop):
    return (x for x in range(2, stop) if any(x % d == 0 for d in range(2, x)))
### END SOLUTION

print(*composite_sequence(100))

4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 33 34 35 36 38 39 40 42 44 45 46 48 49 50 51 52 54 55 56 57 58 60 62 63 64 65 66 68 69 70 72 74 75 76 77 78 80 81 82 84 85 86 87 88 90 91 92 93 94 95 96 98 99

Comprehension can also be used to construct a list instead of a generator. An example of list comprehension is as follows:

def prime_list(stop):
    return [
        x for x in range(2, stop) if all([x % d for d in range(2, isqrt(x) + 1)])
    ]  # Enclose comprehension by square brackets

print(prime_list(100))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

As a demonstration of list comprehension, consider simulating the coin tossing game:

With list comprehension, we can easily simulate a sequence of biased coin flips as follows:

from random import random as rand

p = 1302/10000  # unknown chance of head
coin_flips = ["H" if rand() <= p else "T" for i in range(1000000)]
print("Chance of head:", p)
print("Coin flips:", *coin_flips[:100], "...")

Chance of head: 0.1302
Coin flips: T T H T H T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T H T T H T T T T T T T T H T T T T T T T T T T T T T T T T H T T T H H T T T H T T H T T T T T T T H T T T H T T T T T T T T T T ...

p should be kept secret, while coin_flips can be shown to the player:

H means a head comes up, and
T means a tail comes up.

How to estimate the chance p from coin_flips?

Given that there $k$ heads in $n$ coin flips, a simple estimate is the fractional count of heads observed:

\hat{p} = \frac{k}{n}.

(3)

head_indicators = [1 if outcome == "H" else 0 for outcome in coin_flips]
phat = sum(head_indicators) / len(head_indicators)
print("Fraction of heads observed:", phat)

Fraction of heads observed: 0.129931

Does the estimate look reasonable? How accurate is this estimate?

Let’s formulate the problem mathematically. Denote the total number of coin flips by $n$ . For $1\leq i\leq n$ , define

x_i := \begin{cases} 1 & \text{if a head comes up in the $i$-th coin-flip,}\\ 0 & \text{otherwise,} \end{cases}

(4)

which is called an indicator variable.

The estimate above can be expressed in terms of $n$ and $x_i$ ’s as follows:

\hat{p} := \frac{\sum_{i=1}^n x_i}{n},

(5)

namely, the sample average of $x_i$ ’s. (Why?) This is an example of an M-estimator.

The variation of the estimate can be calculated from the sample variance:^[1]

\begin{align} v &:= \frac{\sum_{i=1}^n (x_i- \hat{p})^2}{n} \\ &= \left(\frac1n\sum_{i=1}^n x_i^2\right) - \hat{p}^2. \end{align}

(6)

Except for a small chance of $5\%$ ,

p \approx \hat{p} \pm 2\sqrt{\frac{v}{n}},

(7)

which is called the $95\%$ -confidence interval estimate.^[2]

def variance(seq):
    ### BEGIN SOLUTION
    return (
        (sum(i**2 for i in seq) / len(seq) - average(seq) ** 2)
    )
    ### END SOLUTION

v = variance(head_indicators)
n = len(head_indicators)

delta = 2 * (v / n) ** 0.5
print(f"p \u2248 {phat:.4f} \u00B1 {delta:.4f} except for 5% chance.")
print(
    "95% confidence interval estimate of p: [{:.4f},{:.4f}]".format(
        phat - delta, phat + delta
    )
)

p ≈ 0.1299 ± 0.0007 except for 5% chance.
95% confidence interval estimate of p: [0.1293,0.1306]

There is a simpler way to calculate the variance for coin tosses, which follows a Bernoulli distribution:

v = phat * (1 - phat)
print(f"p \u2248 {phat:.4f} \u00B1 {2*(v/n)**0.5:.4f}")

p ≈ 0.1299 ± 0.0007

%%hermes --no-context
Explain the formula for the variance of samples of Bernoulli variables.

↻ Session: main (ACP: cbd08506-750…)

See Also

\begin{aligned} &\text{Let }X_i\;\sim\;\text{Bernoulli}(p),\; i=1,\dots,n.\\ &\text{Define }S_n = \sum_{i=1}^n X_i \;\;\Longrightarrow\;\; S_n \sim \text{Binomial}(n,p).\\[4pt] &\text{For a Bernoulli variable }X,\; \operatorname{Var}(X)=p(1-p).\\ &\text{Hence}\\ &\qquad \operatorname{Var}(S_n)=\sum_{i=1}^n \operatorname{Var}(X_i)=np(1-p),\\ &\qquad\text{because the }X_i\text{ are independent.}\\[4pt] &\text{For the sample mean }\bar X_n=\frac{S_n}{n},\\ &\qquad \operatorname{Var}(\bar X_n)=\frac{1}{n^2}\operatorname{Var}(S_n) =\frac{1}{n^2}\bigl(np(1-p)\bigr) =\frac{p(1-p)}{n}. \end{aligned}

(8)

Operations¶

Selection¶

How to traverse a tuple/list?

We can use a for loop to iterate over all the items in order.

a = (*range(5),)
for item in a:
    print(item, end=" ")

0 1 2 3 4

To do it in reverse, we can use the reversed function.

reversed?
a = [*range(5)]
for item in reversed(a):
    print(item, end=" ")

4 3 2 1 0

Init signature: reversed(sequence, /)
Docstring:      Return a reverse iterator over the values of the given sequence.
Type:           type
Subclasses:

We can also traverse multiple tuples/lists simultaneously by zipping them.

zip?
a = (*range(5),)
b = reversed(a)
for item1, item2 in zip(a, b):
    print(item1, item2)

Init signature: zip(*iterables, strict=False)
Docstring:     
The zip object yields n-length tuples, where n is the number of
iterables passed as positional arguments to zip().  The i-th element
in every tuple comes from the i-th iterable argument to zip().  This
continues until the shortest argument is exhausted.

If strict is true and one of the arguments is exhausted before the
others, raise a ValueError.

   >>> list(zip('abcdefg', range(3), range(4)))
   [('a', 0, 0), ('b', 1, 1), ('c', 2, 2)]
Type:           type
Subclasses:

How to select an item in a sequence?

We can select an item of a sequence a by subscription

a[i]

where a is a list and i is an integer index.

A non-negative index indicates the distance from the beginning.

\boldsymbol{a} = (a_0, ... , a_{n-1})

(9)

%%pytutor
a = (*range(10),)
print(a)
print("Length:", len(a))
print("First element:", a[0])
print("Second element:", a[1])
print("Last element:", a[len(a) - 1])
print(a[len(a)])  # IndexError

A negative index represents a negative offset from an imaginary element one past the end of the sequence.

\begin{aligned} \boldsymbol{a} &= (a_0, ... , a_{n-1})\\ & = (a_{-n}, ..., a_{-1}) \end{aligned}

(10)

%%pytutor
a = [*range(10)]
print(a)
print("Last element:", a[-1])
print("Second last element:", a[-2])
print("First element:", a[-len(a)])
print(a[-len(a) - 1])  # IndexError

How to select multiple items?

We can use slicing to select a range of items as follows:

a[start:stop]
a[start:stop:step]

The selected items corresponds to those indexed using range:

(a[i] for i in range(start, stop))
(a[i] for i in range(start, stop, step))

a = (*range(10),)
print(a[1:4])
print(a[1:4:2])

(1, 2, 3)
(1, 3)

Unlike range, the parameters for slicing take their default values if missing or equal to None:

a = [*range(10)]
print(a[:4])  # start defaults to 0
print(a[1:])  # stop defaults to len(a)
print(a[1:4:])  # step defaults to 1

[0, 1, 2, 3]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3]

The parameters can also take negative values:

print(a[-1:])
print(a[:-1])
print(a[::-1])  # What are the default values used here?

[9]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

A mixture of negative and positive values are also okay:

print(a[-1:1])      # equal [a[-1], a[0]]?
print(a[1:-1])      # equal []?
print(a[1:-1:-1])   # equal [a[1], a[0]]?
print(a[-100:100])  # result in IndexError like subscription?

[]
[1, 2, 3, 4, 5, 6, 7, 8]
[]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Can AI explain the rules for slicing?

%%hermes --no-context
Explain very concisely in a paragraph or two how the default values of 
start, stop, and step are determined in the slicing operations in Python:
```python
print(a[-1:1])      # equal [a[-1], a[0]]?
print(a[1:-1])      # equal []?
print(a[1:-1:-1])   # equal [a[1], a[0]]?
print(a[-100:100])  # result in IndexError like subscription?
```

↻ Session: main (ACP: cbd08506-750…)

See Also

How Python chooses the defaults for a slice

Slice	Undefined parts →	Rules applied
`a[start:stop]` (`step` omitted)	`start` → `0` if step > 0, `len(a)-1` if step < 0	`stop` → `len(a)` if step > 0, `-1` if step < 0
`a[start:stop:step]`	`start` → `0` (step > 0) or `len(a)-1` (step < 0)	`stop` → `len(a)` (step > 0) or `-1` (step < 0)

Indices that are out of range are clipped to the valid boundaries; slicing never raises an IndexError.

What each of your examples actually returns

a[-1:1]
- start = -1 (last element)
- stop = 1
- step = 1 (default)
  Step > 0 but start (≈len‑1) > stop (1), so the slice is empty → [].
a[1:-1]
- start = 1
- stop = -1 (which is len(a)-1)
- step = 1
  This includes indices 1 up to len(a)-2. It is [] only when len(a) < 3.
a[1:-1:-1]
- start = 1
- stop = -1
- step = -1
  Since step < 0, traversal moves backwards until reaching stop (exclusive). The result is [a[1], a[0]] if the list has at least two items.
a[-100:100]
- start = -100 → becomes max(0, len(a)-100)
- stop = 100 → capped at len(a)
- step = 1
  The slice simply returns the whole list (or a large sub‑segment if the list is shorter). No IndexError is raised.

These rules explain why the first two prints return empty lists, the third returns the first two elements, and the last does not raise an error.

def sss(a, i=None, j=None, k=None):
    ### BEGIN SOLUTION
    l = len(a)
    step = 1 if k is None else k
    m = l if step > 0 else l - 1
    start = 0 if i is None else min(i if i > 0 else max(i + l, 0), m)
    stop = l if j is None else min(j if j > 0 else max(j + l, 0), m)
    ### END SOLUTION
    return start, stop, step


a = [*range(10)]
assert sss(a, -1, 1) == (9, 1, 1)
assert sss(a, 1, -1) == (1, 9, 1)
assert sss(a, 1, -1, -1) == (1, 9, -1)
assert sss(a, -100, 100) == (0, 10, 1)

def quicksort(seq):
    """Return a sorted list of items from seq."""
    if len(seq) <= 1:
        return list(seq)
    i = random.randint(0, len(seq) - 1)
    pivot, others = seq[i], [*seq[:i], *seq[i + 1 :]]
    left = quicksort([x for x in others if x < pivot])
    right = quicksort([x for x in others if x >= pivot])
    return [*left, pivot, *right]


seq = [random.randint(0, 99) for i in range(10)]
print(seq, quicksort(seq), sep="\n")

[38, 47, 19, 1, 4, 60, 93, 40, 4, 58]
[1, 4, 4, 19, 38, 40, 47, 58, 60, 93]

Solution to Exercise 6

The above recursion creates a sorted list as [*left, pivot, *right] where

pivot is a randomly selected item in seq,
left is the sorted list of items smaller than pivot, and
right is the sorted list of items no smaller than pivot.

The base case happens when seq contains at most one item, in which case seq is already sorted.

Solution to Exercise 7 #

Interleaving two lists using slicing:

def interleave_slice(a, b):
    result = [None] * len(a) * 2
    result[::2] = a
    result[1::2] = b
    return result

Using list comprehensions:

def interleave_comp(a, b):
    return [x for pair in zip(a, b) for x in pair]

Evaluation points:

Slicing approach is fast (O(n)) and leverages Python’s efficient slice assignment.
List comprehension with zip() is more readable and Pythonic.
Both produce the same result for equal-length lists.
The AI should handle edge cases: empty lists, lists of different lengths (using itertools.zip_longest if needed).

Quick sort is an example of randomized algorithm. In particular, the pivot is randomly chosen. Why?

%%hermes --no-context
For the quicksort algorithm, explain in a paragraph whether it is okay to pick
the pivot deterministically, say the first element of the sequence?

↻ Session: main (ACP: cbd08506-750…)

See Also

Choosing a deterministic pivot such as the first element in quicksort is generally not advisable because it turns the algorithm into a worst‑case performer on already‑sorted, nearly‑sorted, or specially crafted inputs. In these cases every partition creates an imbalanced split, leading to O(n²) time complexity instead of the expected O(n log n). Randomizing the pivot (or using median‑of‑three heuristics) breaks the pathological patterns and keeps the average‑case performance stable. Therefore, while a deterministic pivot is simple to implement, it undermines quicksort’s efficiency guarantees in practice.

%%hermes --no-context
Explain in a paragraph what randomized algorithm is and how
randomization helps.

↻ Session: main (ACP: cbd08506-750…)

See Also

A randomized algorithm is an algorithm that, besides reading its input, internally generates random numbers or makes random choices (for example, picking a random pivot in quicksort, randomly hashing keys, or flipping a coin to decide a branch) and therefore can take different execution paths on the same input. Randomization helps by smoothing out worst‑case instances, ensuring that the algorithm performs well on average, breaking symmetry that would otherwise lead to pathological behavior, and often simplifying the design of solutions that would be much more complex or slower if forced to be deterministic (such as linear‑time selection, randomized quicksort, or hash‑based data structures).

%%hermes --no-context
Explain briefly in a paragraph or two whether we can derandomize a randomized
algorithm without loss of efficiency. Is P=BPP?

↻ Session: main (ACP: cbd08506-750…)

See Also

Can we derandomize without hurting efficiency?
In general, a truly efficient derandomization is only known for special cases. For many classic randomized algorithms (e.g., Las‑Vegas selection, linear‑time Karger’s minimum cut, or randomized quicksort), a deterministic counterpart exists whose running time matches the expected cost of the random version up to constant factors. However, there are also pivotal examples where the best known deterministic algorithm is asymptotically slower: the primality test—Miller‑Rabin runs in (O((\log n)^4)) expected time, while the first deterministic polynomial‑time test (AKS) requires roughly (O((\log n)^{6.5})). Thus, derandomization without loss of efficiency is not guaranteed and often remains an open challenge.

Is P = BPP?
P (deterministic polynomial time) versus BPP (bounded‑error probabilistic polynomial time) is one of the central open questions in theoretical computer science. If every problem solvable efficiently with randomness could also be solved deterministically in the same time, we would have (P = BPP). While many believe the two classes coincide—because apparent randomness advantages can often be removed by clever deterministic constructions—no proof or counterexample has yet been found. Consequently, the question remains open, and the cost of derandomization for arbitrary algorithms is still unknown.

Computational Complexity Classes

Mutation¶

What is the difference between tuple and list?

List is mutable, allowing changes after creation; but
tuple is immutable, which cannot be modified after creation.

%%hermes --no-context
Explain in a paragraph or two why one would prefer tuple over list in Python, 
given that list is mutable but tuple is not?

↻ Session: main (ACP: cbd08506-750…)

Why a tuple is often a better choice than a list

Tuples are immutable, which means once they are created they cannot be altered. That immutability gives the interpreter several optimizations that lists cannot obtain. A tuple’s internal representation is fixed after creation, allowing Python to use a compact, read‑only block of memory and to compute a hash value once for the whole object. As a result tuples are slightly faster to create and iterate over, use less memory, and can safely be used as dictionary keys or set members—something a list can never do.

From a design‑perspective, choosing a tuple signals intent: the values it holds are a fixed grouping that should never change. This protects code from accidental mutation, makes reasoning about program state easier, and is especially valuable in concurrent or performance‑critical contexts. In short, when the collection represents a fixed, constant “record” of values, a tuple’s immutability and extra guarantees outweigh the flexibility that a mutable list provides.

For list (but not tuple), subscription and slicing can also be used as the target of an assignment operation to mutate the list:

%%pytutor
b = [*range(10)]  # aliasing
b[::2] = b[:5]
b[0:1] = b[:5]
b[::2] = b[:5]  # fails

Last assignment fails because [::2] with step size not equal to 1 is an extended slice, which can only be assigned a list of equal size.

%%hermes --no-context
Explain in a paragraph or two the following limitation of extended slice in 
Python as compared to the basic slice:
When assigning to an extended slice, the list on the right hand side of the 
statement must contain the same number of items as the slice it is replacing.

↻ Session: main (ACP: cbd08506-750…)

See Also

When you write an extended slice assignment, such as

a[1:9:2] = [10, 11, 12, 13]

Python interprets the slice as a specific set of indices that are equally spaced (here, 1, 3, 5, 7). The right‑hand side ([10, 11, 12, 13]) must provide exactly one value for each of those indices. This one‑to‑one mapping is necessary because the interpreter simply replaces each selected element in place; it cannot shift the surrounding elements to make room or remove them, as it does with a simple slice. If the RHS were longer or shorter than the number of selected indices, Python would have no place to put the extra items or would leave some positions unchanged, so it raises ValueError: attempt to assign sequence of size … to extended slice of size ….

With a basic slice (a[1:9]) the situation differs. A normal slice denotes a contiguous block, and when you assign to it, Python is allowed to grow or shrink the list — elements before or after the slice can be re‑indexed to accommodate any size of RHS. This flexibility is not available with extended slices because the step value creates a rigid pattern that cannot be altered by insertion or deletion of elements.

What is the difference between mutation and aliasing?

In the previous code:

The first assignment b = [*range(10)] is aliasing, which gives the list the target name/identifier b.
Other assignments such as b[::2] = b[:5] are mutations that calls __setitem__ because the target b[::2] is not an identifier.

list.__setitem__?

Signature:      list.__setitem__(self, key, value, /)
Call signature: list.__setitem__(*args, **kwargs)
Type:           wrapper_descriptor
String form:    <slot wrapper '__setitem__' of 'list' objects>
Namespace:      Python builtin
Docstring:      Set self[key] to value.

# %%pytutor
a = b = [0]
b[0] = a[0] + 1
print(a[0] < b[0])

False

Solution to Exercise 8

The first line a = b makes a an alias of the same object b points to, and so
the second line mutates the same object a and b point to.
Hence, a[0] == b[0].

a = [0, 1]
i = 0
a.__setitem__(i := i + 1, i)
print(a)
code1=In[-1].rsplit('\n',maxsplit=1)[0]

[0, 1]

a = [0, 1]
i = 0
a[i := i + 1] = a[i]
print(a)
code2=In[-1].rsplit('\n',maxsplit=1)[0]

[0, 0]

Solution to Exercise 9

a[i := i + 1] = a[i] is not the same as calling a.__setitem__(i := i + 1, i). According to the python documentation,

the expression to be assigned, i.e., a[i], is first evaluated to a[0] and therefore 0;
since the target a[i := i + 1] is a user defined object, it continues to evaluate the target reference, i.e., the address of a, which corresponds to the list [0, 1],
followed by the subscription i:=i+1, which evaluates to 1;
Finally, a.__setitem__ is called with the subscription, 1, and expression to be assigned, 0, and so the list a points to is mutated to [0, 1].

In comparison, directly calling a.__setitem__(i := i + 1, i)

first evaluates the first argument i := i + 1, which gives 1 that is assigned to i, and
then evaluates the second argument i to 1, and so
a.__setitem__(1, 1) is called instead, which does not change the list a points to.

Let’s see if AI has the correct understanding:

%%hermes --no-context
Explain what gets printed when running the following Python code:
---
{code2}

↻ Session: main (ACP: cbd08506-750…)

See Also

[0, 1]

Why this happens

Evaluation order of a subscript assignment
In a statement like a[i] = b, Python first evaluates the left‑hand side (the container a and the index i) before it evaluates the right‑hand side expression b.
The byte‑code order is LOAD_NAME a → LOAD_NAME i → LOAD_NAME b → STORE_SUBSCR, so the index is computed before the value that will be stored.
Execution of the walrus expression
The index in our code is the walrus expression i := i + 1.
- Before the assignment begins, i is 0.
- The walrus increments i to 1 and yields that value. Thus the target becomes a[1].
Right‑hand side evaluation
After the target is known, the right‑hand side a[i] is evaluated.
Now i is already 1, so a[i] returns the current value at index 1, which is 1.
Assignment
The statement then does a[1] = 1.
Since a[1] already holds 1, the list is unchanged.

Consequently, printing a outputs the original list: [0, 1].

Why mutate a list?

The following is another implementation of composite_sequence that takes advantage of the mutability of list.

def sieve_composite_sequence(stop):
    is_composite = [False] * stop  # initialization
    for factor in range(2, stop):
        if is_composite[factor]:
            continue
        for multiple in range(factor ** 2, stop, factor):
            is_composite[multiple] = True
    return (x for x in range(4, stop) if is_composite[x])
sieve_code=In[-1].rsplit('\n', maxsplit=1)[0]

for x in sieve_composite_sequence(100):
    print(x, end=" ")

4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 33 34 35 36 38 39 40 42 44 45 46 48 49 50 51 52 54 55 56 57 58 60 62 63 64 65 66 68 69 70 72 74 75 76 77 78 80 81 82 84 85 86 87 88 90 91 92 93 94 95 96 98 99

The algorithm

changes is_composite[x] from False to True if x is a multiple of a smaller number factor, and
returns a generator that generates composite numbers according to is_composite.

%%hermes --no-context
Explain in a paragraph or two why `factor ** 2` is used instead of `factor * 2`
in the following function that attempts to generate a sequence of composite
numbers up to and excluding stop.
---
{sieve_code}

See Also

Why factor ** 2 instead of factor * 2?
In the sieve, each prime factor should cross out only those multiples that have not already been eliminated by a smaller prime. For a prime p, any composite less than p² must have a prime divisor smaller than p—otherwise it would itself be prime. Consequently those lower composites have already been marked in previous iterations, and touching them again would be redundant work. By starting the inner loop at p², the algorithm jumps straight to the first “new” multiple that needs marking, reducing the total assignments to roughly (O(n \log \log n)). If we began at p·2 instead, we would repeatedly re‑mark numbers like 6 (when p=3) or 10 (when p=5), which only increases runtime without affecting correctness. Thus factor ** 2 is the classic optimization that keeps the sieve efficient.

# A sample if you did not define composite_sequence before.
def composite_sequence(stop):
    return (x for x in range(2, stop) if \
            any(x % d == 0 for d in range(2, isqrt(x) + 1)))

%%timeit
for x in composite_sequence(10000): pass

%%timeit
for x in sieve_composite_sequence(10000): pass

for x in sieve_composite_sequence(10000000): pass

Solution to Exercise 10

The line if is_composite[factor]: continue avoids the redundant computations of checking composite factors.

%%pytutor
a = [[0] * 2] * 2
a[0][0] = a[1][1] = 1
print(a)

### BEGIN SOLUTION
a = [[0] * 2 for i in range(2)]
### END SOLUTION
a[0][0] = a[1][1] = 1
print(a)

[[1, 0], [0, 1]]

%%hermes --no-context
Explain the different levels of copy for Python lists.

↻ Session: main (ACP: cbd08506-750…)

See Also

Copying Python Lists

A list in Python is an object that holds references to other objects.
When you “copy” a list you can choose how many levels of those references you want to duplicate.

Copy Level	What it does	Typical syntax	When to use
No copy (assignment)	Creates a new reference to the *same list object. No new list is built.	`b = a`	When you just want an alias that points to the original.
Shallow copy	Creates a new list, but the elements are shallowly referenced: each element still points to the same objects as in the original.	`b = a[:]`
`b = list(a)`
`b = a.copy()`
`from copy import copy; b = copy(a)`	When you want a separate list container but are OK with shared elements (immutable or you don’t care about mutating them).
Deep copy	Recursively copies the list and all nested objects they reference, producing a fully independent object graph.	`from copy import deepcopy; b = deepcopy(a)`	When the list contains mutable objects (e.g., sub‑lists, dictionaries) and you want total isolation between the copies.

Assignment – Flat Alias

a = [1, 2, 3]
b = a          # b is just another name for a
b.append(4)    # modifies the same list
print(a)       # [1, 2, 3, 4]

No new object is created; the reference count of a is simply increased.

Shallow Copy – New Top‑Level List

Using slicing

a = [1, 2, [3, 4]]
b = a[:]          # or: b = list(a)

Using .copy() (Python 3.3+)

b = a.copy()

Using copy.copy()

from copy import copy
b = copy(a)

All of the above produce a new list object b whose elements are the same references that a holds.

b[2].append(5)    # changes the sub‑list inside both a and b
print(a)  # [1, 2, [3, 4, 5]]
print(b)  # [1, 2, [3, 4, 5]]

Key point: The outermost container is new; the contained objects are not copied.

Deep Copy – Completely Independent

from copy import deepcopy
c = deepcopy(a)   # recursively copies nested containers

Now c shares no objects with a:

c[2].append(6)
print(a)  # [1, 2, [3, 4, 5]]      (unchanged)
print(c)  # [1, 2, [3, 4, 5, 6]]

deepcopy performs a recursive traversal of the object graph, copying every mutable object it encounters.
It also respects custom copy semantics via the _deepcopy_registry for user‑defined types.

Practical Considerations

Scenario	Preferred copy method	Reason
Quick list clone for immutable items (e.g., numbers, strings)	Shallow copy (`[:]`)	Fast; originals are safe because immutable.
Need to edit one copy without affecting the other when the list contains mutable sub‑lists	Deep copy (`deepcopy`)	Prevent accidental sharing of nested objects.
You just want another variable pointing to the list	Assignment	Zero overhead.
You’re working with very large lists and only care about the top‑level container	Shallow copy	Minimal extra memory.

Assignment: same object ‑ no copy.
Shallow copy ([:], list(), .copy(), copy.copy()) : new list, shared elements.
Deep copy (deepcopy) : new list and new copies of all nested objects.

Choose the level that matches how independently you need your copies to behave.

Methods¶

There is also a built-in function sorted for sorting a sequence:

sorted?
sorted(seq)

[1, 4, 4, 19, 38, 40, 47, 58, 60, 93]

Signature: sorted(iterable, /, *, key=None, reverse=False)
Docstring:
Return a new list containing all items from the iterable in ascending order.

A custom key function can be supplied to customize the sort order, and the
reverse flag can be set to request the result in descending order.
Type:      builtin_function_or_method

Is quicksort quicker?

%%timeit
quicksort(seq)

5.98 μs ± 35.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%%timeit
sorted(seq)

204 ns ± 1.52 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Python has used the Timsort algorithm (a hybrid of merge sort and insertion sort) since Python 2.3.

Timsort explained

What are other operations on sequences?

The following compares the lists of public attributes for tuple and list.

We determine membership using the operator in or not in.
Different from the keyword in in a for loop, operator in calls the method __contains__.

list_attributes = dir(list)
tuple_attributes = dir(tuple)

print(
    'Common attributes:', ', '.join([
        attr for attr in list_attributes
        if attr in tuple_attributes and attr[0] != '_'
    ]))

print(
    'Tuple-specific attributes:', ', '.join([
        attr for attr in tuple_attributes
        if attr not in list_attributes and attr[0] != '_'
    ]))

print(
    'List-specific attributes:', ', '.join([
        attr for attr in list_attributes
        if attr not in tuple_attributes and attr[0] != '_'
    ]))

Common attributes: count, index
Tuple-specific attributes: 
List-specific attributes: append, clear, copy, extend, insert, pop, remove, reverse, sort

There are no public tuple-specific attributes, and
all the list-specific attributes are methods that mutate the list, except copy.

The common attributes

count method returns the number of occurrences of a value in a tuple/list, and
index method returns the index of the first occurrence of a value in a tuple/list.

%%pytutor
a = (1,2,2,4,5)
count_of_2 = a.count(2)
index_of_1st_2 = a.index(2)

reverse method reverses the list instead of returning a reversed list.

%%pytutor
a = [*range(10)]
print(reversed(a))
print(*reversed(a))
print(a.reverse())

copy method returns a shallow copy of a list.
tuple does not have the copy method but it is easy to create a copy by slicing.

%%pytutor
a = [*range(10)]
b = tuple(a)
a_reversed = a.copy()
a_reversed.reverse()
b_reversed = b[::-1]

sort method sorts the list in place instead of returning a sorted list.

%%pytutor
import random
a = [random.randint(0,10) for i in range(10)]
print(sorted(a))
print(a.sort())

extend method that extends a list instead of creating a new concatenated list.
append method adds an object to the end of a list.
insert method insert an object to a specified location.

%%pytutor
a = b = [*range(5)]
print(a + b)
print(a.extend(b))
print(a.append('stop'))
print(a.insert(0,'start'))

pop method deletes and returns the last item of the list.
remove method removes the first occurrence of a value in the list.
clear method clears the entire list.

We can also use the function del to delete a selection of a list.

%%pytutor
a = [*range(10)]
del a[::2]
print(a.pop())
print(a.remove(5))
print(a.clear())

Footnotes¶

If $n$ is small (fewer than 100), the unbiased sample variance should be used.
↩
If $n$ is small, the factor 2 needs to be increased by looking up the $t$ -value from the student’s $t$ -distribution.
↩