Algorithmic Thinking
COMP 182
Logic and Proofs §
Propositions §
please don’t confuse AND
/conjunction/ with OR
/disjunction/.
F | F | F | F | F | T | T | T | T | T |
F | T | F | T | T | T | F | F | T | F |
T | F | F | T | T | F | T | F | F | T |
T | T | T | T | F | T | T | T | F | F |
Tautology: always true
Contradiction: always false
Satisfiable: not a contradiction. not always false. not impossible.
SAT: propositional satisfiability. NP-complete.
Propositional equivalence §
and are logically equivalent if () is a tautology.
De Morgan’s laws:
-
-
-
double negation
-
commutative laws
-
distributive laws
-
implication laws
prove equivalences using:
- truth tables
- a series of other equivalences
Predicates and Quantifiers §
variables.
e.g. ,
quantifiers:
-
universal quantification
. for all in the presumed domain, is true
-
existential quantification
. there exists an such that is true.
demorgan’s laws:
,
negating nested quantifiers:
- s///g
- s///g
- negate the proposition
Proofs and Proof Techniques §
proofs: valid arguments that establish the truth of statements
Rules of Inference §
Proof techniques §
- direct proofs
- contrapositive proofs
- proof by contradiction
- existence proofs
- counterexamples
Sets §
unordered collection of unique items
- roster method
- set comprehension
cardinality of a finite set: number of elements in the set
infinite sets: countable, uncountable
Proper subsets (): subsets excluding the set itself
Set operations §
- union —
- intersection —
- disjoint:
- difference —
- complement —
- cartesian product —
Set identities §
-
equality
implies
-
de morgan’s laws
-
complementation law —
-
commutative
-
associative
-
distributive
Functions §
non-empty sets (domain) and (codomain)
function: assignment — from every element in to exactly one element in
range (elements actually used as values) codomain
and are equal functions when:
when and
Injections, surjections, bijections §
-
Injection aka “one-to-one”
:
hoz. line test
-
Surjection aka “onto”
-
Bijection
both one-to-one and onto
There exists a bijection iff
Inverse and composition §
Relations and their properties §
a binary relation from to is a subset of .
,
,
- reflexivity —
- symmetric —
- antisymmetric —
- transitivity —
composing —
Representing relations §
-
adjacency matrix where:
-
di(rected)graphs
Relation closures §
" is the closure of wrt " — relation is the smallest set that satisfies property such that
[ is a relation on set ]:
-
reflexive closure
-
symmetric closure
-
transitive closure
Equivalence relations §
-
reflexive
-
symmetric
-
transitive
beware of “or”/“common” relations wrt transitivity
two element are equivalent () if they’re related by an equivalent relation.
is an equivalence relation on , . equivalence class of () is
partition of .
- are non-empty sets
- for any ,
bipartition: .
fundamental theorem of equivalence relations: the set of all equivalence classes of a relation on form a partition of .
Partial Orders §
- reflexive
- antisymmetric
- transitive
set + partial order = partial-ordered set aka “poset”
and are elements of a poset . and are comparable if either or . else, they are incomparable.
if is a poset where every two elements of are comparable, is a totally ordered set and is a total order.
Hasse diagrams are graphical reps of partial orders. excludes reflexivity and arrows that can be obtained by transitivty.
is a maximal element if there’s no such that
is a minimal element if there’s no such that
minimal and maximal elements do not have to exist or be unique.
is the greatest element if .
is the least element if .
greatest and least elements do not have to exist, but they must be unique.
a totally ordered set is a well-ordered set if every non-empty subset of has a least element
Matrices §
Graphs §
Undirected graphs §
Pair where:
- is a non-empty set of nodes
Directed graphs §
aka digraphs
Pair where:
- is a non-empty set of nodes
Jargon §
-
neighbours
-
degree
- in-degree
- out-degree
-
tail, head
-
subgraph
subset of nodes and subset of edges.
-
induced subgraph
subset of edges and all edges that connect them.
-
Special graphs §
-
complete graph: graph with an edge between every two nodes
-
cycle
-
bipartite graph
can be bipartitioned into and such that
bipartite theorem: a graph is bipartite iff there exists a function such that
colour neighbours of -coloured nodes with and vice-versa
- complete bipartite graph
-
forest: acyclic
-
tree: connected and acyclic.
Connectivity §
-
path
- simple — path that doesn’t contain the same node more than once
- circuit — path that begins and ends at the same node
- cycle — simple circuit
-
connected
- connected component
- strongly connected
- weakly connected
- strongly connected component
Graph Isomorphism §
-
graph isomorphism
equivalence relation
-
subgraph isomorphism
partial order
Q: subgraph isomorphism vs subgraph
- every graph is isomorphic to itself
Representing graphs §
number of nodes
number of edges
-
adjacency
listsetinput size
❤ sparse
-
adjacency matrix
input size
❤ dense
Sequences and Summations §
sequence: a function from a subset of the set of integers to a set . ,
-
geometric progression
initial term , common ratio
-
arithmetic progression
initial term , common difference
recurrence relation for a sequence is an equation that expresses in terms of one or more of the previous terms of the sequence
summation:
series: sum of a sequence from or as necessary
- telescoping sums
- perturbation method
Algorithm Efficiency §
finite sequence of precise instructions for performing a computation
- a name
- input/output
- unambiguous steps
- finite {time,number of steps}
- correct output values for each set of input values
Big O notation §
if there exist positive constants and such that for all
- , .
- , .
Big Omega notation §
if there exist positive constants and such that for all
Big Theta notation §
… aka “order of”
if there exist positive constants , , and such that for all
iff and .
Complexity of algorithms §
efficiency:
- time
- space
ignore multiplicative and additive constants
for a given input size :
-
worst case — upper bound
-
best case — usually useless
-
average case — informative, but requires making assumptions about the input
-
-
-
-
-
-
,
-
if there exists a polynomial-time worst-case algorithm for a problem, the problem is tractable. else, it’s intractable.
- tractable: class P
- intractable
- solution can be verified in polynomial time: class NP
- class NP-complete
halting problem:
- does a given computer program terminate for a given input
- proven unsolvable
post correspondence problem
BFS §
[see also: COMP 140’s BFS section]
[see also: COMP 140’s Queue section]
Mathematical Induction §
Important fact: The set of positive integers is well-ordered.
-
Basis step: Show that
-
Inductive step: Show that
The assumption that is called the inductive hypothesis
Strong Mathematical Induction §
-
Basis step: Show that
-
Inductive step: Show that