Midterm Methods

Question 1

Propose-and-Reject Algorithm (Gale-Shapley)

Answer 1

1. Each unmatched job proposes to its highest-ranked remaining candidate
2. Each candidate tentatively accepts their best offer and rejects others
3. Rejected jobs mark candidates as unavailable and try next preference
4. Repeat until all jobs are matched

Question 2

Finding an Eulerian Tour

Answer 2

1. Start at any vertex
2. Follow unused edges, deleting them as you go
3. If stuck at a vertex with no unused edges, place the path there
4. Start a new path from a vertex with unused edges that’s already in the tour
5. Merge the new path with the existing tour
6. Repeat until all edges are used

Question 3

Fast Modular Exponentiation

Answer 3

1. Convert exponent to binary
2. Start with result = 1
3. For each bit from left to right:
   a. If current bit is 0 → result^2 (mod m)
   b. If current bit is 1 → result^2 * base (mod m)
4. Return final result

Question 4

Euclid’s Algorithm for GCD

Answer 4

1. If y = 0, return x
2. Otherwise, return gcd(y, x mod y)
3. Repeat until remainder is 0

Question 5

Extended Euclid’s Algorithm

Answer 5

1. If y = 0, return (1, 0, x) representing 1·x + 0·y = x
2. Otherwise, recursively find (a', b', d) = extended_gcd(y, x mod y)
3. Return (b', a' - b'·⌊x/y⌋, d) representing a·x + b·y = d
4. Base values are returned up the recursion to find coefficients

Question 6

RSA Setup Procedure

Answer 6

1. Choose two distinct large prime numbers p and q
2. Compute N = p × q
3. Calculate φ(N) = (p-1)(q-1)
4. Choose public exponent e where 1 < e < φ(N) and gcd(e, φ(N)) = 1
5. Determine private key d where d·e ≡ 1 (mod φ(N))
6. Public key is (N, e), private key is d

Question 7

Lagrange Interpolation

Answer 7

1. For each point (xᵢ, yᵢ), create basis polynomial Lᵢ(x)
2. For each Lᵢ(x), compute Lᵢ(x) = ∏(j≠i) (x-xⱼ) / (xᵢ-xⱼ)
3. Combine as P(x) = ∑yᵢ·Lᵢ(x)
4. Simplify the resulting polynomial

Question 8

Shamir’s Secret Sharing

Answer 8

1. Choose secret S and threshold k
2. Create random polynomial P of degree k-1 with P(0) = S
3. Compute n distinct points (i, P(i)) for participants
4. Distribute points to n participants
5. Any k participants can reconstruct using Lagrange interpolation

Question 9

Error Correction for Erasures

Answer 9

1. Represent message as values of a polynomial P(x)
2. Transmit values at points x₁,...,xₙ₊ₖ
3. If k erasures occur, use remaining n points
4. Apply Lagrange interpolation to recover original polynomial
5. Extract message from P(x)

Question 10

Berlekamp-Welch Algorithm for Error Correction

Answer 10

1. Assume received values rᵢ at positions xᵢ
2. Create error locator polynomial E(x) of degree k
3. Create Q(x) = P(x)·E(x) of degree n-1+k \ n4. Set up system of n equations: Q(xᵢ) = rᵢ·E(xᵢ)
4. Solve for coefficients of Q and E
5. Compute P(x) = Q(x) / E(x)
6. Extract original message from P(x)

Question 11

Cantor’s Diagonalization Proof

Answer 11

1. Assume set S is countable
2. List elements of S as s₁, s₂, s₃, …
3. Construct element t that differs from sₙ in nth position
4. Show t must be different from every element in the list
5. Conclude t ∈ S but t is not in the enumeration
6. This contradiction proves S is uncountable

Question 12

Constructing a Bijection between N and Z

Answer 12

1. Define f: N → Z as follows:
2. f(0) = 0
3. For positive n, if n is odd: f(n) = (n+1)/2
4. For positive n, if n is even: f(n) = -n/2
5. This maps {0,1,2,3,4,5,…} to {0,1,-1,2,-2,3,…}
6. Verify f is both injective and surjective

Question 13

Proving Set Equality

Answer 13

1. Prove A ⊆ B: Show that if x ∈ A, then x ∈ B
2. Prove B ⊆ A: Show that if x ∈ B, then x ∈ A
3. Conclude A = B

Question 14

Constructing Truth Tables

Answer 14

1. Identify all atomic propositions
2. Create columns for each proposition and operator
3. List all possible combinations of truth values
4. Fill in truth values working from innermost to outermost operators
5. Read final column for the truth value of the entire statement

Question 15

Method for Strong Induction Proof

Answer 15

1. Establish base case(s): Prove P(0), P(1), etc. as needed
2. State induction hypothesis: Assume P(0), P(1), …, P(k) all true
3. Prove inductive step: Show P(k+1) follows from the hypothesis
4. Conclude P(n) holds for all required n

Question 16

Finding Minimum Spanning Tree (Kruskal’s Algorithm)

Answer 16

1. Sort all edges by weight (ascending)
2. Start with empty graph T
3. For each edge in sorted order:
   a. If adding the edge creates a cycle, skip it
   b. Otherwise, add the edge to T
4. Continue until T has n-1 edges (where n is number of vertices)

Question 17

Solving Linear Congruence ax ≡ b (mod m)

Answer 17

1. Find gcd(a, m)
2. If b is not divisible by gcd(a, m), no solution exists
3. Otherwise, divide all terms by gcd(a, m) to get a’x ≡ b’ (mod m’)
4. Find a⁻¹ (mod m’) using Extended Euclidean Algorithm
5. Compute x ≡ a⁻¹·b’ (mod m’)
6. Generate all solutions: x₀, x₀ + m’, x₀ + 2m’, …, x₀ + (gcd(a,m)-1)m’

Question 18

Chinese Remainder Theorem Implementation

Answer 18

1. Given system x ≡ aᵢ (mod nᵢ) where all nᵢ are pairwise coprime
2. Compute N = n₁·n₂·…·nₖ
3. For each i, compute Nᵢ = N/nᵢ
4. For each i, find Mᵢ where Mᵢ·Nᵢ ≡ 1 (mod nᵢ) using Extended Euclidean Algorithm
5. Compute x ≡ ∑(aᵢ·Nᵢ·Mᵢ) (mod N)

Question 19

Applying Principle of Inclusion-Exclusion

Answer 19

1. To find |A₁ ∪ A₂ ∪ … ∪ Aₙ|:
2. Start with sum of individual set sizes: ∑|Aᵢ|
3. Subtract all pairwise intersections: -∑|Aᵢ ∩ Aⱼ|
4. Add back triple intersections: +∑|Aᵢ ∩ Aⱼ ∩ Aₖ|
5. Continue alternating signs for larger intersections\n6. Final term is (-1)ⁿ⁺¹|A₁ ∩ A₂ ∩ … ∩ Aₙ|