WRIGHT STATE UNIVERSITY Department of Computer Science and Engineering CS7200:  Algorithm Design and Analysis Spring 2021                                          Midterm (30 pts [Stable Matching Problem: 4 + 4 + 1 + 1 pts] Consider an instance of the stable marriage problem with the priority lists:   Albert Diane Emily Fergie Bradley Diane Emily Fergie Charles Diane Emily Fergie   Diane Albert Bradley Charles Emily Albert Charles Bradley Fergie Charles Bradley Albert   Is {Albert-Diane, Bradley-Emily, Charles-Fergie} a stable matching? If yes, then provide an informal justification

WRIGHT STATE UNIVERSITY
Department of Computer Science and Engineering

CS7200:  Algorithm Design and Analysis

Spring 2021                                          Midterm (30 pts

[Stable Matching Problem: 4 + 4 + 1 + 1 pts]

Consider an instance of the stable marriage problem with the priority lists:

1. Is {Albert-Diane, Bradley-Emily, Charles-Fergie} a stable matching? If yes, then provide an informal justification. If no, provide a “witness” pair that causes instability.

(b) Determine man-optimal and woman-optimal solutions.  

Man-optimal:

Woman-optimal:

(c)  Number of functions from the set {Albert, Bradley, Charles} to the set {Diane, Emily, Fergie} =

(d)  Number of perfect matchings from the set {Albert, Bradley, Charles} to the set {Diane, Emily, Fergie} =

1. [Greedy Algorithm: ((1+1+2) + (1+1+2)) pts]

Original Coin Exchange Problem: Given coins of denominations, say, 1, 5, 10, and 25, find the minimum number of coins that add up to a given amount of money.

1. Does the greedy algorithm provide an optimal strategy to exchange 41 cents using denominations 1, 5, 10, and 15? What is the optimal solution?

YES / NO

GREEDY SOLUTION:

OPTIMAL SOLUTION:

2. Does the greedy algorithm provide an optimal strategy to exchange 41 cents using denominations 1, 3, 9, and 14? What is the optimal solution?

YES / NO

GREEDY SOLUTION:

OPTIMAL SOLUTION:

3.  [Big-Oh, Big-Theta, Big-Omega Notation: (3*1 + 2*2 pts)]

State whether the following are true or false providing brief justification.

( = is to be interpreted as belongs to.)

1. (3 n³) + (10 n² log₂ n²) = O(n³ log₂ n)    

 TRUE / FALSE

2. (n log₁₀ 2) + (10 (n / log₂ n)) = O(n / ln n) 

 TRUE / FALSE

3. (n

   

    ln n^0.5) + (n

   

     log n²) = Q(n

   

    log n) 

 TRUE / FALSE

4. 2ⁿ + eⁿ + 10^n/5 = W(2ⁿ)

TRUE / FALSE

5. 2^log₂ⁿ + e^{ln n} + 10^log₁₀ⁿ = Q (n)

(Subscript of log is the base (e.g., 2, e, 10).)

 TRUE / FALSE

4) [Divide and Conquer:   5 pts]

An odd-length array A[1...2n+1] of distinct numbers is bouncy if

 A[1] > A[2] < A[3] > A[4] < ...> A[2n] < A[2n + 1].

The inequality constraints are required only of adjacent numbers.

Given an array B[1…2n+1] of distinct numbers, describe a linear-time algorithm that outputs a reordering of numbers belonging to the input array B in A[1...2n+1] such that A is bouncy. Your solution will be graded on its clarity and correctness. Base your solution on the ideas underlying Quicksort Algorithm and you may assume that Median can be computed in linear-time using Quicksort logic.