CSC148H1: data structures, and recursion.
CSC108H1 taught you to write programs. This course teaches you to design them: choose the right structure for the data, hide how it works behind a specification, and solve problems that fold back into themselves.
The real beginning of computer science.
CSC148H1 "Introduction to Computer Science" covers abstract data types and the data structures that implement them, linked data structures, encapsulation and information hiding, object-oriented programming, specifications, analyzing the efficiency of programs, and recursion. It runs 36 lecture hours and 24 practical hours; attendance at practicals is required. It assumes the programming experience from CSC108H1.
The reputation is deserved. The step up from CSC108H1 is real, and recursion is where most people stall. The course allows a move back to CSC108H1 after the add deadline if it turns out to be too much — the calendar says so explicitly, which tells you how common that is.
Chapters
In course order. Each page has the concept, runnable code, the design reasoning behind it, pitfalls, and practice.
- Open →
Abstract data types
Separating what a structure does from how it does it.
- Open →
Object-oriented design
Encapsulation, information hiding, representation invariants.
- Open →
Stacks & queues
Two ADTs, and why the choice changes the answer.
- Open →
Linked lists
Nodes, references, and the cost of pointer surgery.
- Open →
Recursion
Base case, recursive case, and trusting the recursion.
- Open →
Recursion on nested data
Nested lists and the shape of the data driving the code.
- Open →
Trees
General trees, traversals, and recursive structure.
- Open →
Binary search trees
The ordering property and what it buys.
- Open →
Efficiency analysis
Big-O properly, worst case, and comparing structures.
- Open →
Sorting & inheritance
Divide-and-conquer sorts; subclasses and polymorphism.
Textbook Spine
The calendar lists the topics in the order used here. The course normally runs on its own course notes rather than a published textbook. Check Quercus for the current notes, the assignment handouts, and the required docstring and type-annotation style, which is marked.
Units 1-2 cover the calendar's "abstract data types", "encapsulation and information-hiding" and "specifications". This is the conceptual frame: what a client may rely on, and what the implementer stays free to change.
Units 3-4 cover "data structures for implementing them" and "linked data structures". Stacks and queues are the ADTs; linked lists are the first implementation built from scratch rather than borrowed from Python.
Units 5-8 cover "recursion" and the recursive structures it exists to handle. Trees are where recursion stops being a curiosity and becomes the only sensible approach.
Units 9-10 cover "analyzing the efficiency of programs" and finish the object-oriented thread with inheritance. Big-O returns from CSC108H1, now applied to structures you built yourself.
Contract before code
Write the docstring, the type annotations, the preconditions and the examples first. In this course the specification is marked, and writing it first is also the fastest way to get the body right.
Let the recursion work
Assume the recursive call handles the smaller case correctly, then combine. Tracing every level by hand is how people get stuck, not how they get unstuck.
Code mirrors data
If the data is recursive, the code is recursive with the same shape. A tree with subtrees becomes a function calling itself on each subtree.
State the cost
Name the big-O of every operation you write. Choosing between two structures is nearly always a cost comparison.
Practice Plan
CSC148H1 is passed by writing code, not by reading it. The unit pages give exercises; use this course-level mix to build exam readiness.
Base case first
For every recursive function, write the base case before anything else. Missing or wrong base cases cause most infinite recursions.
Draw the structure
Sketch nodes and arrows before writing linked-list or tree code. Reference bugs are almost impossible to see in code and obvious in a diagram.
Test the edges
Empty structure, one element, and the deepest nesting you can manage. These break more code than any typical case.
Write the invariant down
State what must always be true of your representation, then check every method preserves it. This is how subtle bugs get caught before they run.
Course-wide challenge bank
These mix recursion, structure choice and analysis in the way the final exam does.
You must process items in the order they arrive, and separately undo the most recent action. Which ADT for each?
Solution sketch
Write a function counting all integers in an arbitrarily nested list.
Solution sketch
def count_ints(obj) -> int:
"""Return the number of integers in obj, a nested list of ints.
>>> count_ints([1, [2, [3, 4]], 5])
5
"""
if isinstance(obj, int):
return 1
return sum(count_ints(item) for item in obj)Inserting at the front: Python list or linked list?
Solution sketch
Binary search tree lookup is often called $O(\log n)$. When is it not?
Solution sketch
Resources
CSC148H1 — official calendar listing
Department of Computer Science — undergraduate
The calendar confirms the CSC148H1 topic list and the 36L/24P hours. The course normally uses its own notes rather than a published textbook; verify the current notes, assignment specifications and required code style against Quercus each year.