Problem Session 2 Notes

Introduction

• Instructor: Justin
• Course: 6006
• Session: Problem Session 2
• Goal: Work through example problems from previous years' homeworks and exams.

Session Structure

• Justin will be present in multiple problem sessions.
• Handwritten notes are available for reference.

Problem Overview

• There are four problems to discuss in this session:
  1. Solving recurrences using the Master Theorem.
  2. Infinity stones problem.
  3. Queue stack structure.
  4. Interaction problems.

Problem 1: Solving Recurrences

Master Theorem Review

• The Master Theorem is a tool for solving recurrences of the form:
  [ T(n) = aT(n/b) + f(n) ]
  • Variables:
    • a: number of subproblems
    • b: factor by which the problem size is reduced
    • f(n): cost of work done outside the recursive calls

Cases of the Master Theorem

1. Case 1: If ( f(n) ) is ( O(n^{ ext{log}_b a - ext{epsilon}}) ):

   • Conclusion: ( T(n) = Θ(n^{ ext{log}_b a}) )

2. Case 2: If ( f(n) ) is ( Θ(n^{ ext{log}_b a} imes ext{log}^k n) ):

   • Conclusion: ( T(n) = Θ(n^{ ext{log}_b a} imes ext{log}^{k+1} n) )

3. Case 3: If ( f(n) ) is ( Ω(n^{ ext{log}_b a + ext{epsilon}}) ) and ( a f(n/b) \leq c f(n) ) for some ( c < 1 ):

   • Conclusion: ( T(n) = Θ(f(n)) )

Example Problem

• Problem Statement: Solve ( T(n) = 2T(n/2) + O( ext{sqrt}(n)) )
  • Solution Steps:
    • Identify a = 2, b = 2, f(n) = O(√n)
    • Calculate ( n^{ ext{log}_2 2} = n^1 )
    • Compare f(n) and ( n^{ ext{log}_b a} ):
      • f(n) grows slower, so apply Case 1.
      • Conclusion: ( T(n) = Θ(n) )

Problem 2: Infinity Stones

• Problem involves finding a specific planet using binary search.
  • Key Insight: The algorithm needs to account for the infinite number of planets by doubling the index until the target is found.
  • Once a suitable range is identified, binary search can be employed.

Problem 3: Queue Stack Structure

• Design a data structure to handle operations on images:
  1. Create empty document (O(1))
  2. Import image (O(n))
  3. Display images (O(n))
  4. Move below another image (O(log n))
• Solution:
  • Use a doubly linked list for order and a sorted array for fast access.
  • Use pointers in the sorted list to track positions in the linked list.

Problem 4: Brick Blowing

• Scenario: A wolf blows over houses based on the number of bricks.
• Damage Calculation:
  • For each house, count how many to the right that have fewer bricks.
  • Use a two-finger approach to optimize counting (O(n)).
• Special condition: Identify the non-special house and adjust counting accordingly.

Conclusion

• The session covered recurrence relations, binary search applications, data structure design, and a unique algorithmic problem involving counting.
• Emphasis on understanding algorithms and the importance of clear problem definition.