## Description

1. (Greedy) Given n rods of lengths L1, L2, . . . , Ln, respectively, the goal

is to connect all the rods to form a single rod. The length and the cost

of connecting two rods are equal to the sum of their lengths. Devise a

greedy algorithm to minimize the cost of forming a single rod.

2. (Greedy) During a summer music festival that spans m days, a music

organizer wants to allocate time slots in a concert venue to various artists.

However, each time slot can accommodate only one performance, and

each performance lasts for one day.

There are N artists interested in performing at the festival. Each artist

has a specific deadline, Di

, indicating the last day on which they can

perform, and an expected audience turnout, Ai

, denoting the number of

attendees they expect to draw if they perform on or before their deadline.

It is not possible to schedule an artist’s performance after their deadline,

meaning an artist can only be scheduled on days 1 through Di

.

The goal is to create a performance schedule that maximizes the overall

audience turnout. The schedule can assign performances for n artists

over the course of m days.

Note: The number of performances (n) is not greater than the total

number of artists (N) and the available days (m), i.e., n ≤ N and n ≤ m.

It may not be feasible to schedule all artists before their deadlines, so

some performances may need to be skipped.

(a) Let’s explore a situation where a greedy algorithm is used to allocate

n performance to m days consecutively, based on their increasing

deadlines Di

. If, due to this approach, a task ends up being scheduled after its specified deadline Di

, it is excluded (not scheduled).

Provide an counterexample to demonstrate that this algorithm does

not consistently result in the best possible solution.

(b) Let’s examine a situation where a greedy algorithm is employed to

distribute n performance across m days without any gaps, prioritizing

performances based on their expected turnouts Ai

in decreasing order.

If, as a result of this approach, a performance ends up being scheduled

after its specified deadline Di

, it is omitted from the schedule (not

scheduled). Provide a counterexample to illustrate that this algorithm

does not consistently produce the most advantageous solution.

(c) Provide an efficient greedy algorithm that guarantees an optimal solution to this problem without requiring formal proof of its correctness.

3. (Master Theorem) The recurrence T(n) = 7T(n/2) + n

2 describes the

running time of an algorithm ALG. A competing algorithm ALG′ has a

running time of T

′

(n) = aT′

(n/4) + n

2

log n What is the largest value of

a such that ALG′

is asymptotically faster than ALG?

4. (Master Theorem) Consider the following algorithm StrangeSort which

sorts n distinct items in a list A.

(a) If n ≤ 1, return A unchanged.

(b) For each item x ∈ A, scan A and count how many other items in A

are less than x.

(c) Put the items with count less than n/2 in a list B.

(d) Put the other items in a list C.

(e) Recursively sort lists B and C using StrangeSort.

(f) Append the sorted list C to the sorted list B and return the result.

Formulate a recurrence relation for the running time T(n) of StrangeSort

on an input list of size n. Solve this recurrence to get the best possible

O(·) bound on T(n).

5. (Master Theorem) For the given recurrence equations, solve for T(n) if

it can be found using the Master Method. Else, indicate that the Master

Method does not apply.

(a) T(n) = T(n/2) + 2n

(b) T(n) = 5T(n/5) + n log n–1000n

(c) T(n) = 2T(n/2) + log2 n

(d) T(n) = 49T(n/7) − n

2

log n

2

(e) T(n) = 3T

n

4

+ n log

6. (Divide-and-Conquer) We know that binary search on a sorted array of

size n takes Θ(log n) time. Design a similar divide-and-conquer algorithm

for searching in a sorted singly linked list of size n. Discuss its worst-case

runtime complexity.

7. (Divide-and-Conquer) We know that mergesort takes Θ(n log n) time

to sort an array of size n. Design a divide-and-conquer mergesort algorithm for sorting a singly linked list. Discuss its worst-case runtime

complexity.

8. (Divide-and-Conquer) Imagine you are responsible for organizing a

music festival in a large field, and you need to create a visual representation of the stage setup, accounting for the various stage structures. These

stages come in different shapes and sizes, and they are positioned on a

flat surface. Each stage is represented as a tuple (L, H, R), where L and

R are the left and right boundaries of the stage, and H is the height of

the stage.

Your task is to create a skyline of these stages, which represents the

outline of all the stages as seen from a distance. The skyline is essentially

a list of positions (x-coordinates) and heights, ordered from left to right,

showing the varying heights of the stages.

Take Fig. 1 as an example: Consider the festival setup with the following

stages: (2, 5, 10), (8, 3, 16), (5, 9, 12), (14, 7, 19). The skyline for this

festival setup would be represented as: (2, 5, 5, 9, 12, 3, 14, 7, 19), with

the x-coordinates sorted in ascending order.

(a) Given the skyline information of n stages for one part of the festival

and the skyline information of m stages for another part of the festival,

demonstrate how to compute the combined skyline for all m+n stages

efficiently, in O(m + n) steps.

(b) Assuming you’ve successfully solved part (a), propose a Divide-andConquer algorithm for computing the skyline of a given set of n stages

in the festival. Your algorithm should run in O(n log n) steps.

9. (Dynamic Programming) Imagine you are organizing a charity event

2 8 10 12 14 16 19

3

5

7

9

5

Figure 1: Example of festival stage setup.

to raise funds for a cause you care deeply about. To reach your fundraising goal, you plan to sell two types of tickets.

You have a total fundraising target of n dollars. Each time someone

contributes, they can choose to buy either a 1-dollar ticket or a 2-dollar

ticket. Use Dynamic Programming to find the number of distinct

combinations of ticket sales you can use to reach your fundraising goal of

n dollars?

For example, if your fundraising target is 2 dollars, there are two ways

to reach it: 1) sell two 1-dollar tickets; 2) sell one 2-dollar ticket.

(a) Define (in plain English) subproblems to be solved.

(b) Write a recurrence relation for the subproblems

(c) Using the recurrence formula in part b, write pseudocode using iteration to compute the number of distinct combinations of ticket sales

to reach fundraising goal of n dollars.

(d) Make sure you specify base cases and their values; where the final

answer can be found.

(e) What is the runtime complexity of your solution? Explain your answer.

10. (Dynamic Programming) Assume a truck with capacity W is loading.

There are n packages with different weights, i.e. (w1, w2, . . . wn), and all

the weights are integers. The company’s rule requires that the truck

needs to take packages with exactly weight W to maximize profit, but

the workers like to save their energies for after work activities and want to

load as few packages as possible. Assuming that there are combinations

of packages that add up to weight W, design an algorithm to find out

the minimum number of packages the workers need to load.

(a) Define (in plain English) subproblems to be solved.

(b) Write a recurrence relation for the subproblems

(c) Using the recurrence formula in part b, write pseudocode using iteration to compute the minimum number of packages to meet the

objective.

(d) Make sure you specify base cases and their values; where the final

answer can be found.

(e) What is the worst case runtime complexity? Explain your answer.