\( \newcommand{\NOT}{\neg} \newcommand{\AND}{\wedge} \newcommand{\OR}{\vee} \newcommand{\XOR}{\oplus} \newcommand{\IMP}{\Rightarrow} \newcommand{\IFF}{\Leftrightarrow} \newcommand{\TRUE}{\text{True}\xspace} \newcommand{\FALSE}{\text{False}\xspace} \newcommand{\IN}{\,{\in}\,} \newcommand{\NOTIN}{\,{\notin}\,} \newcommand{\TO}{\rightarrow} \newcommand{\DIV}{\mid} \newcommand{\NDIV}{\nmid} \newcommand{\MOD}[1]{\pmod{#1}} \newcommand{\MODS}[1]{\ (\text{mod}\ #1)} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\cA}{\mathcal A} \newcommand{\cB}{\mathcal B} \newcommand{\cC}{\mathcal C} \newcommand{\cD}{\mathcal D} \newcommand{\cE}{\mathcal E} \newcommand{\cF}{\mathcal F} \newcommand{\cG}{\mathcal G} \newcommand{\cH}{\mathcal H} \newcommand{\cI}{\mathcal I} \newcommand{\cJ}{\mathcal J} \newcommand{\cL}{\mathcal L} \newcommand{\cK}{\mathcal K} \newcommand{\cN}{\mathcal N} \newcommand{\cO}{\mathcal O} \newcommand{\cP}{\mathcal P} \newcommand{\cQ}{\mathcal Q} \newcommand{\cS}{\mathcal S} \newcommand{\cT}{\mathcal T} \newcommand{\cV}{\mathcal V} \newcommand{\cW}{\mathcal W} \newcommand{\cZ}{\mathcal Z} \newcommand{\emp}{\emptyset} \newcommand{\bs}{\backslash} \newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor} \newcommand{\ceil}[1]{\left \lceil #1 \right \rceil} \newcommand{\abs}[1]{\left | #1 \right |} \newcommand{\xspace}{} \newcommand{\proofheader}[1]{\underline{\textbf{#1}}} \)

Foundations of Computer Science

Course Notes for CSC110 and CSC111

David Liu and Mario Badr

CSC110/CSC111 logo artwork

1. Working with Data

1.1 Introducing the Python Programming Language
1.2 Using the Python Console
1.3 Representing Data I: Numbers
1.4 Representing Data II: Booleans and Strings
1.5 Representing Data III: Collections
1.6 Storing Data in Variables
1.7 Building Up Data with Comprehensions
1.8 Application: Representing Colour

2. Functions

2.1 Python’s Built-In Functions
2.2 Defining Our Own Functions
2.3 Local Variables and Function Scope
2.4 Methods: Functions Belonging to a Data Type
2.5 Importing Python Modules
2.6 Type Conversion Functions
2.7 The Function Design Recipe
2.8 Testing Functions I: doctest and pytest
2.9 Application: Representing Text

3. Formal Logic in Computer Science

3.1 Propositional Logic
3.2 Predicate Logic
3.3 Filtering Collections
3.4 If Statements: Conditional Code Execution
3.5 Simplifying If Statements
3.6 The Main Block: if __name__ == '__main__'
3.7 Logical Statements with Multiple Quantifiers

4. Function Specification and Correctness

4.1 Specifying What a Function Should Do
4.2 Type Annotations Revisited
4.3 Checking Function Specifications with python_ta
4.4 Testing Functions II: hypothesis
4.5 Justifying Correctness (Beyond Using Test Cases)
4.6 Proofs and Programming I: Divisibility
4.7 Proofs and Programming II: Prime Numbers
4.8 Application: Linear Regression

5. Working with Complex Data

5.1 Tabular Data
5.2 Defining Our Own Data Types, Part 1
5.3 Defining Our Own Data Types, Part 2
5.4 Repeated Execution: For Loops
5.5 For Loop Variations
5.6 Index-Based For loops
5.7 Nested For Loops
5.8 PythonTA and Accumulation Tables

6. Modifying Values and Variables

6.1 Variable Reassignment, Revisited
6.2 Objects and Object Mutation
6.3 Mutable Data Types
6.4 The Full Python Memory Model: Introduction
6.5 Aliasing and “Mutation at a Distance”
6.6 The Full Python Memory Model: Function Calls
6.7 Testing Functions III: Testing Mutation

7. Number Theory: Theorems, Proofs, and Algorithms

7.1 Introduction to Number Theory
7.2 Greatest Common Divisor
7.3 Proofs and Algorithms III: Computing the Greatest Common Divisor
7.4 Modular Arithmetic
7.5 Modular Exponentiation and Order

8. Case Study: Cryptography

8.1 Introduction to Cryptography
8.2 The One-Time Pad and Perfect Secrecy
8.3 Computing Shared Secret Keys
8.4 The RSA Cryptosystem
8.5 Implementing RSA in Python
8.6 Application: Securing Online Communications

9. Analyzing Algorithm Running Time

9.1 Introduction to Running Time Analysis
9.2 Comparing Asymptotic Function Growth: Big-O Notation
9.3 Big-O, Omega, Theta
9.4 Asymptotic Growth and Limits
9.5 Analyzing Algorithm Running Time
9.6 Analyzing Comprehensions and While Loops
9.7 Analyzing Built-In Data Type Operations
9.8 Worst-Case Running Time Analysis
9.9 Testing Functions IV: Efficiency

10. Abstraction, Classes, and Software Design

10.1 An Introduction to Abstraction
10.2 Defining Our Own Data Types, Part 3
10.3 Defining Our Own Methods
10.4 Data Types, Abstract and Concrete
10.5 Stacks
10.6 Exceptions as a Part of the Public Interface
10.7 Queues
10.8 Priority Queues
10.9 Defining a Shared Public Interface with Inheritance
10.10 The object Superclass

11. Case Study: Building a Simulation

11.1 The Problem Domain: Food Delivery Networks
11.2 Object-Oriented Modelling
11.3 A “Manager” Class
11.4 Food Delivery Events
11.5 Creating a Discrete-Event Simulation

12. Interlude: Nifty Python Features

12.1 Sequences Revisited: Ranges, Indexing, and Slicing
12.2 String Interpolation with f-strings
12.3 Functions with Optional Parameters

13. Linked Lists

13.1 Introduction to Linked Lists
13.2 Traversing Linked Lists
13.3 Mutating Linked Lists
13.4 Index-Based Mutation
13.5 Linked List Running-Time Analysis

14. Induction and Recursion

14.1 Proof by Induction
14.2 Recursively-Defined Functions
14.3 Introduction to Nested Lists
14.4 Nested Lists and Structural Recursion
14.5 Recursive Lists
14.6 Application: Fractals

15. Trees

15.1 Introduction to Trees
15.2 Recursion on Trees
15.3 Mutating Trees
15.4 Running-Time Analysis for Tree Operations
15.5 Introduction to Binary Search Trees
15.6 Mutating Binary Search Trees
15.7 The Running Time of Binary Search Tree Operations

16. Case Study: Abstract Syntax Trees

16.1 Introduction to Abstract Syntax Trees
16.2 Variables and the Variable Environment
16.3 From Expressions to Statements
16.4 Abstract Syntax Trees in Practice

17. Graphs

17.1 Introduction to Graphs
17.2 Some Properties of Graphs
17.3 Representing Graphs in Python
17.4 Connectivity and Recursive Graph Traversal
17.5 A Limit for Connectedness
17.6 Cycles and Trees
17.7 Computing Spanning Trees
17.8 Application: Control Flow Graphs

18. Sorting

18.1 Sorting Lists and Binary Search
18.2 Selection Sort
18.3 Insertion Sort
18.4 Introduction to Divide-and-Conquer Algorithms
18.5 Mergesort
18.6 Quicksort
18.7 Running-Time Analysis for Mergesort and Quicksort
18.8 Application: Scheduling Events
18.9 Generalized Sorting

19. Average-Case Running Time (optional reading)

19.1 Introduction to Average-Case Running Time
19.2 Average-Case Running Time of Linear Search

Appendix A. Python Reference

A.1 Python Built-In Function Reference
A.2 Python Built-In Data Types Reference
A.3 Python Special Method Reference
A.4 Python Exceptions Reference
A.5 Python Syntax Diagrams

Appendix B. Python Libraries

B.1 doctest
B.2 pytest
B.3 python-ta
B.4 typing
B.5 pdb

Appendix C. Math Reference

C.1 Summations and Products
C.2 Inequalities

Acknowledgments

These notes draw heavily from existing videos from CSC108 Introduction to Computer Programming (made by Jen Campbell and Paul Gries), course notes from CSC148 Introduction to Computer Science (co-authored by Diane Horton and David Liu) and CSC165 Mathematical Expression and Reasoning for Computer Science (co-authored by Toniann Pitassi and David Liu). We have linked to related CSC108 videos throughout the sections in these notes.

We were also assisted by a team of undergraduate students: Shannon Komguem, Oleksandr Kozin, Callum Cassidy-Nolan, Amy Peng, Evan Kanter, Kavin Singh, Tiffany Tang, Edwin Jiang, and Utsav Shinghal.

Cover artwork by Clémence Koh.

Errata

If you encounter any typos or errors in these notes, please let us know by email at csc111-2023-01@cs.toronto.edu.