# Course: SOFTENG 211

SOFTENG 211 - "software engineering theory"

This course is inappropriately named. To my knowledge, it's better that it's called something like "discrete mathematics". This course is the best course in this semester.

- logic
- propositional logic, first-order logic, predicate logic, quantifiers
- the 16 binary boolean operators

- set theory
- equality
- indiscernability of identicals / identity of indiscernables

- "pairs"
- "reification"
- !! "element of" being the only predicate needed
- Zermelo-Fraenkel Set Theory
- "functions" - are relations which is left-total and right-unique
- Cartesian product
- equivalence relation
- equivalence classes
- partition

- partial order
- "strict partial order"?
- total order

- transitive closure
- directed acyclic graph

- "uniqueness" & "totality" of functions
- injectivity, surjectivity, bijectivity

- equality
- mathmatical induction
- pigeonhole principle

- strings
- string:= function: N --> alphabet
- concatenation
- partial evaluation of functions
- semigroup, monoid
- e.g. function compositio

- computability
- Gödel's Incompleteness Theorums (IT1 & IT2)
- strings and "languages"
- deterministic finite automata
- pumping lemma
- concatenation of languages
- Mealy+ machines

- Turing machines
- universal Turing machines
- how it runs over the same tape (like a caterpillar)
- algorithm (really just manually simulating a TM)

- halting problem, entscheidungsproblem, busy beavers
- time complexity of UTM (uncomputably steep)

- universal Turing machines
- "primitive recursive functions" & others
- introducing P & NP problems
- other universal computing paradigms
- Conway's game of life
- UTM running on a bintree instead of a linear tape

- boolean algebra
- normal forms (CNF, DNF)
- satisfiability(of CNF)/non-validity(of DNF) (hard)
- prefix normal form

- lambda calculus
- currying
- lambda terms
- infinite supply (x0, x1, x2, ...)
- application
- abstraction

- free variables vs. bound variables
- shadowing
- alpha-conversion (renaming a bound variable)
- beta-reduction (applying an abstraction)
- pairs, and the "True", "False" abstractions(functions)
- recursion, and intro to the Y-combinator
- evaluation order
- deterministic strategies
- applicative order (start with rightmost, innermost)
- it sometimes loops forever

- normal order (start with leftmost, outermost)
- it sometimes duplicates work (but can be solved by caching,

aka "lazy evaluation")

- it sometimes duplicates work (but can be solved by caching,

- applicative order (start with rightmost, innermost)
- non-deterministic strategies
- inherent parallelism

- deterministic strategies

- counting
- set, multiset, list, permutation
- bitstring/signature

- some counting principles
- invariance
- disjoint sum
- cartesian product

- counting "weak compositions" & "compositions"
- counting functions f: S -> T, given |S|, |T| (power)
- counting surjective functions f (Stirling number of the second kind)

- set, multiset, list, permutation
- graphs
- directed graph (aka "digraph")
- "walk", "path", "cycle"
- tree
- example: counting binary trees which have n nodes
- using transition matrices
- counting walks
- using generating functions, on matrices

- counting walks
- Eulerian cycles
- Hamiltionian cycle
- minimum spanning trees
- Prim's algorithm
- Kruskal's algorithm

- shortest path
- Dijkstra's algorithm

- using generating functions
- example: Fibonacci sequence
- example: Pascal's triangle (two-param GenFunc) (combinations)