CS147 Discrete Mathematics & Its Applications

⚠️ Hike! The map is not the terrain! Course summary: Probabilistic methods; Algorithms; Euler walks; Trees; Connected Graphs; Spanning Trees; Ramsey Numbers; Diagonal Ramsey Numbers; Large Graph cuts. ![[CS147 Discrete Mathematics & Its Applications 2024-06-11 01.11.52.excalidraw]] --- # 1. Algorithms & Runtime Analysis ## 1.1 Worst Case Time Complexity of Divide & Conquer Algorithms (Week 1-2) | Definitions | Lemmas | Main Theorems | Examples | | -------------------------------------------- | -------------------------------------------------------------------------- | --------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------- | | | | | | | [[Big O Relation on Real Sequences]]. | [[Big O of Real Sequence in Terms of Limit]]. | [[Sum Rule for Big O of Real Sequences]]. | [[Big O of Logarithms to Different Bases are Equal]]. | | [[Big Omega Relation on Real Sequences]]. | | [[Big O of Constant Multiple of Real Sequence]]. | [[Asymptotic Value of Partial Sum of Geometric Series]]. | | [[Big Theta Relation on Real Sequence]]. | | | [[Partial Sum of Arithmetic Series is Big Theta of Quadratic]]. | | [[Little o Relation on Real Sequences]]. | [[Equivalence of Definitions of Little o Relation on Real Sequences]]. | | [[Partial Sum of Harmonic Series is Big Theta of Linearithm]]. | | [[Little omega Relation on Real Sequences]]. | [[Equivalence of Definitions of Little omega Relation on Real Sequences]]. | | [[Asymptotic Value of Partial Sum of Arithmetic-Geometric Series]]. | | | [[Harmonic Numbers]]. | | Let $f(n)=2^{\sqrt{ \ln n }}$ and $g(n)=n^{0.0001}$ then show that $f(n)=\mathcal{O}(g(n))$ and $f(n)\neq \Omega(g(n)).lt;br> | | [[Algorithm for Computational Problem]]. | | | | | [[Worst-case Running Time of Algorithm]]. | | | | | | | | | | [[Sorting]]. | | | | | [[Bubble Sort]]. | | [[Correctness of Bubble Sort]]. | | | | | [[Bubble Sort has Quadratic Worst-case Asymptotic Running Time]]. | | | [[Divide & Conquer Algorithm]]. | | | | | [[Merge Sort]]. | | [[Merge Sort has Linearithmic Worst-case asymptotic Running Time]]. | | | [[Insertion Sort]]. | | [[Master Theorem for Polynomial Work]]. | Solve $T(n)=aT\left( \frac{n}{b} \right)+\Theta(n\log n).$ | | [[Binary Search]]. | | [[Binary Search has Logarithmic Worst-case Asymptotic Running Time]]. | | ## 1.2. Average Case Time Complexity of Randomized Quicksort (Week 3-5) | Definitions | Lemmas | Theorems | Examples | | --------------------------------------------------------------------------------- | ------------------------------------------ | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------- | | [[Probability Measure]]. | | | | | [[Conditional Probability]]. | | | | | [[Finite Partition of Sample Space]]. | | [[Law of Total Probability]]. | | | | | [[Bayes' Theorem]]. | [[Naive Bayes classifier]]. | | [[Independence of Two Events]]. | | | | | [[Mutually Independent Set of Events]]. | | | | | [[Pairwise Independent Set of Events]]. | | | | | | | [[Probability Measure is Strongly Additive]]. | | | | | [[Probability of Union is Less than Sum of Probabilities (Boole's Inequality)]]. | | | | | | | | [[Recurrence Relation]]. | | | | | [[Linear Recurrence Relation]]. | | | | | | | | | | [[Ordinary Generating Function]]. | | Using generating function to solve recurrence functions | | | | | Characteristic root method | | | [[Random Variables]]. | | | [[Coupon Collector's Problem]] Show that $\mathbb{P}(T\geq N)$ is small using chebyshev. | | [[Discrete random variables]]. | [[Expectation of Geometric Distribution]]. | [[Expectation of Integrable Non-negative Discrete Real-Valued Random Variable Equals Sum of Tail Probabilities]]. & [[Expectation of Integrable Continuous Real-Valued Random Variable Equals Sum of Tail Probabilities]]. | [[Infinite Monkey Problem]]. | | [[Conditional Expectation of Discrete Real Valued Random Variable Over Event]] | | | | | [[Conditional Expectation of Discrete Real-Valued Random Variable Over Another]]. | | [[Expectation of Conditional Expectation of Discrete Random Variable Over Another Equals Expectation (Total Expectation Theorem)]] | | | | | | | | | | Be able to use [[Markov's Inequality for Non-negative Integrable Discrete Real-valued Random Variables\|Markov's inequality]] for DRVs that are bounded below by defining non-negative DRV. | | | | | | | | [[Deterministic Quicksort]]. | | | | | [[Randomized Quicksort]]. | | [[Average Case Time Complexity of Randomized Quicksort is Linearithmic]]. | | # 2. Graph Theory ## 2.1. Pigeonhole Principle & System of Distinct Representatives (Week 6) | Definitions | Lemma | Theorems | Examples | | --------------------------------------- | ----- | --------------------------------------------------------------------------------------------- | --------------- | | | | [[Pigeonhole Principle]]. | | | [[System of Distinct Representatives]]. | | [[Hall's Theorem]]. | [[Week 7.pdf]]. | ## 2.2. Introduction to Graphs (Week 7) | Definitions | Lemma | Theorems | Examples | | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------ | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------- | | Be able to define [[Simple Graph]] using ZFC in $L_{1}.$ Be able to define the following terms in context: **adjacent**; **endpoints**; **incident**; **neighbour**; **open neighbourhood**; **closed neighbour hood**. Be able to formally define [[Undirected Multigraph]]. | | | Types of graphs: [[Path (Type of Simple Graph)]]; [[Cycle (Type of Simple Graph)]]; [[Complete Graph]]; | | | | | | | Be able to formally define [[Matching (in graphs)]]. Be aware of the following computational problem: [[Maximum Matching of Undirected Graph Problem]]. | | State, prove and use: [[Hall's Theorem]]. | | | | | | | | Be able to define in context: degree; degree sequence. | Degree of vertex of simple graph is number of neighbours. | | | | Define: [[Graphical Sequence]]. | | [[Degree-Sum Formula]]. | ??State, use and prove: [[Necessary Condition for List of Integers to be Degree Sequence of Simple Graph (Erdős–Gallai theorem)]]. | | | | | | | Define: [[Subgraph]]; [[Induced Subgraph]]. | | | Define: path in graph; cycle in graph; clique in graph. | | Define [[Connected Graph]]. | | [[Path defines Equivalence Relation on Disconnected Simple Graph]]. Note the equivalence classes are called the connected components. | [[Connected Graph with n vertices has at least n-1 edges]]. | | | | | | | Define [[Isomorphism of Graphs]]. | | | | | | | | | | Define in context: [[Walk in Undirected Graph]]; [[Euler Walk in Undirected Graph]]. | | State & prove: [[Euler's Circuit Theorem]]. [[Necessary Condition for Existence of Euler Walk in Undirected Graph]]. | [[Seven Bridges of Königsberg Problem]]. | | | | | | | Define in context: [[Graph Colouring]]. | | [[Simple Graph is Bipartite if and only if Connected Components are Bipartite]]. | | | | [[Length of Path in Bipartite Graph]]. [[Bipartite Graph contains odd Closed Walk iff contains odd Cycle]]. | [[Graph is Bipartite iff does not contain Odd Cycle]]. | | ## 2.4. Trees (Week 8) | Definitions | Lemma | Theorems | Examples | | ------------------------------------------------------------------ | ---------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------- | | Define: [[Forest (Acyclic Multigraph)]]; [[Trees (graph theory)]]. | [[Finite tree with at least two vertices has a leaf]]. | Can construct cycle if there exists two different paths between a pair of vertices - [[Tree necessarily has unique path between every pair of vertices]]. | [[Trees are Bipartite]]. | | | [[Finite tree is a connected graph with one less edge than vertices]]. | | | | | [[Tree with degree k node has at least k Pendant nodes]]. | | [[Tree has at least two Pendant nodes]]. | | | | | | | [[Spanning Tree of Connected Graph]]. | [[Every Connected Graph has a Spanning Tree]]. | | [[Connected Graph with n vertices has at least n-1 edges]]. [[Finite tree is a connected graph with one less edge than vertices]]. | | [[Cutpoint in Connected Graph]]. | | | [[Connected Graph has a node that is not a cutpoint]]. | ## 2.5. Matching (Week 9) | Definitions | Lemma | Main Theorems | Examples | | ----------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | [[Vertex Cover]]. | [[The size of the minimum vertex cover is at least the size of the maximum matching]]. [[Maximum Matching of Path or Even Cycle equals Minimum Vertex Cover]]. | | | | | [[Proof by minimal counterexample]]. | State [[König-Egevàry Theorem (Size of Maximum Matching of Bipartite Graph Equals Size of Minimum Vertex Cover)\|König-Egevàry theorem]] and prove it - by minimal counterexample; - by construction of vertex cover from matching; - it follows from Hall's theorem. | Consider a tree $T=(V,E)$ and a function $\chi:V\to \mathbb{N}.$ Suppose that $T$ is rooted at a node $r \in V .$ Moreover, suppose that for all nodes $x\in V$ in the tree with at least one child and any child $y$ of $x,$ $\chi(x)\geq \chi (y)$. Prove by minimal counterexample that for every $x\in V,$ $\chi(x)\leq \chi(r).lt;br> Give an example of a non-bipartite graph $G$ where $μ(G) = \tau(G).lt;br> Prove [[König-Egevàry Theorem implies that Hall's condition is Sufficient for Existence of Maximum Matching of Bipartite Graph]]. | ## 2.6. Elements of Ramsey Theory (Week 9-10) | Definitions | Lemmas | Main Theorems | Examples | | ------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | --------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------- | | | [[Probabilistic Method]]. | | [[Lower Bound for Maximum Cut in Terms of Number of Edges]]. [[Average Case Time Complexity of Randomized Max-Cut Approximation Algorithm]]. | | | | | | | [[Ramsey Number on Two Colours]]. | [[Ramsey Numbers on Two Colours is Symmetric]]. | | | | | [[Ramsey Numbers on Two Colours in First Row or Column]]. [[Ramsey Numbers on Two Colours in Second Row or Column]]. [[Recurrence Inequality for Ramsey Numbers on Two Colours]]. | [[Upper bound for Ramsey Numbers on Two Colours (Ramsey's Theorem)]]. | [[Upper bound for Diagonal Ramsey Numbers on Two Colours]]. | | [[Ramsey Number on Multiple Colours]] | | multi colour ramsey theoery | | | | | | | | | | [[Probabilistic Method]]. | [[Lower Bound for Diagonal Ramsey Numbers on Two Colours]]. [[Lower Bound for Diagonal Ramsey Numbers on Two Colours Where Row=Column is at Least 3]]. |