CompSci 260P: Week 5

Highlights

• Maximum Students Problem
  • Recursive algorithm considers skipping or using
  • Requires tracking the number of consecutive rooms used
  • Or instead assume previous room was not used, solve accordingly
• Hitting Set
  • Reduce from Vertex Cover
  • Could also probably do Set Cover
  • Reduction gets a lot messier though, as it requires sorting and mapping

Maximum Students in Non-Consecutive Rooms

• Problem: A professor is preparing a building for exams
  • The building has rooms, numbered 1 to
  • Room can hold students
  • To prevent cheating, no two consecutive rooms can be used
  • Rooms can be combined by demolishing a wall
    • At least one of the original walls must stay intact
• Goal: Find the maximum number of students that can be hosted for exams

Solution 1: Using

• Define a function :
  • Input:
    • : Current room number
    • : Number of consecutive rooms used prior to room
  • Output: Maximum number of students that can be hosted in rooms to , given

Solution 1: Base Case

• If
  • Return 0
• If
  • Return

Solution 1: Recursive Step

• Choice 1: Use room
  • Accommodate students in room
  • Recursively compute
• Choice 2: Do not use room
  • Recursively compute
• Final Result:

Solution 1: Code

def Solve(S, n):
    def MaxStudents(i, c):
        if i >= n:
            return 0
        if c == 2:
            return MaxStudents(i + 1, 0)
        use  = MaxStudents(i + 1, c + 1) + S[i]
        skip = MaxStudents(i + 1, 0) 
        return max(use, skip)
    return MaxStudents(0, 0)

• Index 0 instead of Index 1

Solution 2: Using

• Define a function :
  • Input: : Current room number
  • Output: Maximum number of students that can be tested in rooms to
  • Note: Assume is not occupied!

Solution 2: Base Cases:

• If
  • Return 0
• If
  • Return
• If
  • Return

Recursive Step:

• Choice 1: Do not use room
  • Recursively compute
• Choice 2: Use room skip
  • Accommodate students
• Choice 3: Use rooms , skip
  • Accommodate students
• Final Result: (start at room 1)

Solution 2: Code

def Solve(S, n):
    def MaxStudents(i):
        if i >= n:
            return 0
        if i == n - 1:
            return S[n - 1]
        if i == n - 2:
            return S[n - 2] + S[n - 1]
        skip = MaxStudents(i + 1)
        use = S[i] + MaxStudents(i + 2)
        demo = S[i] + S[i + 1] + MaxStudents(i + 3)
        return max(skip, use, demo)
    return MaxStudents(0)

Memoization

• Both solutions can be optimized using memoization
• Store the results of either in a table
  • Solution 1: Matrix of
  • Solution 2: Array of
• When a subproblem is encountered again, retrieve stored results
  • Solution 1: 3 solutions to retrieve from and
  • Solution 2: 3 solutions to retrieve from
• Time Complexity:

Hitting Set

• Input:
  • Set , and collection of subsets of
    • for each
  • Integer
• Output:
  • Whether there is a hitting set of size at most
• Hitting Set: Set such that contains at least one element from each
• Prove this problem is NP-Complete

Example

• Output: "Yes"
  • is a hitting set
  • and are also hitting sets

NP-Completeness Proof: NP

• Given a set of elements
• Check it is a hitting set for
  • For each verify contains an element in
  • Can be done in polynomial time

Hitting Set is NP-hard:

• Reduction from Vertex Cover
• Given an instance of Vertex Cover (a graph and an integer ):
  • For each vertex in , define an element that can be in a set
  • For each edge in , define the set containing and .
• Claim: This solves the vertex cover problem

Hitting Set: No False Positives

• Suppose is the solution to the Hitting Set
• Vertices in correspond to Vertex Cover
  • For every edge there is a set with or
  • Thus must contain either or
  • Therefore, can be made into a vertex cover

Hitting Set: No False Negatives

• Suppose is a Vertex Cover
• Elements in is a Hitting Set
  • For every set, there is an edge containing its two elements
  • is guaranteed to have it due to the nature of Vertex Cover
  • Therefore, can be made into a hitting set