Introduction to Programming (Python)

Question 1 (20)

(a) (6)

from math import factorial
 
def sin_taylor(x, n):
    if n == 0:            # base case
        return 0.0
    k = n - 1             # this term's index
    term = (-1)**k * x**(2*k+1) / factorial(2*k+1)
    return term + sin_taylor(x, n - 1)   # recursive case

• Base case n == 0 → returns 0.0 (empty sum). (2)
• Recursive case adds the (n-1)-th term to sin_taylor(x, n-1). (2)
• Each call adds a stack frame; Python's default recursion limit (~1000). Large n exceeds the limit → RecursionError (stack overflow). (2)

(b) (6)

from math import radians
 
v0, g = 30, 9.81
data = [
    (deg, v0**2 * sin_taylor(radians(2*deg), 10) / g)
    for deg in range(10, 81, 10)
]

• Correct comprehension structure [expr for deg in range(...)]. (2)
• radians conversion inside and doubling angle 2*deg. (2)
• Correct range range(10,81,10) → 10..80. (2)

Approx ranges (m): 10°≈31.4, 20°≈59.0, 30°≈79.4, 40°≈90.4, 50°≈90.4, 60°≈79.4, 70°≈59.0, 80°≈31.4.

(c) (8)

best = max(data, key=lambda t: t[1])
# best -> (40, ~90.4) or (50, ...) depending; both ~90.4

• max(..., key=lambda t: t[1]) picks max range. (2)
• Analytic proof: $R=\frac{v_0^2\sin 2\theta}{g}$ is maximized when $\sin 2\theta$ is max, i.e. $2\theta=90°\Rightarrow\theta=45°$. Since $\sin$ peaks at $90°$. (3)
• Discrepancy: the discrete list only samples multiples of 10°; 45° isn't sampled. 40° and 50° are symmetric about 45° ($\sin 80°=\sin 100°$) so both give ≈90.4 m — the winner is whichever max encounters, and neither is the true optimum. Discretization error, not algorithm error. (3)

Question 2 (22)

(a) (6)

def word_freq(text):
    for ch in ".,!?;":
        text = text.replace(ch, "")
    words = text.lower().split()
    freq = {}
    for w in words:
        freq[w] = freq.get(w, 0) + 1
    return freq

• Lowercase + punctuation removal + split. (2)
• Accumulation with get. (2)
• get(key,0) returns default 0 for unseen keys; bare dict[key] raises KeyError on first occurrence, forcing an if key in dict guard. get is safer/shorter. (2)

(b) (6)

def top3(text):
    freq = word_freq(text)
    ordered = sorted(freq.items(), key=lambda kv: (-kv[1], kv[0]))
    return ordered[:3]

• sorted with lambda key. (2)
• Tie-break: (-count, word) → descending count, ascending word. (2)
• Slice top 3. (2) (A dict comprehension may filter/reshape; sorted list of tuples is the required return type.)

(c) (10)

• LEGB: name resolution order Local → Enclosing → Global → Built-in. In bump, the statement count = count + 1 assigns to count, so Python marks count as a local variable of bump for the whole function. On the RHS it reads that local count before assignment → UnboundLocalError. The enclosing count is never consulted for read because the local binding shadows it. (4)

Fix 1 — nonlocal:

def make_counter():
    count = 0
    def bump():
        nonlocal count
        count = count + 1
        return count
    return bump

(2)

Fix 2 — mutable container (mutate, don't rebind):

def make_counter():
    count = [0]
    def bump():
        count[0] = count[0] + 1
        return count[0]
    return bump

(2)

• Trade-off: nonlocal is clearer and directly expresses intent but needs Python 3; the list/dict trick works even without nonlocal (worked in Py2 closures) but obscures intent with indexing. (2)

Question 3 (18)

(a) (7)

• Proof: Let the lowest set bit of $n$ be at position $j$, so $n = \dots1\underbrace{00\ldots0}_{j}$. Subtracting 1 flips that bit to 0 and all $j$ trailing zeros to 1: $n-1 = \dots0\underbrace{11\ldots1}_{j}$. AND-ing keeps the higher bits unchanged and zeroes out position $j$ and below → lowest set bit cleared. (4)

def popcount(n):
    c = 0
    while n:
        n &= n - 1
        c += 1
    return c

• Each iteration removes exactly one set bit, so the loop runs exactly (number of set bits) times. (3)

(b) (5)

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

• Condition: a power of two has exactly one set bit; n & (n-1) clears that bit → 0. Must also guard n > 0 (0 gives 0 & -1 == 0 falsely). (3) correct expression, (2) justification.

(c) (6)

• x << k: shifting bits left by $k$ multiplies the place value of every bit by $2^k$, i.e. $x\cdot 2^k$. x >> k: shifting right discards the low $k$ bits = integer division by $2^k$ = $\lfloor x/2^k\rfloor$ for $x\ge 0$. (2)

Hand evaluations (13 = 1101₂, 6 = 0110₂): (4, ~0.7 each)

• 13 << 2 = $13\cdot4 = 52$
• 13 >> 1 = $\lfloor13/2\rfloor = 6$
• 13 & 6 = 1101 & 0110 = 0100 = 4
• 13 | 6 = 1101 | 0110 = 1111 = 15
• 13 ^ 6 = 1101 ^ 0110 = 1011 = 11
• ~13 = $-(13+1)$ = −14 (two's complement ~x = -x-1)

[
  {"claim":"sin_taylor(radians(90),10) ~ 1 so 45deg is analytic max of range", "code":"from sympy import sin,pi,diff,solve,symbols\nth=symbols('theta',real=True)\nR=sin(2*th)\nsol=solve(diff(R,th),th)\nresult = any(s==pi/4 for s in sol)"},
  {"claim":"popcount of 13 (1101) is 3", "code":"def pc(n):\n c=0\n while n:\n  n&=n-1\n  c+=1\n return c\nresult = pc(13)==3"},
  {"claim":"is_power_of_two correct for sample set", "code":"def ip(n):\n return n>0 and (n&(n-1))==0\nresult = [ip(k) for k in [1,2,3,4,16,0,6]]==[True,True,False,True,True,False,False]"},
  {"claim":"bitwise hand evaluations for 13,6", "code":"result = (13<<2==52) and (13>>1==6) and (13&6==4) and (13|6==15) and (13^6==11) and (~13==-14)"}
]