Homework: Homework 2. Program Reasoning

Assigned

• February 3, 2026

Due

• February 6, 2026 10:00pm

Collaboration

You must work individually this assignment. Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone.

Submitting

You will submit your compiled pdf on Gradescope. Everything must be typed in \(\Latex\)

Homework exercises are your opportunity to showcase your mastery of the week’s material. In lab, you gain practice employing the fundamental skills we introduce in class. In contrast, the homeworks are integrative in nature, requiring to put those skills into context as well as mix different skills together to solve problems that are more like the ones you find in the real world.

Formatting and Submitting Your Work

Create a LaTeX document for each demonstration exercise, using the csc208_template.tex template file to format your document. Your write-ups for each problem should reflect good writing principles and mathematical style:

• Grammatically correct English prose and mathematics.
• Structure of the prose made obvious through subheadings, paragraphs, and lists.
• Math appropriately integrated into the prose as needed.

To achieve this, you will need to set aside ample time for revision and editing of your work before the deadline. Approach the demonstration exercises not like a one-and-done problem set, but as a writing assignment where you are putting in work that you eventually refine into a polished, complete product.

When you are done, you should compile your LaTeX file to a PDF and then submit that PDF to Gradescope when you are done. Please do not submit your LaTeX source (in textual or PDF format); we would like to only work with a complete, rendered document!

Problem 1: Tracing

Consider the following Python program mystery that performs a more complicated recursive computation:

def mystery(l):
    if len(l) == 0:
        return []
    elif len(l) == 1:
        return l
    else:
        x = head(l)
        y = head(tail(l))
        t = tail(tail(l))
        return cons(y, cons(x, mystery(t)))

1. Give the step-by-step evaluation of the following expressions. In your work, whenever you need to write down a conditional statement, you can elide the branches of the conditional with ellipses. In other words, instead of:

   if len(l) == 0:
       return []
   elif len(l) == 1:
       return l
   else:
       x = head(l)
       y = head(tail(l))
       t = tail(tail(l))
       return cons(y, cons(x, mystery(t)))
   

   You should write instead:

   if len(l) == 0: ...
   

   • mystery([])
   • mystery(0, 1)
   • mystery("a", "b", "c", "d")

   When giving your evaluation traces, please use a verbatim block, placing each step of the derivation on its own line, separated by a long arrow (-->), e.g.,

   \begin{verbatim}
       1 + 2 * 3
   --> 1 + 6
   --> 7
   \end{verbatim}
   

2. In a sentence, describe what the mystery function does.

Problem 2: Blasting Booleans

Consider the following Python functions over booleans that give implementations of the standard boolean operations not, and, and or:

def my_not(b):
    if b:
        return False
    else:
        return True

def my_and(b1, b2):
    if b1:
        return b2
    else:
        return False

def my_or(b1, b2):
    if b1:
        return True
    else:
        return b2

Prove the following claims of program equivalence about these definitions:

~~~ admonish question title=”Claim 1” my_not(my_and(True, False)) ≡ True.

~~~ admonish question title="Claim 2"
There exists a boolean `b1` such that for all booleans `b2`, `my_or(b1, b2)` ≡ `True`.

~~~ admonish question title=”Claim 3 (Negation is an Involution)” For any boolean b, my_not(my_not b) ≡ b.

~~~ admonish question title="Claim 4 (De Morgan's Law)"
For any pair of booleans `b1` and `b2`, `my_not(my_and(b1, b2))` ≡ `my_or(my_not(b1), my_not(b2))`.

Make sure not to skip any steps in your derivations!