CSC148 Lecture Notes

Diane Horton and David Liu

See the Lectures page on 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 Python Type Annotations
1.5 Testing Your Work
1.6 Choosing Test Cases
1.7 Introduction to Property-based Testing

2. Object-Oriented Programming

2.1 Introduction to Object-Oriented Programming
2.2 Representation Invariants
2.3 Designing Classes
2.4 Inheritance: Introduction and Methods
2.5 Inheritance: Attributes and Initializers
2.6 Inheritance: Thoughts on Design
2.7 The object Class and Python Special Methods

3. Abstract Data Types

3.1 Introduction to Abstract Data Types
3.2 Stacks and Queues
3.3 Exceptions
3.4 Analysing Program Running Time

4. Linked Lists

4.1 Introduction to Linked Lists
4.2 Traversing Linked Lists
4.3 Mutating Linked Lists
4.4 Linked Lists and Running Time

5. Introduction to Recursion

5.1 Motivation: Adding Up Numbers
5.2 Nested Lists: A Recursive Data Structure

6. Trees and Binary Search Trees

6.1 Introduction to Trees
6.2 A Tree Implementation
6.3 Mutating Trees
6.4 Introduction to Binary Search Trees
6.5 Binary Search Tree Implementation and Search
6.6 Mutating Binary Search Trees
6.7 Binary Search Trees and Running Time
6.8 Expression Trees

7. Recursion Wrap-up

7.1 Recursive Sorting Algorithms
7.2 Efficiency of Recursive Sorting Algorithms