Past Course Notes
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)
Links: FAS Calendar
| Lecture # | Topics | Link |
|---|---|---|
| 1 | Worst case analysis of running time; Abstract data types; Binary heaps | |
| 2 | Binomial heaps; Dictionary ADT | |
| 3 | AVL trees | |
| 4 | Augmented AVL trees; Order statistics | |
| 4 (tutorial) | Interval trees (augmented AVL) | |
| 5 | Average case analysis; Randomized Algorithms; Universal hashing | |
| 5 (tutorial) | Height of random BSTs | |
| 6 | Randomized quicksort; Principle of deferred decision; Amortized analysis | |
| 6 (tutorial) | Randomized Maj3; Reservoir sampling; Biased coins | |
| 7 | Potential function method for amortized analysis | |
| 8 | Disjoint sets and its optimizations | |
| 10 | Disjoint set log* analysis | |
| 11 | Graph traversals (BFS,DFS); Parenthesis property; White path theorem | |
| 11 (tutorial) | Strongly connected components | |
| 12 | Minimum spanning trees; Kruskal’s algorithm |
CSC165 (Mathematical Expression and Reasoning for Computer Science)
Links: FAS Calendar
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.
| Lecture # | Topics | Link |
|---|---|---|
| 1 | Mathematical preliminaries, sets, functions | |
| 2 | Functions, sigma/pi notation, propositional logic, truth tables | |
| 3 | Implications, biconditions, reordering quantifiers | |
| 4 | Negating quantified statements | |
| 5 | Precedence rule, proving existential and universal statements | |
| 6 | * Missing * | |
| 7 | Example: proof with primes | |
| 8 | Simple induction, examples of induction | |
| 9 | More on simple induction | |
| 10 | Strong induction, representation of natural numbers | |
| 11 | Representation in binary, analyzing running time | |
| 12 | More on binary numbers, introduction of \(\mathcal{O}\) notation | |
| 13 | Patterns of upper bound | |
| 14 | Examples of runtime analysis on code snippets | |
| 15 | More examples on runtime analysis | |
| 16 | Even more examples, Collatz sequence |
CSC240 (Enriched Introduction to the Theory of Computation)
Links: FAS Calendar
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.
| Lecture # | Topics | Link |
|---|---|---|
| 1 | Induction, \(2^n\times 2^n\) chessboard problem | |
| 2 | Examples of simple induction, AM/GM inequality, strong (complete) induction | |
| 3 | More strong induction, recursively defined sets, structural induction | |
| 4 | Functions on recursively defined sets, example about leaves on binary trees | |
| 5 | Justification of structural induction by strong induction, partial orders, and the well-ordering principle | |
| 6 | Countable and uncountable sets, proof by diagonalization, the halting problem | |
| 7 | Introduction of asymptotic notation and their properties. Tips on solving recurrences | |
| 8 | More on solving recurrences, “plug-and-chug”, Master theorem, characteristic polynomials | |
| 9 | Runtime analysis, example about merge sort | |
| 10 | Analyzing running time for recursive binary search. Correctness of algorithms | |
| 11 | Examples on correctness proofs: pre/post conditions. Examples: merge sort and quick sort | |
| 12 | Language theory, regular expressions, definition of DFAs | |
| 13 | Example of DFAs. Non-deterministic Finite Automaton (NFAs) | |
| 14 | Pumping lemma and its applications | |
| 15 | Closure of operations on regular languages and their proofs |
STA130 (An Introduction to Statistical Reasoning and Data Science)
Links: FAS Calendar
This is an introductory course on data science. It covers both programming in R, as well as some basic statistical concepts such as linear regression and hypothesis testing.