CSC148 Course Notes

Last updated November 19, 2023

See Quercus for the readings assigned each week. You will eventually be responsible for all readings listed here, unless we clearly indicate otherwise.

1. Recapping and Extending Some Key Prerequisite Material

• 1.1 The Python Memory Model: Introduction
• 1.2 The Python Memory Model: Functions and Parameters
• 1.3 The Function Design Recipe
• 1.4 Preconditions
• 1.5 Python Type Annotations

2. Testing Your Code

• 2.1 Testing Your Work
• 2.2 Choosing Test Cases
• 2.3 Code Coverage
• 2.4 Introduction to Property-Based Testing

3. Object-Oriented Programming

• 3.1 Introduction to Object-Oriented Programming
• 3.2 Representation Invariants
• 3.3 The Class Design Recipe
• 3.4 More on Designing Classes
• 3.5 Inheritance: Introduction and Methods
• 3.6 Inheritance: Attributes and Initializers
• 3.7 Inheritance: Tracing Initialization
• 3.8 Inheritance: Thoughts on Design
• 3.9 The object Class and Python Special Methods

4. Abstract Data Types

• 4.1 Introduction to Abstract Data Types
• 4.2 Stacks and Queues
• 4.3 Exceptions
• 4.4 Analysing Program Running Time

5. Exceptions

• 5.1 Introduction to Exceptions
• 5.2 General Rules for try-except
• 5.3 Why Not Just Return a Special Value?
• 5.4 Additional Clauses

6. Linked Lists

• 6.1 Introduction to Linked Lists
• 6.2 Traversing Linked Lists
• 6.3 Linked List Mutation
• 6.4 Linked Lists and Running Time

7. Recursion

• 7.1 Motivation: Adding Up Numbers
• 7.2 Nested Lists: A Recursive Data Structure
• 7.3 Understanding Recursive Functions: Partial Tracing
• 7.4 Writing Recursive Functions: Using the Recursive Structure of the Problem
• 7.5 Writing Recursive Functions: Using a Set of Test Scenarios
• 7.6 How Recursive Code Can Fail
• 7.7 Recursion and the call stack
• 7.8 Branching recursion

8. Trees and Binary Search Trees

• 8.1 Introduction to Trees
• 8.2 A Tree Implementation
• 8.3 Mutating Trees
• 8.4 Introduction to Binary Search Trees
• 8.5 Binary Search Tree Implementation and Search
• 8.6 Mutating Binary Search Trees
• 8.7 Tree Traversals
• 8.8 Binary Search Trees and Running Time
• 8.9 Expression Trees

9. Recursive Sorting Algorithms

• 9.1 Recursive Sorting Algorithms
• 9.2 Efficiency of Recursive Sorting Algorithms