Difficulty: Intermediate | Prerequisites: Python data types, functions, loops, conditionals (see Part 1 notes).
This set of notes covers the second half of CS303E's core material: defining your own classes, writing recursive functions, understanding how search and sort algorithms work, and reading from and writing to files. These topics build directly on the data types covered in Part 1. If you are not comfortable with lists, dictionaries, and string methods, review those first. Classes and recursion are among the most heavily tested topics on Exam 3.
Classes let you bundle data and behaviour into reusable objects. Recursion solves problems by having a function call itself with a smaller input until it hits a base case. Linear and binary search find elements in lists (binary requires a sorted list). Selection sort repeatedly picks the smallest unsorted element and swaps it forward. File I/O lets your programs read from and write to text files on disk.
__init__
The constructor method, called automatically whenever a new object of the class is created. Sets up the object's initial state. In simple terms, it is the function that runs when you write MyClass(args).
__str__
A special method that returns a string representation of the object. Called by print() and str(). If not defined, Python uses a default (the class name and memory address), so printing still works; it just produces something unhelpful.
Private attribute
An attribute whose name begins with two underscores (e.g. self.__data). Python name-mangles it so it cannot be accessed directly from outside the class. In simple terms, it is data the class keeps to itself.
Positional argument
An argument passed by position in a function call. In f(2, 5, c=4, d=4), the values 2 and 5 are positional arguments.
Keyword argument
An argument passed by name in a function call. In f(2, 5, c=4, d=4), c=4 and d=4 are keyword arguments.
Base case
The part of a recursive function that returns an answer directly, without making another recursive call. Every recursive function needs at least one base case to stop the recursion.
Recursive case
The part of a recursive function that calls itself with a smaller or simpler input, working towards the base case.
Linear search
Searching a list by checking each element one at a time from the beginning. If the element is not present, the function makes len(L) comparisons.
Binary search
Searching a sorted list by repeatedly halving the search space. Requires the list to be sorted. If the list is unsorted, binary search does not work correctly (it may miss the element entirely).
Selection sort
A sorting technique that repeatedly finds the smallest element in the unsorted portion of the list and swaps it to the front.
None
The value returned implicitly by any function that has no explicit return statement. Also the return value of in-place methods like list.sort() and list.append().
Relative path
A file path that specifies location relative to the current working directory, as opposed to an absolute path which starts from the root of the file system.
Defining a class
A class bundles data (attributes) and behaviour (methods) into a single unit. The __init__ method is called automatically when you create a new object. All instance attributes are set on self.
class Pokemon:
def __init__(self, number, name):
self.number = number
self.name = namePrivate attributes
Attributes beginning with two underscores (e.g. self.__score) are private. Python name-mangles them, so they cannot be accessed with obj.__score from outside the class. Within the class, self.__score is a private variable.
__str__ method
Defines the string representation of your object. print(obj), str(obj), and obj.__str__() all produce the same output. If __str__ is not defined, Python does not raise an error; it uses a default representation.
All three of print(s), print(str(s)), and print(s.__str__()) are valid ways to display an object.
Object comparison (==)
By default, == checks identity (whether two variables point to the same object in memory), not equality of attribute values. So if p1 = Pokemon(7, "Squirtle") and p2 = Pokemon(7, "Squirtle"), then p1 == p2 is False (different objects), but p1.number == p2.number is True and str(p1) == str(p2) is True.
To make == compare values, you would need to define the __eq__ method, which this course may not cover.
Structure of a recursive function
Every recursive function has at least one base case (returns a value directly) and at least one recursive case (calls itself with a smaller input). Any function which calls itself is considered recursive.
Building results recursively
A common pattern is to process the first element of a string or list, recursively handle the rest, and combine the results.
def f(s):
if s == "": # base case
return {}
res = f(s[1:]) # recursive call on the rest
if s[0] not in res:
res[s[0]] = 0
res[s[0]] += 1
return resThis builds a character frequency dictionary. For f("an assassin sins"), it counts every character (including spaces).
Recursive string building
Another common pattern: compare characters at position 0 across multiple strings, pick the best, and concatenate with the recursive result on the remaining characters.
def teamPerformance(str1, str2, str3):
if str1 == "":
return ""
best = min(str1[0], str2[0], str3[0])
return best + teamPerformance(str1[1:], str2[1:], str3[1:])Here min() works because 'A' < 'B' < 'C' < 'D' < 'F' in ASCII order, so the alphabetically smallest letter is the best grade.
Why prefer recursion over iteration?
Recursive functions are often simpler to implement and understand, especially for problems that naturally break into sub-problems (trees, string processing, divide-and-conquer). Recursion is not always more efficient, and modern hardware is not optimised for deep function call stacks.
Linear search
Checks every element from left to right. If the target is not in the list, it makes exactly len(L) comparisons. Works on sorted or unsorted lists.
Binary search
Repeatedly splits the search space in half. Much faster on large sorted lists (roughly log2(n) comparisons). However, it requires the input list to be sorted. If the list is unsorted, binary search does not work correctly; it may report that an element is absent when it is present.
Binary search does not always take fewer comparisons than linear search. For a very short list, or when the target is near the beginning, linear search can find the element in fewer probes.
Selection sort works by scanning the unsorted portion of the list, finding the smallest element, and swapping it to the front. It then moves the boundary one position to the right and repeats.
The exam also tests a variant that looks like an insertion-sort step: given a list and an index j, the code takes the value at j, shifts larger elements to the right, and inserts the value in its correct sorted position.
def f(lst, j):
val = lst[j]
i = j + 1
while (i < len(lst)) and (lst[i] < val):
lst[i - 1] = lst[i]
i += 1
lst[i - 1] = val
return lstFor f([7, 2, 14, 6, 9, 13, 15, 19], 2): val = 14, then elements smaller than 14 at positions 3 onward (6, 9, 13) shift left, and 14 is placed where the shifting stopped. Result: [7, 2, 6, 9, 13, 14, 15, 19].
Opening files
open("file.txt", "w") opens the file for writing. If the file already exists, it is overwritten (not appended to, and no error is raised). Use "a" mode to append instead.
Closing files
You should always close a file when done. Reasons to close:
Good practice to release resources.
Output may be held in a buffer and not written to disk until the file is closed.
Other programs may not be able to access the file while it is open.
The claim that "the file will become corrupted if close is not called" is not a standard reason and would be the odd one out on an exam.
Absolute vs relative paths
An absolute path specifies the full location from the root (e.g. /home/user/data.txt). A relative path specifies location relative to the current working directory (e.g. data.txt or ./data/input.txt).
Reading files and building data structures
A common exam pattern is reading a file line by line, parsing each line (split on : then on ,), and building a dictionary from the data.
def visitorDictionary(filename):
result = {}
f = open(filename)
for line in f:
parts = line.strip().split(":")
name = parts[0].strip()
countries = parts[1].split(",")
for country in countries:
country = country.strip()
if country not in result:
result[country] = set()
result[country].add(name)
f.close()
return resultStudents often think binary search works on unsorted lists. It does not. It may silently return a wrong answer.
Students often think binary search is always faster than linear search. For short lists or targets near the beginning, linear search can win.
Students often think __str__ must be defined or print() will crash. It does not crash; Python uses a default representation.
Students often think p1 == p2 compares attribute values. By default, it checks whether p1 and p2 are the same object in memory.
Students often think open("file.txt", "w") will raise an error if the file exists. It does not; it silently overwrites the file.
⚠️ Know the difference between object identity (== by default) and value equality. Be ready to trace p1 == p2 vs p1.attr == p2.attr vs str(p1) == str(p2).
⚠️ Trace recursive functions step by step. The exam will ask you to determine the output of a recursive function on a specific input.
⚠️ Know that linear search on a missing element uses len(L) comparisons.
⚠️ Binary search requires a sorted list. This is a true/false favourite.
⚠️ open("file.txt", "w") overwrites. "a" appends.
⚠️ Be able to write a visitorDictionary-style function: read a file, parse lines, build a dict of sets.
⚠️ Lists passed to functions are passed by reference. Mutations inside the function affect the original.
True or False: Binary search works correctly on unsorted lists. → False
Fill in the blank: The function called whenever a new object is created is ______. → __init__
True or False: If __str__ is not defined, printing an object raises an error. → False
Fill in the blank: The part of a recursive function that returns a value without a recursive call is the ______. → base case
True or False: open("file.txt", "w") appends to an existing file. → False (it overwrites)
Q: Suppose L is a non-empty list of integers and the element you are searching for is not present. Using linear search, how many comparisons are made?
A: len(L). Linear search checks every element.
Q: Which of the following is a reason to prefer recursion over iteration?
A: Recursive functions are often simpler to implement and understand.
Q: What is the output of the following code?
class Pokemon:
def __init__(self, number, name):
self.number = number
self.name = name
def __str__(self):
return "This is " + self.name + " with Pokedex id " + str(self.number)
p1 = Pokemon(7, "Squirtle")
p2 = Pokemon(7, "Squirtle")
print(p1 == p2, end=" ")
print(p1.number == p2.number, end=" ")
print(str(p1) == str(p2), end=" ")A: False True True
Q: What is the output?
def f(lst):
if lst[-1] > 5:
lst.append(8)
print(lst, end=" ")
nums = [1, 9]
f(nums)
print(nums, end=" ")
f(nums)A: [1, 9, 8] [1, 9, 8] [1, 9, 8, 8]
The first call appends 8 (since 9 > 5), printing [1, 9, 8]. Because lists are mutable, nums is now [1, 9, 8] outside the function too. The second call appends another 8 (since 8 > 5), printing [1, 9, 8, 8].
Q: What does open("file.txt", "w") do if file.txt already exists?
A: It overwrites the file with whatever new content you write. The old contents are lost.
Q: Which is NOT a reason to close a file after writing? (A) File corruption, (B) Release resources, (C) Buffer may not be flushed, (D) Other programs cannot access it.
A: A. File corruption is not a standard reason given in this course.
Classes connect to data types because class attributes are stored as lists, dicts, sets, etc. Understanding mutability is essential for predicting how methods change an object's state. Recursion connects to string and list processing because recursive functions often slice strings or lists one element at a time. Searching and sorting connect to algorithm analysis and understanding why some approaches scale better than others. File I/O connects to dictionaries and sets because reading structured data from a file and organising it into a lookup structure is a standard exam question.
Tags: Python classes, OOP, init, str, private attributes, name mangling, object comparison, recursion, base case, recursive case, linear search, binary search, selection sort, insertion sort, file I/O, open, close, read, write, append, absolute path, relative path, positional argument, keyword argument, None, CS303E, UT Austin, Dr. Bill Young