HW 3

Problem 1

Provide binary search algorithm that takes a sorted list of strings and finds a specific string x. What is the runtime of your algorithm?

Solution:

def binary_search(arr, x):
  """
  Performs a binary search on a sorted list of strings.
 
  Args:
    arr: The sorted list of strings.
    x: The string to search for.
 
  Returns:
    The index of the string if found, otherwise -1.
  """
  low = 0
  high = len(arr) - 1
  while low <= high:
    mid = (low + high) // 2
    if arr[mid] == x:
      return mid
    elif arr[mid] < x:
      low = mid + 1
    else:
      high   
 = mid - 1
  return -1 

Problem 2

What is the runtime of an algorithm that sorts n strings?

Solution:

• Quick sort
  • is $O(nlogn)$
  • but since the comparisons between two string is $O(m)$ where $m$ is the length of string
  • So total time wold be $O(m\cdot nlogn)$

This basic pattern is then repeated for all the other sorts because when we compare numbers the comparison time is $O(1)$ which is not true in this case, so we multiply my $m$

Problem 3

Given two integers $x$, $y$ such that $x$, and $y$ are $n$ digits long each, for example if 202 is 3 digits long. Provide a divide and conquer algorithm based on the idea that

Given $X=X_L{X}_R$ where $X_L=X[\mathrm{1..}\frac{n}{2}]$ and $X_R=X[\frac{n}{2}+\mathrm{1...}n]$ and similarly you can breakup $Y$

Then $X\ast Y=(X_L\cdot 10^{\frac{n}{2}}+X_R)(Y_L\cdot 10^{\frac{n}{2}}+Y_R)$

Solution:

def multiply(x, y):
  n = number of digits in x #(or y, as they have the same length)
 
  if n == 1:
    return x * y
 
  # Calculate the midpoint for splitting
  mid = n / 2
 
  # Split x and y into halves
  XL = x / 10^mid 
  XR = x % 10^mid
  YL = y / 10^mid
  YR = y % 10^mid
 
  # Recursive calls
  P1 = multiply(XL, YL)
  P2 = multiply(XL, YR)
  P3 = multiply(XR, YL)
  P4 = multiply(XR, YR)
 
  # Combine the results
  return P1 * 10^n + (P2 + P3) * 10^(n/2) + P4 

Problem 4

Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

1. Greedy Approach This approach is greedy because it makes the locally optimal choice at each step. Instead of considering the global picture or future consequences, it focuses on selecting the activity that starts last among the compatible activities at the current decision point. This “last-to-start” strategy aims to maximize the remaining time for potentially scheduling other activities later. 2. Proof of Optimality Let’s prove that this “last-to-start” greedy approach produces an optimal solution for the activity selection problem. We’ll use an exchange argument.

• Assume an optimal solution O exists that is different from the greedy solution G.

• Let a_i be the first activity in O that differs from G. This means G chose a different activity, a_j, where a_j starts later than a_i (because G always picks the last to start).

• Exchange a_i with a_j in O to create a new solution O’.

• Since a_j starts later than a_i and both are compatible with the activities scheduled before them, replacing a_i with a_j won’t create any conflicts. Therefore, O’ is still a feasible solution.

• O’ is also an optimal solution. O’ has the same number of activities as O because we simply swapped one activity for another. Since O was assumed to be optimal, O’ must also be optimal.

• Contradiction. We can repeatedly apply this exchange argument to replace all activities in O that differ from G, ultimately transforming O into G without losing any activities. This contradicts our initial assumption that O was an optimal solution different from

• Conclusion: The “last-to-start” greedy approach always yields an optimal solution for the activity selection problem. This is because any optimal solution that differs from the greedy solution can be transformed into the greedy solution by a series of exchanges without losing any activities.

  • also this is essentially if we flipped the first example we went over in class it the same result.

Problem 5

Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities.

Provide examples to show that the following greedy approaches do not always produce an optimal solution:

1. Selecting the activity of least duration from among those that are compatible with previously selected activities.

2. Always selecting the compatible activity that overlaps the fewest other remaining activities.

3. Always selecting the compatible remaining activity with the earliest start time.

Solution:

Example for Approach 1: Selecting the Activity of Least Duration

Given Activities:

Activity	Start	Finish	Duration
A	1	4	3
B	3	5	2
C	0	6	6
D	5	7	2
E	8	9	1

Applying the Least-Duration Strategy:

1. Select Activity E (8-9): Duration 1.
2. Select Activity B (3-5): Next shortest duration among compatible activities before time 8.
3. Activities Selected: B and E.

Total Activities Selected: 2

Optimal Solution:

• Select Activities A (1-4), D (5-7), and E (8-9)

Total Activities Selected: 3

Conclusion: Selecting activities based on least duration does not guarantee a maximum-size set.

---

Example for Approach 2: Selecting the Activity That Overlaps the Fewest Other Remaining Activities

Given Activities:

Activity	Start	Finish	Overlaps With
A	1	4	B, C
B	2	5	A, C, D
C	3	6	A, B, D
D	5	7	B, C
E	6	8

Calculating Overlaps:

• Activity E: Overlaps with 0 activities.
• Activities A, B, C, D: Overlaps with 2 or 3 activities.

Applying the Fewest-Overlaps Strategy:

1. Select Activity E (6-8): Overlaps with 0 activities.
2. Select Activity D (5-7): Next fewest overlaps (2 overlaps).
3. Cannot Select A, B, or C: They overlap with already selected activities.

Total Activities Selected: 2

Optimal Solution:

• Select Activities A (1-4), D (5-7), and E (6-8)

Total Activities Selected: 3

Conclusion: This strategy fails to find the maximum-size set.

---

Example for Approach 3: Selecting the Activity with the Earliest Start Time

Given Activities:

Activity	Start	Finish
A	1	4
B	3	5
C	0	6
D	5	7
E	8	9

Applying the Earliest Start Time Strategy:

1. Select Activity C (0-6): Earliest start time.
2. Next Compatible Activities: Only Activity E (8-9).
3. Select Activity E (8-9).

Total Activities Selected: 2

Optimal Solution:

• Select Activities A (1-4), D (5-7), and E (8-9)

Total Activities Selected: 3

Conclusion: Selecting activities based on earliest start time does not yield a maximum-size set.

---

Final Conclusion:

These examples demonstrate that not all greedy strategies guarantee an optimal solution for the activity-selection problem. The classic greedy algorithm that always selects the next activity with the earliest finish time does produce an optimal solution.