📚 The Way of the Program

Definition: The way of the program is the mindset that combines mathematical formalism,
engineering design, and scientific experimentation to solve problems with computers.

Problem solving is the core skill: formulate the problem, devise creative solutions, and
express them clearly.
Learning to program provides a concrete arena for practicing these skills.

🐍 Python as a Teaching Language

High‑level language: abstracts away machine details, letting students focus on ideas.
Interpreted: immediate feedback; no separate compilation step.
Rich standard library (web, graphics, etc.) enables interesting projects early.
Supports procedural abstraction, data structures, object‑oriented programming, and
even functional concepts.
Syntax is clean and concise, reducing “low‑level” distractions (e.g., no #include, void main(),
semicolons).

Why Python?
Fun, productive, and easy to start – students can write “neat things” right away.
Portable across Linux, Windows, macOS.
Free and open‑source; aligns with the GNU Free Documentation License.

⚙️ High‑Level vs Low‑Level Languages

Aspect High‑Level Language (e.g., Low‑Level Language (e.g.,
Python) Assembly)
Abstraction High – hides hardware details Low – direct hardware
manipulation
Portability Runs on many platforms with Usually tied to a specific
little change architecture
Development Speed Faster; shorter, more readable Slower; verbose, error‑prone
code
Execution Needs interpreter or compiler Executes directly on CPU
translation
Typical Use General‑purpose applications, Specialized
teaching performance‑critical code

🔁 Interpreters vs. Compilers

 Feature Interpreter Compiler
Operation Reads source line‑by‑line, Translates entire source to
executes immediately object code before execution
Speed of Development Immediate feedback; ideal for Longer edit‑compile cycle
learning
Runtime Overhead Interprets each statement at No overhead after compilation
run time
Portability Same source runs on any Need separate binaries per
platform with the interpreter target platform
Python Interpreted language – uses (Can be compiled to bytecode
Python interpreter internally, but still an
interpreter)

Quote: “A compiler translates a program once, producing an executable that can run repeatedly
without further translation. An interpreter reads and executes the program incrementally.”

💻 Running Python Programs

1. Command‑line mode – type statements interactively.

$ python
>>> print 1 + 1
2

2. Script mode – write code in a file (*.py) and run it.

# file: [Link]
print(1 + 1)

Execute:

$ python [Link]
2

Files that contain Python code conventionally end with .py.

🖥️ “Hello, World!” – The First Program
C++ version (requires many details):

#include <iostream.h>
void main() {
cout << "Hello, world." << endl;
}

Python version (minimal, no boilerplate):

print("Hello, World!")

Observation: The Python example eliminates 13 paragraphs of C++ syntax explanation, letting
students focus on the concept of a program statement.

📦 Variables: Conceptual Shift

C++ view: Variable = named memory location; requires type declaration.
Python view: Variable = name that refers to an object; no explicit type needed.

Quote: “In Python a variable is a name that refers to a thing,” mirroring the mathematical notion of
a variable.

🔧 Functions – Simple Syntax

Definition keyword: def
Call: just type the function name with arguments.

def add(a, b):

return a + b

result = add(3, 4) # result is 7

No return types, parameter types, or reference/value distinctions.

📊 Summary Tables
Comparison: Python vs. C++ for Beginners
 Feature Python C++
Syntax complexity Minimal; easy to read Verbose; many keywords
(#include, void, ;)
Setup No compilation; run directly Requires compilation, linking
Learning curve Low; immediate results Steeper; low‑level details can
intimidate
Standard library Large, ready‑to‑use modules Smaller, more fragmented
Teaching focus Concepts first, details later Often forced to cover low‑level
details early

🛠️ Practical Tips for New Learners

Start with the interpreter to experiment interactively.
Write short scripts (.py files) and run them frequently.
Use meaningful variable names; Python’s dynamic typing lets you focus on what the
variable represents, not how it’s stored.
When defining functions, think of def as “declare” and the function name as the action
you’ll perform later.

End of notes for the introductory portion of “How to Think Like a Computer Scientist.”## 🖥️ What Is a
Program?

A program is a sequence of instructions that specifies how to perform a computation.

The basic instruction types that appear in almost every language are:
Instruction Description
Input Get data from keyboard, file, or other device
Output Display data on screen or write to a file/device
Math Perform arithmetic (e.g., addition, multiplication)
Conditional execution Execute a block only if a condition holds
Repetition Perform an action repeatedly (loops)
Programming = breaking a large task into smaller subtasks that can be expressed with these primitives.

🐞 Debugging
 Debugging is the process of finding and fixing errors (bugs) in a program.

Three error categories:

Error type When it appears Typical cause
Syntax error Before execution (while Violates language grammar
parsing)
Runtime error (exception) During execution Invalid operation (e.g., division
by zero)
Semantic error Executes without error Logic is wrong – program does
messages something else

🕵️‍♂️ Experimental Debugging

1. Observe the wrong output (clues).
2. Form a hypothesis about the cause.
3. Modify the code and test.
4. If the hypothesis was right, the result matches expectation; otherwise, repeat.

📚 Formal vs. Natural Languages

Formal languages are designed by people for specific purposes (e.g., mathematics, chemistry,
programming).

Key differences:
Aspect Natural Language Formal Language
Ambiguity Common, resolved by context Designed to be (nearly)
unambiguous
Redundancy High (verbose) Low (concise)
Literalness Uses idiom, metaphor Means exactly what it says
Parsing Done subconsciously Explicit parsing required

Parsing

Parsing is analyzing a sentence (or program) to determine its syntactic structure.

👋 The First Program
print("Hello, World!")

print is a print statement – it displays the value on the screen.

Quotation marks delimit the string literal; they are not printed.

📖 Glossary (selected terms)

Term Definition
program Set of instructions that specifies a computation
algorithm General process for solving a class of problems
bug An error in a program
debugging Finding and removing bugs
syntax Structural rules of a language
runtime error Error occurring during execution
semantic error Logic error; program runs but gives wrong result
keyword Reserved word that cannot be used as an
identifier
operator Symbol representing a computation (e.g., +, *)
operand Value that an operator acts upon
expression Combination of values, variables, and operators
that yields a single result
statement An executable instruction (e.g., assignment,
print)
comment Text ignored by the interpreter, starts with #

🔢 Values, Types, and Variables

Values are the basic data (e.g., 2, "Hello").
Types determine how a value can be used:
int – integers (2)
float – floating‑point numbers (3.2)
str – strings ("Hello")
 >>> type("Hello, World!")
<class 'str'>
>>> type(17)
<class 'int'>
>>> type(3.2)
<class 'float'>

Variable Assignment

message = "What’s up, Doc?"

n = 17
pi = 3.14159

The variable name appears on the left, the value on the right.
Variable names must start with a letter, may contain letters, digits, and underscores (_).
Keywords (e.g., class, def, if) cannot be used as variable names.
Illegal example Reason
76trombones = "big parade" Starts with a digit
more$ = 1000000 Contains illegal $ character
class = "CS 101" class is a keyword

🧩 Statements
Statement type Effect
Print Displays a value (print(message))
Assignment Binds a name to a value (x = 5)
Multiple statements in a script execute sequentially, producing output as each statement finishes.

➗ Operators and Operands

Operator Meaning Example
+ Addition / string concatenation 2+3→5
- Subtraction 5-2→3
* Multiplication / string 4 * 2 → 8; "Fun"*3 → FunFunFun
repetition
 / Integer division if both 59 / 60 → 0
operands are int (result
truncated)
// Explicit integer division (same 59 // 60 → 0
as / for ints)
** Exponentiation 5**2 → 25
% Modulus (remainder) 7%3→1

Order of Operations (PEMDAS)

1. Parentheses ()
2. Exponentiation **
3. Multiplication * and Division / (left‑to‑right)
4. Addition + and Subtraction - (left‑to‑right)
Parentheses can be used to override precedence or improve readability.

📚 Operations on Strings
+ → concatenation
* → repetition (string × integer)

fruit = "banana"
bakedGood = " nut bread"
print(fruit + bakedGood) # banana nut bread
print("Fun"*3) # FunFunFun

Illegal operations (e.g., message - 1, "Hello"/123) raise a semantic error.

🧱 Composition
Expressions can be nested inside other statements:

print(17 + 3) # prints 20
print("Minutes:", hour*60+minute) # combines arithmetic with print
percentage = (minute * 100) / 60 # expression on RHS of assignment

Left‑hand side of an assignment must be a variable name, not an expression.

💬 Comments
# compute the percentage of the hour that has elapsed
percentage = (minute * 100) / 60 # caution: integer division

Everything from # to end‑of‑line is ignored by Python.

Use comments to explain why the code does something, not what it does.

📞 Functions
3.1 Function Calls

>>> type("32")
<class 'str'>
>>> betty = type("32")
>>> print(betty)
<class 'str'>

Syntax: function_name(argument).
The argument is the value supplied; the return value is what the function produces.

3.2 Type Conversion

Function Purpose
int(x) Convert to integer (truncates floats)
float(x) Convert to floating‑point
str(x) Convert to string

>>> int("32")
32
>>> int(3.999)
3
>>> float("3.14159")
3.14159
>>> str(32)
'32'

3.3 Type Coercion (Automatic)

If either operand of +, -, *, / is a float, the other is coerced to float.

>>> minute = 59
>>> minute / 60.0
0.983333333333

3.4 Math Functions (module math)

import math
decibel = math.log10(17.0)
angle = 1.5
height = [Link](angle)

Use dot notation: [Link].

Common functions: sin, cos, tan, log, log10, sqrt, exp.
Constant [Link] is available.

3.5 Defining New Functions

def newLine():
print()

def threeLines():
newLine()
newLine()
newLine()

Syntax: def NAME(PARAMETER_LIST): followed by an indented block.

Empty parentheses → no parameters.
Indentation (two spaces in these notes) defines the function body.

3.6 Flow of Execution

Execution starts at the first top‑level statement.
Function definitions are executed (they create the function object) but do not run the
body.
When a function is called, execution jumps to its body, runs it, then returns to the point of
call.

3.7 Parameters & Arguments

def printTwice(bruce):
print(bruce, bruce)
 printTwice('Spam') # Spam Spam
printTwice(5) # 5 5

Parameter names are local to the function; they need not match the argument variable
names.

3.8 Local Variables

Variables created inside a function exist only within that function’s frame.

def catTwice(part1, part2):

cat = part1 + part2
printTwice(cat)

# 'cat' is destroyed after catTwice finishes.

3.9 Stack Diagrams

A stack diagram visualizes frames (function calls) and the variables they contain.

__main__
chant1 -> "Pie Jesu domine,"
chant2 -> "Dona eis requiem."
catTwice
part1 -> "Pie Jesu domine,"
part2 -> "Dona eis requiem."
cat -> "Pie Jesu domine, Dona eis requiem."
printTwice
bruce -> "Pie Jesu domine, Dona eis requiem."

The top of the stack is the currently executing function.

3.10 Recursion
A function may call itself.

def countdown(n):
if n == 0:
print("Blastoff!")
else:
print(n)
countdown(n-1)
 Base case – condition that stops further recursive calls (n == 0).
Recursive case – calls the same function with a simpler argument (n-1).
Infinite recursion occurs when no base case is reachable, leading to a RuntimeError: maximum
recursion depth exceeded.

🔀 Conditionals
4.1 Modulus Operator

>>> remainder = 7 % 3
>>> print(remainder)
1

Useful for divisibility checks (x % y == 0) and extracting digits (x % 10).

4.2 Boolean Expressions

Operator Meaning
== Equality
!= Inequality
> Greater than
< Less than
>= Greater than or equal
<= Less than or equal
Result is True or False.

4.3 Logical Operators

Operator Description
and Both operands must be true
or At least one operand true
not Negates a boolean expression
Non‑zero numbers are treated as True; zero is False.

4.4 if Statements
 if x > 0:
print("x is positive")

Header ends with :; body is indented.

Use pass for an empty body.

4.5 Alternative Execution (if … else)

if x % 2 == 0:
print(x, "is even")
else:
print(x, "is odd")

Exactly one branch executes.

4.6 Chained Conditionals (elif)

if x < y:
print("x < y")
elif x > y:
print("x > y")
else:
print("x == y")

Only the first true condition’s block runs.

4.7 Nested Conditionals

if x == y:
print("equal")
else:
if x < y:
print("x < y")
else:
print("x > y")

Can be simplified with logical operators:

if 0 < x < 10:

print("x is a positive single digit")
4.8 return Statement

def printLogarithm(x):
if x <= 0:
print("Positive numbers only, please.")
return
result = [Link](x)
print("log =", result)

return ends the function early; optional value after return becomes the function’s result.

4.9 Recursion (revisited)

def nLines(n):
if n > 0:
print()
nLines(n-1)

Each call creates a new frame; base case (n == 0) stops recursion.

4.10 Keyboard Input

name = raw_input("What is your name? ")

print(name)

raw_input returns a string.

For numeric input, use raw_input + conversion (int(), float()).

📦 Additional Glossary (selected)

Term Definition
modulus operator (%) Returns the remainder after integer division
boolean expression Evaluates to True or False
comparison operator One of ==, !=, >, <, >=, <=
logical operator and, or, not
conditional statement Controls flow based on a boolean condition
compound statement Header + indented body (e.g., if, def)
 nesting Placing one structure inside another
recursion Function calls itself
base case Non‑recursive terminating condition
infinite recursion No base case; leads to RuntimeError
prompt Message displayed to the user before input

🎯 Key Takeaways
1. Programs consist of basic instructions (input, output, math, condition, repetition).
2. Debugging follows a systematic, experimental approach.
3. Formal languages require precise syntax and semantics; parsing is essential.
4. Variables bind names to values of specific types; naming rules avoid keywords.
5. Expressions obey operator precedence (PEMDAS) and can be composed.
6. Functions enable reuse, modularity, and recursion; they may return values.
7. Conditionals (if, elif, else) control execution flow; logical operators simplify complex tests.
8. Recursion must have a clear base case to avoid infinite loops.
9. User input is obtained via raw_input; always convert to the desired type.
These notes can be combined with other sections to build a complete study guide for introductory
🟢
Python programming.## Boolean Functions
Boolean functions return True or False, useful for hiding complex tests.
Example (concise form):

def isDivisible(x, y):

return x % y == 0

Use directly in conditionals:

if isDivisible(x, y):
print("x is divisible by y")
else:
print("x is not divisible by y")

Tip: Avoid if isDivisible(x, y) == True; the extra comparison is unnecessary.

🔁 Recursion
Recursion expresses a definition that references itself.
Factorial (n!) definition:
 n Definition
0 $\mathbb{1}$
$n>0$ $n \times (n-1)!$
Python implementation (step‑by‑step):

def factorial(n):
if n == 0:
return 1
else:
recurse = factorial(n-1)
result = n * recurse
return result

Leap of Faith: When encountering a recursive call, assume the call works correctly and
focus on how the current call combines that result.

📈 Fibonacci
Mathematical definition:
n Formula
0 $\mathbb{1}$
1 $\mathbb{1}$
$n\ge 2$ $F(n-1) + F(n-2)$
Python version (uses leap of faith):

def fibonacci(n):
if n == 0 or n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)

🛡️ Type Checking for Factorial

def factorial(n):
if not isinstance(n, int):
print("Factorial is only defined for integers.")
return -1
 elif n < 0:
print("Factorial is only defined for positive integers.")
return -1
elif n == 0:
return 1
else:
return n * factorial(n-1)

Guardians (first two if statements) protect the recursive logic from invalid inputs.

📚 Glossary – Fruitful Function

Fruitful function: A function that returns a value (i.e., has a return value).

Other terms:
Temporary variable: Holds intermediate results.
Dead code: Never executed (e.g., after a return).
None: Default return value when no return is given.
Incremental development: Build and test small pieces step‑by‑step.
Guardian: Input‑validation checks that protect the core algorithm.

🔄 Iteration
Repeating tasks without errors → use loops (while, for).

🔁 While Loop
def countdown(n):
while n > 0:
print(n)
n = n - 1
print("Blastoff!")

Flow:
1. Evaluate condition.
2. If false → exit loop.
3. If true → execute body, then return to step 1.

📋 Generating Tables
 x = 1.0
while x < 10.0:
print(x, '\t', [Link](x))
x = x + 1.0

Use \t for column alignment.

Logarithm base‑e; for base‑2 use [Link](x)/[Link](2.0).

📐 Two‑Dimensional Tables (Multiplication Table)

def printMultiples(n):
i = 1
while i <= 6:
print(n*i, '\t', i)
i = i + 1

def printMultTable():
i = 1
while i <= 6:
printMultiples(i)
i = i + 1

Extending to a square table of size high:

def printMultiples(n, high):

i = 1
while i <= high:
print(n*i, '\t', i)
i = i + 1

def printMultTable(high):
i = 1
while i <= high:
printMultiples(i, high)
i = i + 1

🧩 Encapsulation & Generalization

Encapsulation: Wrap code in a function to reuse and debug in isolation.
Generalization: Replace constants with parameters (e.g., printMultiples(n) instead of
hard‑coding 2).
🏠 Local Variables
Variables defined inside a function are local; they do not interfere with same‑named
variables in other functions.
Example call stack diagram (conceptual): each function call has its own i and n.

📦 Functions Overview
Naming convention: use descriptive, often yes/no style for booleans (isDivisible).
Benefits:
1. Improves readability.
2. Enables modular debugging.
3. Supports recursion and iteration.
4. Promotes code reuse.

🧵 Strings – Compound Data Type

Strings are sequences of characters; each character can be accessed via an index (s[0] is
the first character).
Indexing starts at 0; negative indices count from the end (s[-1] is the last character).

Length

len(s) # number of characters

last = s[-1] # last character

Traversal (while vs. for)

# while version
index = 0
while index < len(fruit):
print(fruit[index])
index = index + 1

# for version (preferred)

for char in fruit:
print(char)

String Slices
 s = "Peter, Paul, and Mary"
print(s[0:5]) # 'Peter'
print(s[7:11]) # 'Paul'
print(s[17:21]) # 'Mary'

Omit start → start at 0; omit end → go to end; s[:] copies the whole string.

Comparison

if word == "banana":
...
if word < "banana":
...

Uppercase letters sort before lowercase; convert to a common case ([Link]()) for
case‑insensitive comparison.

Immutability
Strings cannot be changed in place:

greeting = "Hello"
# greeting[0] = 'J' # TypeError
newGreeting = 'J' + greeting[1:]

Find Function

def find(st, ch):

index = 0
while index < len(st):
if st[index] == ch:
return index
index = index + 1
return -1

Returns index of ch or -1 if not found.

Counting Characters

def countLetters(s, target):

count = 0
for char in s:
 if char == target:
count += 1
return count

String Module Highlights

import string
index = [Link]("banana", "a") # = 1
lowercase = [Link] # all lowercase letters
uppercase = [Link]
digits = [Link]
whitespace = [Link]

[Link] also supports substrings and range arguments.

Character Classification

def isLower(ch):
return ch in [Link] # or: return 'a' <= ch <= 'z'

📚 Lists
Created with brackets: mylist = [1, 2, 3] or via range().
Access: mylist[0], supports negative indices.

Length & Traversal

for i in range(len(mylist)):
print(mylist[i])
# or simply
for item in mylist:
print(item)

Membership

if 'apple' in fruits: # True/False

...

List Operations
 Operator Meaning
+ Concatenate two lists
* Repeat list N times

a = [1,2,3] + [4,5] # [1,2,3,4,5]

b = [0] * 4 # [0,0,0,0]

Slices

lst = ['a','b','c','d','e','f']
print(lst[1:3]) # ['b','c']
print(lst[:4]) # ['a','b','c','d']
print(lst[3:]) # ['d','e','f']

Mutability

fruits = ["banana", "apple"]

fruits[0] = "pear"

Use slice assignment to replace multiple elements or delete them:

lst[1:3] = ['x','y'] # replace

lst[1:3] = [] # delete
lst[1:1] = ['b','c'] # insert

Deletion (del)

del a[1] # remove element at index 1

del a[1:5] # remove a slice

Objects & Values

Variables reference objects; id(obj) returns a unique identifier.
Two variables can refer to the same object (aliasing) or separate objects with equal values.
Aliasing & Cloning
 a = [1,2,3]
b = a # alias; changes affect both
c = a[:] # clone; independent copy

List Parameters
Passing a list to a function passes a reference (alias), not a copy.

def deleteHead(lst):
del lst[0]

numbers = [1,2,3]
deleteHead(numbers) # numbers becomes [2,3]

Nested Lists & Matrices

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

elem = matrix[1][2] # 6 (row 2, column 3)

Split & Join (string module)

import string
words = [Link]("The rain in Spain...")
joined = [Link](words) # 'The rain in Spain...'
joined_underscore = [Link](words, '_') # 'The_rain_in_Spain...'

🧩 Tuples
Immutable ordered collections, defined with commas (parentheses optional).

t = (1, 2, 3)
single = ('a',) # note trailing comma

Tuple Assignment (swap without temp)

a, b = b, a
Returning Tuples

def swap(x, y):

return y, x

a, b = swap(a, b)

Caution: A function that attempts x, y = y, x inside does not affect the caller’s variables
(semantic error).

Random Numbers

import random
x = [Link]() # float in [0.0, 1.0)

Scale to a range: x * high.

Generate integer in [low, high]:

rand_int = [Link](low, high)

Histograms (single‑pass bucket counting)

def histogram(values, numBuckets):

buckets = [0] * numBuckets
for v in values:
index = int(v * numBuckets) # floor to bucket index
buckets[index] += 1
return buckets

📖 Glossaries (selected)
Compound data type: A type whose values consist of multiple components (e.g., strings, lists,
tuples).

Mutable vs. Immutable:

Mutable objects (lists) allow element modification.

Immutable objects (strings, tuples) do not.
 Alias: Multiple variables referencing the same object.

Clone: Creating a new object with the same value (new = old[:] for lists).

Guardians: Input‑validation checks placed at the start of a function.

Leap of Faith: Assuming a recursive call works correctly to reason about the surrounding code.

Histogram: List of counts representing how many values fall into each bucket. ## 📦 Compound
Types

Mutable: list, dictionary

Immutable: string, tuple

🔢 Tuples
“A sequence type similar to a list but immutable.”

Used as keys in dictionaries because they are immutable.

Tuple assignment swaps values in one statement (parallel assignment).

📚 Dictionaries
“A collection of key‑value pairs that maps immutable keys to any values.”

Created with {} or with a literal of key‑value pairs.

Keys are called keys, values are values, and each pair is a key‑value pair.

📖 Dictionary Operations
Operation Syntax Effect
Create empty eng2sp = {} New empty dictionary
Add/Update eng2sp['one'] = 'uno' Insert or change entry
Delete del inventory['pears'] Remove entry
Length len(dict) Number of key‑value pairs
Access dict[key] Retrieve value (KeyError if
missing)

🛠️ Dictionary Methods
 Method Call Returns
keys [Link]() List of keys
values [Link]() List of values
items [Link]() List of (key, value) tuples
has_key d.has_key(k) True/False (key present)
get [Link](k, default) Value or default if missing

🔁 Aliasing and Copying

Aliasing: alias = original → both names reference the same object.
Copy: copy = [Link]() creates a shallow copy (new dict, same values).

🗂️ Sparse Matrices
List‑of‑lists stores many zeros.
Dictionary representation stores only non‑zero entries:

matrix = {(0, 3): 1, (2, 1): 2, (4, 3): 3}

Access with tuple key: matrix[0, 3] → 1.

Use get to return a default for missing entries:

[Link]((1, 3), 0) # returns 0

🔢 Hints & Fibonacci

Hint: Store already computed values to avoid recomputation.
Memoized Fibonacci using a dictionary:

previous = {0: 1, 1: 1}
def fibonacci(n):
if previous.has_key(n):
return previous[n]
new = fibonacci(n-1) + fibonacci(n-2)
previous[n] = new
return new

🔢 Long Integers
 Python automatically promotes to long when an integer overflows.
Create explicitly with 1L or long():

type(1L) # <type 'long'>

long(57) # 57L

Operations on longs behave like normal integers; overflow yields a long.

📊 Counting Letters (Histograms)

Build a histogram using a dictionary:

letterCounts = {}
for letter in "Mississippi":
letterCounts[letter] = [Link](letter, 0) + 1
# Result: {'M':1, 'i':4, 's':4, 'p':2}

Sort for alphabetical display:

items = [Link]()
[Link]()
print(items) # [('M', 1), ('i', 4), ('p', 2), ('s', 4)]

📂 Files
📖 Opening, Reading, Writing
f = open("[Link]", "w") # write mode, creates or truncates file
[Link]("Now is the time")
[Link]()

f = open("[Link]", "r") # read mode

text = [Link]() # reads whole file
[Link]()

read(n) reads up to n characters; returns empty string at EOF.

readline() returns a line including the newline.
readlines() returns a list of remaining lines.

🔁 Copying Files (Chunked)

 def copyFile(oldFile, newFile):
f1 = open(oldFile, "r")
f2 = open(newFile, "w")
while True:
text = [Link](50)
if text == "":
break
[Link](text)
[Link]()
[Link]()

🗂️ Directories
Specify full path: open("/usr/share/dict/words", "r").
/ is a directory separator, not part of a filename.

🥒 Pickling (Serialization)
import pickle
f = open("[Link]", "wb")
[Link](12.3, f)
[Link]([1, 2, 3], f)
[Link]()

f = open("[Link]", "rb")
x = [Link](f) # 12.3 (float)
y = [Link](f) # [1, 2, 3] (list)
[Link]()

⚠️ Exceptions
Exception Cause
ZeroDivisionError Division by zero
IndexError Invalid list index
KeyError Missing dict key
IOError File operation failure
Handle with try/except:

try:
f = open(filename, "r")
 except IOError:
print("No such file:", filename)

Raise custom exceptions:

def inputNumber():
x = input("Pick a number: ")
if x == 17:
raise ValueError, "17 is a bad number"
return x

🏗️ Classes and Objects

📍 Point Class
class Point:
pass

p = Point()
p.x = 3.0
p.y = 4.0

Attributes accessed via dot notation.

📏 Rectangle Class (composition)

class Rectangle:
pass

box = Rectangle()
[Link] = 100.0
[Link] = 200.0
[Link] = Point()
[Link].x = 0.0
[Link].y = 0.0

🔁 Instances as Arguments
def printPoint(p):
print('(' + str(p.x) + ', ' + str(p.y) + ')')
🤝 Sameness (Equality)
== compares references (shallow equality).
Deep equality requires explicit comparison:

def samePoint(p1, p2):

return p1.x == p2.x and p1.y == p2.y

📋 Copying Objects
Method Result Notes
[Link](obj) Shallow copy Copies top‑level container,
shares nested objects
[Link](obj) Deep copy Recursively copies all
embedded objects

import copy
p2 = [Link](p1) # independent copy

⏰ Time Class
class Time:
def __init__(self, hours=0, minutes=0, seconds=0):
[Link] = hours
[Link] = minutes
[Link] = seconds

🕒 Pure Functions vs Modifiers

Pure: addTime(t1, t2) returns a new Time without altering inputs.
Modifier: increment(time, secs) changes the passed time object.
Pure addition (base‑60 conversion)

def convertToSeconds(t):
return ([Link] * 60 + [Link]) * 60 + [Link]

def makeTime(seconds):
time = Time()
[Link] = seconds // 3600
[Link] = (seconds % 3600) // 60
 [Link] = seconds % 60
return time

def addTime(t1, t2):

return makeTime(convertToSeconds(t1) + convertToSeconds(t2))

📈 Algorithmic Insight
Treat a Time as a base‑60 number:
$\text{total seconds}=3600\cdot h + 60\cdot m + s$
Conversion to/from seconds simplifies arithmetic and avoids manual carries.

🧩 Operator Overloading & Polymorphism

Overloading in Point

class Point:
def __add__(self, other):
return Point(self.x + other.x, self.y + other.y)

def __sub__(self, other):

return Point(self.x - other.x, self.y - other.y)

def __mul__(self, other): # dot product

return self.x * other.x + self.y * other.y

def __rmul__(self, scalar): # scalar multiplication

return Point(scalar * self.x, scalar * self.y)

def __str__(self):
return '(' + str(self.x) + ', ' + str(self.y) + ')'

Enables expressions like p1 + p2, 2 * p2, p1 * p2.

Polymorphic Function Example

def multadd(x, y, z):

return x * y + z # works for numbers, Points, etc.

Works with any types supporting * and +.

🃏 Card Objects
 class Card:
suitList = ["Clubs", "Diamonds", "Hearts", "Spades"]
rankList = ["narf", "Ace", "2", "3", "4", "5", "6", "7",
"8", "9", "10", "Jack", "Queen", "King"]

def __init__(self, suit=0, rank=2):

[Link] = suit
[Link] = rank

def __str__(self):
return [Link][[Link]] + " of " + [Link][[Link]]

Class attributes (suitList, rankList) are shared by all instances.

__str__ provides a readable string representation, e.g., print(Card(3,1)) → Ace of Spades.

Key Takeaways
Use mutable types for data that changes; immutable types for stable keys.
Dictionaries provide fast key‑based lookup; remember they are unordered.
When dealing with large, sparse data, prefer a dictionary keyed by coordinates.
Memoization (hints) dramatically improves recursive algorithm performance.
Python automatically handles integer overflow via long integers.
File I/O follows the open‑read/write‑close pattern; pickle preserves object types.
Understand aliasing vs copying to avoid unintended side effects.
Design classes with __init__ and __str__; overload operators for natural syntax.
Polymorphic functions work on any type that satisfies the required operations.## Card 🎴
Class
Attributes
suit – integer (0‑3) representing Clubs, Diamonds, Hearts, Spades.
rank – integer (1‑13) where 1 = Ace, 11 = Jack, 12 = Queen, 13 = King.
Class attribute suitList – shared list of suit names
(["Clubs","Diamonds","Hearts","Spades"]).
Class attribute rankList – includes a placeholder "narf" at index 0 so that ranks
map directly (1 → 1, 2 → 2, …).
Behavior
__str__ (or print) uses [Link] to index suitList and [Link] to index rankList.
Modifying a class attribute (e.g., [Link][1] = "Swirly Whales") changes the
value for all Card instances.
 Definition: Class attribute – a variable defined inside a class definition but outside any method; it
is shared by every instance of the class.

Comparison (__cmp__)
Return value Meaning
1 self is greater than other
-1 self is less than other
0 objects are equal

def __cmp__(self, other):

# suit has priority
if [Link] > [Link]: return 1
if [Link] < [Link]: return -1
# suits equal → compare rank
if [Link] > [Link]: return 1
if [Link] < [Link]: return -1
return 0

Exercise: modify __cmp__ so Aces rank higher than Kings (e.g., treat rank 1 as 14).

📦 Deck Class
Structure – [Link] is a list that stores 52 Card objects.
Initialization

class Deck:
def __init__(self):
[Link] = []
for suit in range(4):
for rank in range(1, 14):
[Link](Card(suit, rank))

Printing
printDeck traverses [Link] and prints each card.
__str__ builds a cascade string where each card is indented one more space than
the previous.

def __str__(self):
s = ""
for i in range(len([Link])):
 s += " " * i + str([Link][i]) + "\n"
return s

Shuffling – Fisher‑Yates style using [Link].

import random
def shuffle(self):
n = len([Link])
for i in range(n):
j = [Link](i, n) # i ≤ j < n
[Link][i], [Link][j] = [Link][j], [Link][i]

Definition: Shuffle – random permutation of a collection such that each possible ordering is equally
likely.

Removing / Dealing
removeCard(card) – returns True if card was present, False otherwise.
popCard() – removes and returns the last element ([Link]()).
isEmpty() – len([Link]) == 0.

🙌 Hand (Inheritance from Deck)

Purpose – represents a player's hand; inherits all Deck methods and adds hand‑specific
behavior.
Constructor

class Hand(Deck):
def __init__(self, name=""):
[Link] = [] # override Deck's cards list
[Link] = name

Additional method

def addCard(self, card):

[Link](card)

Custom __str__ (overrides Deck.__str__)

def __str__(self):
header = f"Hand {[Link]}"
if [Link]():
 return header + " is empty\n"
else:
return header + " contains\n" + Deck.__str__(self)

Definition: Inheritance – a class (child) acquires attributes and methods from another class
(parent), allowing code reuse and extension.

🃏 Old Maid Game (Multiple Classes)

OldMaidHand (inherits Hand)
Method removeMatches – removes pairs of matching rank and opposite color.

def removeMatches(self):
count = 0
original = [Link][:]
for card in original:
match = Card(3 - [Link], [Link]) # opposite color
if match in [Link]:
[Link](card)
[Link](match)
print(f"Hand {[Link]}: {card} matches {match}")
count += 1
return count

Uses a copy of the list to avoid modifying the list while iterating.

OldMaidGame (inherits CardGame)

Key steps in play
1. Remove the Queen of Clubs (Card(0,12)).
2. Create an OldMaidHand for each player name.
3. Deal the entire deck ([Link]([Link])).
4. Discard initial matches (removeAllMatches).
5. Loop round‑robin, letting each player pick a neighbor’s top card, add it, attempt matches,
shuffle the hand, and count matches.
6. Stop when 25 matches (i.e., 50 cards) have been made; the remaining card is the “Old
Maid”.
Helper methods
removeAllMatches – sums removeMatches across all hands.
findNeighbor(i) – returns the next non‑empty hand clockwise.
playOneTurn(i) – executes a single player’s turn, returns number of matches
made.
 Glossary
Old Maid: a card‑matching game where the last unmatched card determines the loser.
Neighbor: the next player to the left who still has cards.

🔗 Linked Lists
Node class

class Node:
def __init__(self, cargo=None, next=None):
[Link] = cargo
[Link] = next
def __str__(self):
return str([Link])

cargo holds data; next points to the next Node or None.

Traversal Example

def printList(node):
while node:
print(node)
node = [Link]

Recursive Backward Print

def printBackward(lst):
if lst is None: return
head = lst
tail = [Link]
printBackward(tail)
print([Link], end=' ')

Definition: Recursive data structure – a structure defined in terms of itself (e.g., a list is either
empty or a node pointing to another list).

LinkedList wrapper
Attributes: head (first node) and length.
 Provides methods such as addFirst(cargo) and printBackward() (wrapper) that delegate to
[Link]() (helper).

class LinkedList:
def __init__(self):
[Link] = None
[Link] = 0
def addFirst(self, cargo):
node = Node(cargo)
[Link] = [Link]
[Link] = node
[Link] += 1
def printBackward(self):
print("[", end=' ')
if [Link]:
[Link]()
print("]")

Invariant: [Link] must always equal the actual number of nodes reachable from
[Link].

📚 Stack ADT (Abstract Data Type)

Interface
init()
push(item)
pop()
isEmpty()
Python list veneer

class Stack:
def __init__(self):
[Link] = []
def push(self, item):
[Link](item)
def pop(self):
return [Link]()
def isEmpty(self):
return [Link] == []

Usage example (postfix evaluation)

 def evalPostfix(expr):
import re
tokens = [Link]("([^0-9])", expr)
stack = Stack()
for t in tokens:
if t in ('', ' '): continue
if t == '+':
[Link]([Link]() + [Link]())
elif t == '*':
[Link]([Link]() * [Link]())
else:
[Link](int(t))
return [Link]()

Evaluates "56 47 + 2 *" → $\mathbb{206}$.

Definition: Postfix (Reverse Polish) notation – operators appear after their operands, enabling
stack‑based evaluation without parentheses.

📥 Queue ADT & Implementations

Core operations
Operation Meaning
init() create empty queue
insert(item) add to the back
remove() remove from the front
isEmpty() test emptiness

Linked Queue (basic)

class Queue:
def __init__(self):
[Link] = 0
[Link] = None
def isEmpty(self):
return [Link] == 0
def insert(self, cargo):
node = Node(cargo)
if [Link] is None:
[Link] = node
 else:
last = [Link]
while [Link]:
last = [Link]
[Link] = node
[Link] += 1
def remove(self):
cargo = [Link]
[Link] = [Link]
[Link] -= 1
return cargo

Complexity: insert = O(n) (linear), remove = O(1) (constant).

Improved Queue (constant‑time insert)

class ImprovedQueue:
def __init__(self):
[Link] = 0
[Link] = None
[Link] = None
def isEmpty(self):
return [Link] == 0
def insert(self, cargo):
node = Node(cargo)
if [Link] == 0:
[Link] = [Link] = node
else:
[Link] = node
[Link] = node
[Link] += 1
def remove(self):
cargo = [Link]
[Link] = [Link]
[Link] -= 1
if [Link] == 0:
[Link] = None
return cargo

Complexity: Both insert and remove are O(1).

Priority Queue (list‑based)

class PriorityQueue:
def __init__(self):
[Link] = []
 def isEmpty(self):
return [Link] == []
def insert(self, item):
[Link](item)
def remove(self):
# find index of maximal item
maxi = 0
for i in range(1, len([Link])):
if [Link][i] > [Link][maxi]:
maxi = i
item = [Link][maxi]
del [Link][maxi] # remove it
return item

Complexity: insert = O(1), remove = O(n) (linear scan for max).

Custom priority example – Golfer

class Golfer:
def __init__(self, name, score):
[Link] = name
[Link] = score
def __str__(self):
return "%-16s: %d" % ([Link], [Link])
def __cmp__(self, other):
if [Link] < [Link]: # lower score = higher priority
return 1
if [Link] > [Link]:
return -1
return 0

Inserting Golfer objects into PriorityQueue yields removal in ascending score order (best
golfer first).

🌳 Binary Trees
Node definition

class Tree:
def __init__(self, cargo, left=None, right=None):
[Link] = cargo
[Link] = left
[Link] = right
def __str__(self):
return str([Link])
 Recursive traversal examples
Traversal Order (Root‑Left‑Right) Sample code
Preorder Root, then left subtree, then print([Link]);
right subtree printTree([Link]);
printTree([Link])
Inorder Left, Root, Right printTreeInorder([Link]);
print([Link]);
printTreeInorder([Link])
Postorder Left, Right, Root printTreePostorder([Link]);
printTreePostorder([Link]);
print([Link])
Expression tree – internal nodes hold operators (+, *), leaves hold operands.

expr = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))

Printing in different notations

Preorder → prefix (Polish) notation: + 1 * 2 3
Inorder → infix (needs parentheses for unambiguity)
Postorder → postfix (Reverse Polish): 1 2 3 * +
Indented visualisation

def printTreeIndented(tree, level=0):

if tree is None: return
printTreeIndented([Link], level+1)
print(' '*level + str([Link]))
printTreeIndented([Link], level+1)

Result for the sample tree (sideways view):

3
*
2
+
1

📖 Glossary Highlights (selected)

Term Meaning
 class attribute Variable defined in a class body, shared by all
instances.
inheritance Mechanism allowing a new class to acquire
methods/attributes from an existing class.
wrapper Method that calls a helper to simplify the public
interface.
helper Internal method used by a wrapper; not
intended for direct external calls.
invariant Property that should hold true for an object
throughout its lifetime (except transiently during
updates).
precondition Requirement that must be satisfied before a
method is invoked.
ADT (Abstract Data Type) Specification of operations and their semantics
without prescribing an implementation.
postfix (RPN) Operator follows its operands; evaluates
naturally with a stack.
FIFO “First‑In, First‑Out” queueing policy.
priority queue Queue where removal selects the
highest‑priority element, not necessarily the
earliest inserted.
binary tree Each node has up to two children (left, right).
expression tree Tree representation of an arithmetic expression,
enabling conversion among infix, prefix, and
postfix forms.
---## 🧮 Expression Tree Parser
Key Functions
Function Purpose Important Details
getProduct(tokenList) Parses a product (single Returns a Tree node; recursive
number or * chain). version handles arbitrarily long
products.
getSum(tokenList) Parses a sum (product or + Builds a tree with + at the root;
chain). left child is a product, right
child is another sum.
getNumber(tokenList) Returns a leaf node for a Detects '(' → calls getSum →
number or a parenthesized expects matching ')'. Raises
 sub‑expression. ValueError if a closing
parenthesis is missing.

Building a Product Tree

def getProduct(tokenList):
a = getNumber(tokenList)
if getToken(tokenList, '*'):
b = getProduct(tokenList) # recursive call for long chains
return Tree('*', a, b)
else:
return a

Treats a single operand as a product (useful for uniform parsing).

Example: [2, '*', 3, '*', 5, '*', 7, 'end'] → post‑order output 2 3 5 7 * * *.

Building a Sum Tree

def getSum(tokenList):
a = getProduct(tokenList)
if getToken(tokenList, '+'):
b = getSum(tokenList) # recursive right side
return Tree('+', a, b)
else:
return a

Any expression without parentheses can be represented as a sum of products.

Handling Parentheses

def getNumber(tokenList):
if getToken(tokenList, '('):
x = getSum(tokenList) # parse sub‑expression
if not getToken(tokenList, ')'):
raise ValueError('missing parenthesis')
return x
else:
x = tokenList[0]
if not isinstance(x, int):
return None
tokenList[0:1] = [] # consume token
return Tree(x, None, None)
 Guarantees that addition inside parentheses is performed before surrounding
multiplication.

🐾 Animal Knowledge Tree

Purpose: Interactive program that learns a binary decision tree for guessing animals.

Core Algorithm (simplified)

1. Start with a singleton root containing a generic animal (e.g., "bird").
2. Loop:
a. Ask “Are you thinking of an animal?” – exit if no.
b. Traverse the tree:
At each internal node, ask the stored question.
Move right for yes, left for no.
c. When a leaf is reached, make a guess.
d. If the guess is wrong:
Prompt for the new animal’s name.
Prompt for a distinguishing question.
Replace the leaf’s cargo with the new question and attach two
children: the old guess and the new animal (order depends on the
answer for the new animal).

def animal():
root = Tree("bird") # initial knowledge
while True:
if not yes("Are you thinking of an animal? "):
break
tree = root
while [Link]() is not None:
prompt = [Link]() + "? "
tree = [Link]() if yes(prompt) else [Link]()
guess = [Link]()
if yes("Is it a " + guess + "? "):
print("I rule!")
continue
# learn new animal
animal_name = raw_input("What is the animal’s name? ")
question = raw_input("What question would distinguish a %s from a %s? " %
(animal_name, guess))
[Link](question)
if yes("If the animal were %s the answer would be? " % animal_name):
[Link](Tree(guess))
[Link](Tree(animal_name))
else:
[Link](Tree(animal_name))
[Link](Tree(guess))
Helper

def yes(ques):
from string import lower
ans = lower(raw_input(ques))
return [Link]('y')

Note: The program loses its knowledge when it exits; persisting the tree to a file is a common
extension exercise.

🐞 Debugging Errors
Definition: Debugging is the process of locating, diagnosing, and fixing defects in software.

Error Categories
Category Typical Symptoms Common Strategies
Syntax errors SyntaxError: invalid syntax Check colons, indentation,
during compilation matching quotes/brackets,
correct use of == vs =.
Runtime errors Exceptions (e.g., NameError, Use print statements to trace
TypeError, IndexError) while execution; examine traceback;
program runs add assertions.
Semantic errors Program runs but produces Verify algorithm logic; step
wrong results through with a debugger; write
unit tests for components.

Common Runtime Exceptions & Quick Fixes

Exception Typical Cause Quick Fix
NameError Variable not defined in current Ensure proper variable
scope declaration; avoid using locals
outside their function.
TypeError Wrong operand type (e.g., Use isinstance checks; convert
adding int to list) types as needed.
KeyError Missing dictionary key Use .get() with default or check
key in dict.
 AttributeError Accessing nonexistent Verify object type; correct
attribute/method attribute name.
IndexError Index out of range Print length and index before
access; validate bounds.
ValueError (custom) Logical error such as missing Raise with informative
parenthesis message; catch at higher level
if recoverable.

Debugging Techniques
1. Print‑statement tracing – add messages before/after loops, function entry, and before
critical operations.
2. Infinite loop detection – print loop‑condition values each iteration.
3. Infinite recursion detection – ensure a base case exists; print parameters on each call to
see progress toward the base case.
4. Flow of execution tracing – print "entering <function>" at the start of each function.

🧪 Fraction Data Type

Goal: Create a user‑defined numeric type that behaves like built‑in numbers.

Class Skeleton

class Fraction:
def __init__(self, numerator, denominator=1):
g = gcd(numerator, denominator)
[Link] = numerator // g
[Link] = denominator // g

Reduction is performed automatically using Euclid’s algorithm for the GCD.

Euclid’s GCD Algorithm

def gcd(m, n):

if m % n == 0:
return n
else:
return gcd(n, m % n)

Operator Overloading
 Operator Method Description
* (multiplication) __mul__(self, other) Multiply numerators and
denominators; supports integer
left operand via __rmul__ =
__mul__.
+ (addition) __add__(self, other) Cross‑multiply and add;
supports integer right operand
via __radd__ = __add__.
Comparison __cmp__(self, other) Returns sign of (a*d - b*c)
where self = a/b, other = c/d.
(Future) -, /, ** __sub__, __div__, __pow__ Implement via
negation/inversion or by
converting to common
denominator.

Multiplication Example

def __mul__(self, other):

if isinstance(other, int):
other = Fraction(other)
return Fraction([Link] * [Link],
[Link] * [Link])

__rmul__ = __mul__

Addition Example

def __add__(self, other):

if isinstance(other, int):
other = Fraction(other)
num = [Link] * [Link] + [Link] * [Link]
den = [Link] * [Link]
return Fraction(num, den)

__radd__ = __add__

Comparison Example

def __cmp__(self, other):

diff = [Link] * [Link] - [Link] * [Link]
return diff
Usage Highlights

>>> Fraction(5,6) * Fraction(3,4)

15/24
>>> 4 * Fraction(5,6)
20/6
>>> Fraction(5,6) + 3
23/6
>>> 2 + Fraction(5,6)
17/6

📖 Glossary (Selected Terms)

Term Definition
binary tree Tree where each node has zero, one, or two
children.
leaf Node with no children.
root Topmost node, has no parent.
parent / child Direct predecessor / successor nodes in a tree.
binary operator Operator that takes two operands (e.g., +, *).
subexpression Parenthesized expression treated as a single
operand.
preorder / inorder / postorder Tree traversal orders: root‑first, left‑root‑right,
children‑first respectively.
GCD (greatest common divisor) Largest integer dividing both numerator and
denominator; used to reduce fractions.
operator overloading Providing special methods (__add__, __mul__, …)
so custom objects work with Python’s operators.
base case Termination condition for a recursive function.
exception raising raise ValueError, 'msg' creates an exception that
can be caught by callers.
semantic error Program runs without crashing but produces
incorrect results.
infinite loop / recursion Loop or recursive call that never reaches a
termination condition.
📚 Additional Highlights
Parsing Strategy – By defining product and sum recursively, any expression without explicit
parentheses can be parsed into a binary tree where * has higher precedence than +.
Error‑Handling Extension – After adding parenthesis support, getNumber should raise a
ValueError for missing closing parentheses; similar checks can be added for unexpected
tokens.
Animal Tree Persistence – A simple way to save the learned tree is to serialize it with
pickle or write a custom text representation (preorder list of cargo and child markers).
Debugging Advice – Reduce the problem size, isolate failing components, and keep test
cases minimal to locate bugs efficiently.