Computer science as a science.
Notes
- Course taught by Nick Cheng
- 5 Tutorial sections
- Tutorials lag behind by one week
- OH: https://cmsweb.utsc.utoronto.ca/nick/timetable.html
- https://www.cs.toronto.edu/~vassos/b36-notes/notes.pdf
- https://cmsweb.utsc.utoronto.ca/nick/cscB36/additional-notes/
- Exam seats are randomly assigned
- FYOG Assignments dont count for marks
- Problem sets are used only for extra marks, they are posted collectively on piazza, they are worth 10%
- Final exam 40%
- Term test 1 20% (Oct 4 9-10:30AM)
- Term test 2 20% (Nov 10, 5-6:30PM)
- The media gallery has 2021 videos for future review
- Everytime you use a Indirect Proof, you must explitly show
Concepts
Week 1
- Mathematical Maturity
- Math Proof
- Atomic Symbols
- Mathematical Statement
- Logical Predicate
- Universal Instantiation
- Witness
- Indirect Proof
- Implies
- Or
- Such That
- Twin Prime
- Twin Prime Conjecture
- Halting Problem
- Cartesian Product
- Relation
- Arity
Week 2
- Binary String
- Counting Odd Parity Substrings from Given Binary String
- Simple Induction
- Stamps Simple Induction Example
- Stamps Strong Induction Example
- Unwinding Recurrence
- Master Theorem
- Principle of Well-Ordering
- Proof by Structural Induction
- Smallest Set
Week 3
- Pascal
- Program Correctness
- Loop Invariant
- Iterative Program Correctness
- Recursive Program Correctness
- Pythonized Lemma 2
Week 4
- Nothing new, just practice
Week 5
- Empty String
- Terminating Variable
- Symbol
- Alphabet
- String
- Language
- Regular Language
- Regular Expression
- Semantics of Regular Expressions
- Multiset
- Regex Precedences
- Regex to Match All Strings
- Regex to Match Even Length Strings
- Regex to Match Strings that Start and End with 1
- Equivalent Regex
- Language Function
- Closure of Regular Expressions