﻿ CSE547: Discrete Mathematics
Quiz

# CSE547 : Discrete Mathematics

### Chapter 1.1 : The Tower of Hanoi

• Hanoi Program
1. Look at small cases
• Write recursive function
2. Find and prove recurrence relation
• Count complexity of recursive function
3. Find and prove recurrence solution
1. Solve Recurrence somehow
2. Prove By Induction

### Chapter 1.2 : Lines in the plane

1. Understand Problem
• What is the maximum number of pizza slices that you can make for a given number of cuts?
• What is the maximum number of sections that you can divide the plane for a given number of cuts?
• The answers are the same because you can always draw a circle large enough to contain all intersections.
• The maximal strategy is new line hits each previous line as much as you can (which is once per line).
2. Look at small cases
•  Number of lines 0 1 2 3 Number of slices 1 2 4 7
• Each new line makes a new slice on the entering and leaving side of an intersection
3. Find and prove recurrence relation
• S0 = 1
• Sn = Sn-1 + n
4. Find and prove recurrence solution
1. Solve Recurrence somehow : Sn = n(n+1)/2 + 1
2. Prove By Induction
1. Let P(n) be Sn = n(n+1)/2 + 1
2. P(0) is S0 = 0(0+1)/2 = 0 is True
3. Assume P(n)
4. Sn = (n+1)(n)/2+1
5. Sn + n+1 = (n+1)(n)/2 + 1 + n+1
6. Sn+1 = (n+1)(n)/2 + (n+1) + 1 = (n+1)(n)/2 + (n+1)(2)/2 + 1 = (n+1)(n+2)/2 + 1
7. P(n+1)

### Chapter 1.3 : The Josephus Problem

1. Understand Problem
• There are n people in a circle (numbered 1 through n).
• You go around the circle killing every other person (not first) until one person is left.
• Where do you stand so that you're the last man left standing?
• The maximal strategy is new line hits each previous line as much as you can (which is once per line).
2. Look at small cases
•  Number of people 1 2 3 4 5 6 7 8 9 10 11 Last man standing 1 1 3 1 3 5 7 1 3 5 7
• It looks like 1 13 1357 13579111315 ...
3. Find and prove recurrence relation
• J1 = 1
• J2n = 2Jn - 1
• J2n+1 = 2Jn + 1
4. Find and prove recurrence solution
1. Solve Recurrence somehow : J(2^m+L) = 2L + 1
2. Prove By Induction
1. Let P(n) be J(2^m+L) = 2L + 1
2. P(0) is J(1)=J(2^0+0)=2(0)+1=1 is True
3. Assume P(n)
4. ...
5. P(n+1)

### Exercises

• 1.10
• Proof by Necessity & Sufficiency
• 1.14
• 1.16
• 1.21

### Chapter 2.1 : Notation

• Sums can be written with the ... notation
• a1 + a2 + ... + an
• Sums can be written with the Σ notation
• Delimited Form : $\sum_{k = 1}^n a_k$
• Generalized : 1≤k≤nΣ ak
• Iverson Bracket (strongly zero) : kΣ ak[1≤k≤n]

### Chapter 2.2 : Sums and Recurrences

• \left[ \begin{matrix} S_0 = a_0\\ S_n = S_n_-_1 + a_n \end{matrix} \right\\ \textrm{Has Solution}\\ S_n = \sum_{k=1}^{\infty} a_k

### Chapter 2.3 : Manipulation of Sums

• Distributive law : sum(k in K, c*a_k) = c * sum(k in K, a_k)
• Associative law : sum(k in K, a_k+b_k) = sum(k in K, a_k) + sum(k in K, b_k)
• Commutative law : sum(k in K, a_k) = c * sum(p(k) in K, a_p(k))
• Perturbation Method : Sn + a_n+1 = a_0 + sum(k=0..n, a_k+1)
• Geometric Series : sum(k=0..n, x^k) = (1-x^(n+1))/(1-x)

### Chapter 2.4 : Multiple Sums

• Interchanging the order of summation
• sum(j,sum(k,a_jk[P(j,k)])) = sum(k,sum(j,a_jk[P(j,k)]))

### Chapter 2.5 : General Methods

• sum(k=0..n,k^2) = n(n+1)(2n+1)/6

### Chapter 2.6 : Finite and Infinite Calculus

• Δf(x) = f(x+1) - f(x)
• xm = x(x-1)...(x-m+1)
• x = x(x+1)...(x+m-1)
• ₐΣᵇ g(x)δx = ₐΣᵇ⁻¹ g(x)
• ₐΣⁱ δx + ᵢΣᶻ δx = ₐΣᶻ δx
• x-m = 1/(x+1)
• x-m= 1/(x-1)m
• Σ xⁿ- δx = H(x) if n=-1 else xn+1/(n+1)
• Σ bˣδx = bˣ/(b-1)
• Δ(uv) = uΔv + EvΔu
• ΣuΔv = uv - ΣEvΔu

### Chapter 2.7 : Infinite Sums

• If sum|Ak| exists, then sum(Ak) follows the rules of Chapter 2.
• Geometric Series : sum(k=0..inf, x^k) = 1/(1-x)
• Geometric Series : sum(k=1..inf, x^k) = x/(1-x)

### Exercises

• 2.1
• ₐΣⁱδx + ᵢΣᶻδx = ₐΣᶻδx
• 2.14
• ₐΣᵇg(x)δx = ₐΣᵇ⁻¹g(x)
• 2.21
• 2.28
• 2.31

### Chapter 3.1 : Floors and Ceilings

• ⌊x⌋ = greatest integer ≤ x
• ⌈x⌉ = least integer ≥ x

### Chapter 3.2 : Floor/Ceiling Applications

• Spec(α) and Spec(β) partition N <=> 1/α + 1/β = 1

### Chapter 3.3 : Floor/Ceiling Reccurences

• MergeSort:
• f(1) = 0
• f(n) = f(⌈n/2⌉) + f(⌊n/2⌋) + n-1

### Chapter 3.4 : 'mod': The Binary Operation

• x mod y = x - y⌊x/y⌋

### Chapter 3.5 : Floor/Ceiling Sums

• Change of variable is one way to solve sums of floors.

### Chapter 4.1 : Divisibility

• m\n ⇔ m>0 and n=mk for k∈N

### Chapter 4.2 : Primes

• Prime means has 2 divisors

### Chapter 4.3 : Prime Examples

• π(x) ~ x / ln x

### Chapter 4.4 : Factorial Factors

• εp(n) = The Exponent of p in n's unique factorization. I.E. εp(n) = np when n = Πpnp

### Chapter 4.5 : Relative Primality

• m ⊥ n means gcd(m,n)=1

### Chapter 4.6 : 'mod': The Congruence Relation

• a ≡ b (mod m) ⬄ m\(a-b)
• d⊥m → [ ad≡bd(mod m) ⬄ a≡b(mod m) ]

### Chapter 4.7 : Independent Residues

• Res(x) = {x mod m₁,...,x mod mᵣ}, if mj ⊥ mk for 1≤j<k≤r

### Chapter 4.8 : Additional Applications

• Fermat's Little Theorem:
• nᵖ ≡ n (mod p)   where n∈N,p∈P
• Wilson's Theorem:
• (p-1)! ≡ -1 (mod p)   where p∈P

### Chapter 4.9 : Phi and Mu

• φ(m) = [0,m).count(#⊥m)

• 4.16
• 4.24
• 4.26
• 4.30
• 4.38
• 4.42
• -
• 4.32
• 4.33
• 4.47
• 4.48

### Chapter 5.1 : Basic Identities

• n Permute k = nk
• n Choose k = nk / k!

### Chapter 5.2 : Basic Practice

•  5.6 Absorption : {r\choose k} = \frac{r}{k} {r-1\choose n-1}
•  5.9 Parallel Sum : \sum_{k\leq n} {r+k\choose k} = {r+n+1\choose n}

### Chapter 5.3 : Tricks of the Trade

• \Delta {x\choose k} = {x\choose k-1}
• \Delta^n = (E-1)^2 = \sum_k {n \choose k}E^k(-1)^{n-k}

### Chapter 5.4 : Generating Functions

• $A(z) = \sum_{k\geq 0} a_k z^k = a_0 + a_1z + a_2z^2 + ... \Leftrightarrow \langle a_0,a_1,a_2,...\rangle$
• $\frac{1}{1-z} = \sum_{k\geq 0} 1 z^k = 1+z+z^2+... \Leftrightarrow \langle 1,1,1,...\rangle$
• $\frac{1}{(1-z)^{n+1}} = \sum_{k\geq 0} {n+k \choose k} z^k \Leftrightarrow \langle {n \choose 0},{ n+1 \choose 1},{n+2 \choose 2},...\rangle$

### Chapter 5.5 : Hypergeometric Functions

• F(a1,...,am;b1,...,bn;z)
• F(^a|z) = \sum_{k\geq 0} \frac{a^{\overline k} z^k}{k!} = \sum_{k\geq 0} \frac{(a+k-1)^{\underline k}}{k!} z^k = \sum_{k\geq 0} {a+k-1 \choose k} z^k = \frac{1}{(1-z)^a}

### Chapter 5.6 : Hypergeometric Transforms

• \frac{1}{(1-z)^a} F \left( ^{a,b} _c | \frac{-z}{1-z} \right) = F(^{a,c-b} _c|z)
• \frac{d}{dz} F(^a _b|z) = \frac{a}{b} F(^{a+1} _{b+1}|z)

### Chapter 5.7 : Partial Hypergeometric Sums

• \sum F_k\delta k = c $F$_k + C
• t(k) is hypergeometrically summable ↔ t(k+1)/t(k) is a rational function of k

### Chapter 5.8 : Mechanical Summation

• Partial Sums can be extended to General Sums.
• Zeilberger Summable: terms ratios can be functions of n.

### Chapter 6.1 : Stirling Numbers

• Def: $\{ _{k}^{n} \} = The number of ways to arrange n objects into k nonempty subsets.$
• Def: $$_{k}^{n} ]} = The number of ways to arrange n objects into k nonempty cycles.$ • 6.3) $\{ _{k}^{n} \} = k\{ _{k}^{n-1} \} + \{ _{k-1}^{n-1} \}$ • 6.8) $\[ _{k}^{n}$ = (n-1)$_{k}^{n-1}$ + $_{k-1}^{n-1}$$
• 6.9) $\sum_{k} $_{k}^{n}$ = n!$
• 6.10) $x^n = \sum_{k} \{ _{k}^{n} \} x ^ {\underline k}$
• 6.11) $x^{\overline n} = \sum_{k} $_{k}^{n}$ x ^ k$
• 6.31) $\sum_{k} \{ _{k}^{n} \} $_{m}^{k}$ (-1) ^ {n-k} = [m=n]$

### Chapter 6.2 : Eulerian Numbers

• $\langle _{k}^{n} \rangle = The number of permutations a set of size n, which have k ascents.$

### Chapter 6.3 : Harmonic Numbers

• $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdot\cdot\cdot + \frac{1}{n} = \sum_{k=1}^{n} \frac{1}{k}$

### Chapter 6.4 : Harmonic Summation

• $\sum_{0\leq k

### Chapter 6.5 : Bernoulli Numbers

• $\frac{z}{e^z-1} = \sum_{n\geq 0}B_n \frac{z^n}{n!}$

### Chapter 6.6 : Fibonacci Numbers

• (6.117)$F(z) = \frac{z}{1-z-z^2}$
• (6.121) $\phi^2 = \phi + 1$

### Chapter 6.7 : Continuants

• $a_0 + \frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{a_4+\frac{1}{a_5+\frac{1}{a_6+\frac{1}{a_7}}}}}}}$

### Chapter 7.1 : Domino Theory and Change

• Some Dynamic Programming problems can be solved instead by generating functions.

### Chapter 7.2 : Basic Maneuvers

• $\langle 1,0,0,...\rangle \Leftrightarrow \sum_{n\geq 0} [n=0] z^n = 1$

### Chapter 7.3 : Solving Recurrences

• Recurrences can be easily translated into Generating Functions.

### Chapter 8.1 : Definitions

• (8.1) $\sum_{\omega \in \Omega} Pr(\omega) = 1$

### Chapter 8.2 : Mean and Variance

• (8.13) $VX = E[(X-EX)^2]$

### Chapter 8.3 : Probability Generating Functions

• (8.25) $G_X(z) = \sum_{k \ge 0} Pr(X=k)z^k$
• (8.30) $Mean(G) = G'(1)$
• (8.38) $H(z) = F(z)G(z) \iff Mean(H) = Mean(F) + Mean(G)$

### Chapter 8.4 : Flipping Coins

• (8.56) $H(z) = q + pz$

### Chapter 8.5 : Hashing

• Makes the task of searching about m times faster. (Where m is the number of lists)
• (8.91) $P(x | y) = \frac{P(x \cap y)}{P(y)}$

### Chapter 9.3 : VM as a tool for caching

• Virtual Pages are P=2^p bytes in size
• Practice Problem 9.2
nP=2^pNumber of PTEs
121K 2^12/2^10=2^2
1616K2^16/2^14=2^2
242M 2^24/2^21=2^3
361G 2^36/2^30=2^6

### Chapter 9.6 : Address Translation

• Hardware supports Virtual Memory
• Practice Problem 9.3
PNumber of VPN bitsNumber of VPO bitsNumber of PPN bitsNumber of PPO bits
1KB 54102210
2KB 53112111
4KB 52122012
16KB50141814

### Chapter 9.9 : Dynamic Memory Allocation

• C programs allocate a block by calling malloc
• Free a block by calling the free function

### Chapter 9.9.1 : The malloc and free Functions

• stdlib.h
• Applications that want initialized dynamic memory can use calloc
• Blocks aligned to double words.
• It is the responsibility of the application not to use freed pointers

### Chapter 9.9.2 : Why Dynamic Memory Allocation?

• They do not know the size of certain data structures until the program actually runs
• (int *)malloc(n * sizeof(int))

### Chapter 9.9.3 : Allocator Requirements and Goals

• Aligning blocks (alignment requirement): Blocks must be able to hold any type.
• Throughput (important) vs. Utilization (unimportant)

### Chapter 9.9.4 : Fragmentation

• Fragmentation decreases Utilization.
• Fragmentation: Internal & External.

### Chapter 9.9.5 : Implementation Issues

• Free block organization
• Placement
• Splitting
• Coalescing

### Chapter 9.9.6 : Implicit Free Lists

• Implicit free list = Header has size only
• O(#Blocks)

### Chapter 9.9.7 : Placing Allocated Blocks

• Placement Policy: First Fit, Next Fit, Best Fit
• First Fit tends to leave "splinters"

### Chapter 9.9.8 : Splitting Free Blocks

• Free Block -> Allocated + Free

### Chapter 9.9.9 : Getting Additional Heap Memory

• sbrk() Kernel returns more memory.

### Chapter 9.9.10 : Coalescing Free Blocks

• Coalescing fixes False Fragmentation
• Immediate vs. Deferred Coalescing

### Chapter 9.9.11 : Coalescing with Boundary Tags

• Footer (Boundary Tag) allows for O(1) coalescing
• Footer is a copy of header

### Chapter 9.9.12 : Putting It Together: Implementing a Simple Allocator

• General Allocator Design
• sbrk() increases heap size
• Basic Constants and Macros for Manipulating the Free List
• Creating the Initial Free List
• mem_sbrk() calls sbrk()
• Freeing and Coalescing Blocks
• Allocating Blocks
• FindFit()
• Place()

### Chapter 9.9.13 : Explicit Free Lists

• Payload stores next and prev Free Block
• Free-list has LIFO or Address order

### Chapter 9.9.14 : Segregated Free Lists

• Maintain multiple Free Lists segregated by size
• Simple Segregated Storage
• Segregated Fits
•  Buddy Systems

### Chapter 9.10 : Garbage Collection

• Chapter 9.10.1 : Garbage Collector Basics
• Chapter 9.10.2 : Mark&Sweep Garbage Collectors
• Chapter 9.10.3 : Conservative Mark&Sweep for C Programs