Due to the lack of course work (and, really, anything else to do), I get time to contemplate and write stuff here, so here I am.

In first year, I have decided to take notes in $$\LaTeX$$ for some of my introductory CS courses. These notes were taken both as an effort to kill time during lecture and they were also simultaneously submitted to the UofT note takers service for those who are unable to attend class.

I have previously set up a site notes.jimgao.tk, but I have decided to kill it since hosting is expensive. I thought that the next best option is to host them here and hopefully Google would index this page eventually :P.

Below are the notes catagorized by courses. I might also add my notes for CSC265 here in a few days (or weeks). (CSC265 notes added on Apr 8th, 2022)

CSC265 (Enriched Data Structures and Analysis)

1 Worst case analysis of running time; Abstract data types; Binary heaps PDF
2 Binomial heaps; Dictionary ADT PDF
3 AVL trees PDF
4 Augmented AVL trees; Order statistics PDF
4 (tutorial) Interval trees (augmented AVL) PDF
5 Average case analysis; Randomized Algorithms; Universal hashing PDF
5 (tutorial) Height of random BSTs PDF
6 Randomized quicksort; Principle of deferred decision; Amortized analysis PDF
6 (tutorial) Randomized Maj3; Reservoir sampling; Biased coins PDF
7 Potential function method for amortized analysis PDF
8 Disjoint sets and its optimizations PDF
10 Disjoint set log* analysis PDF
11 Graph traversals (BFS,DFS); Parenthesis property; White path theorem PDF
11 (tutorial) Strongly connected components PDF
12 Minimum spanning trees; Kruskal’s algorithm PDF

CSC165 (Mathematical Expression and Reasoning for Computer Science)

This is a course basically taken by all first-year CS students, and covers the basics of predicate logic, number theory, and some concepts in graph theory. Much of the course is emphasized on stating questions rigorously in formal logic, as well as proving claims with logical rigor.

1 Mathematical preliminaries, sets, functions PDF
2 Functions, sigma/pi notation, propositional logic, truth tables PDF
3 Implications, biconditions, reordering quantifiers PDF
4 Negating quantified statements PDF
5 Precedence rule, proving existential and universal statements PDF
6 * Missing *
7 Example: proof with primes PDF
8 Simple induction, examples of induction PDF
9 More on simple induction PDF
10 Strong induction, representation of natural numbers PDF
11 Representation in binary, analyzing running time PDF
12 More on binary numbers, introduction of $$\mathcal{O}$$ notation PDF
13 Patterns of upper bound PDF
14 Examples of runtime analysis on code snippets PDF
15 More examples on runtime analysis PDF
16 Even more examples, Collatz sequence PDF

CSC240 (Enriched Introduction to the Theory of Computation)

This course is effectively an enriched version of CSC165+CSC236. It covers much of the formal logic stuff, but also covers structural induction, proofs of time complexity and correctness, formal language, DFAs, and NFAs. It was taught by Professor Faith Ellen, and this is definitely one of the more fun courses I have taken.

1 Induction, $$2^n\times 2^n$$ chessboard problem PDF
2 Examples of simple induction, AM/GM inequality, strong (complete) induction PDF
3 More strong induction, recursively defined sets, structural induction PDF
4 Functions on recursively defined sets, example about leaves on binary trees PDF
5 Justification of structural induction by strong induction, partial orders, and the well-ordering principle PDF
6 Countable and uncountable sets, proof by diagonalization, the halting problem PDF
7 Introduction of asymptotic notation and their properties. Tips on solving recurrences PDF
8 More on solving recurrences, “plug-and-chug”, Master theorem, characteristic polynomials PDF
9 Runtime analysis, example about merge sort PDF
10 Analyzing running time for recursive binary search. Correctness of algorithms PDF
11 Examples on correctness proofs: pre/post conditions. Examples: merge sort and quick sort PDF
12 Language theory, regular expressions, definition of DFAs PDF
13 Example of DFAs. Non-deterministic Finite Automaton (NFAs) PDF
14 Pumping lemma and its applications PDF
15 Closure of operations on regular languages and their proofs PDF