CS2040S: Data Structures and Algorithms Solution

Problem Set 2
Overview. This problem set consists of two problems closely connected to binary search.
The first is an easy optimization problem: you are given an array, and your goal is to find the largest element in the array.
The second is a more challenging load balancing problem: you have a collection of tasks and a collection of processors, and your goal is to efficiently assign a sequence of tasks to each processor.
Code Quality Policy. You are expected to practice good coding practices when working on the problem sets. In general, your TAs will provide you with feedbacks on how to improve your code quality. Additionally, Your TAs also reserve the right to penalize your code, should they come across code that has been intentionally obfuscated. If you have any queries regarding this, do check with your TAs.
Problem 1. Optimization
Here’s a simple problem—find the maximum element in an array! Implement the following function:
public static int searchMax(int[] dataArray)
Given an array dataArray where every element is unique, return the value of the largest integer in the array.
There is one additional piece of information you need: the data in the array increases (or decreases) from one end until it reaches its maximum (or minimum), and then decreases (or increases) until it reaches the other end. The change in direction occurs at most once in the array.
More precisely, if the data array has size n, there is some index j such that the subarray dataArray[0..j] is sorted (either increasing or decreasing) and the subarray dataArray[j..n-1] is sorted (either increasing or decreasing).
For example, the following are possible input arrays:
[2, 5, 7, 9, 15, 23, 8, 6]
[73, 42, 13, 5, -17, -324]
[100, 42, 17, 3, 8, 92, 234]
Use the most efficient algorithm you can. State the running time of your algorithm in terms of n (where n is the size of the dataArray).
If you are given an invalid input, you should return the value 0 (although in real life, you would typically throw an error). For the purpose of this question, do note that invalid inputs does not include arrays that violate the rule about changing direction at most once. You do not need to check that the array follows this rule, as it defeats the efficiency of performing binary search.
To think about (Optional) What if all the elements in the array are not unique? How efficiently can the problem be solved then? What is the worst-case example?
Problem 2. Balancing the Load
Your boss, Paul R. Allel, storms into the office, shouting, “The system is too slow! Our users are sending me hate-tweets! Make it faster!” And then he stormed out again. What is he upset about? Well, right now, every day, your system churns through calculating dense matrix inverses for secret government agencies. And recently, there is so much work that one server just can’t keep up. So you decide to parallelize: by buying more servers, you should be able to perform the computation faster!
Today, you have n jobs, stored sequentially on disk, in order. Each job has a size: jobSizes[i] is the size of job i. The maximum individual job size M = θ(n).

The total load of a processor is the sum of sizes of the jobs allocated to the processor, e.g., in the above case the load of processor 2 is:
jobSizes[4] + jobSizes[5] + jobSizes[6] + jobSizes[7]
Your goal in this problem is to find an assignment of jobs to processors in a manner that minimizes the maximum load on any processor (that is, consider the processor with the highest load — we want the load on this processor to be as small as possible). In fact, for today, we will just compute the minimum possible load.
Problem 2.a. The first step is to figure out, given a specific target load, whether p processors is sufficient. Design and implement the most efficient algorithm you can think of for the following function:
static boolean isFeasibleLoad(int jobSizes[], int queryLoad, int p)
Use the most efficient algorithm you can. State the running time of your algorithm in terms of n and M (where n is the number of jobs and M is the maximum individual size of jobs).
Examples:
jobSizes = [1, 2, 3], queryLoad = 3, p = 2 : Feasible (p1 takes [1, 2], p2 takes [3]) jobSizes = [1, 2, 3], queryLoad = 1, p = 2 : Not feasible
Problem 2.b. The second step is to determine the minimum achievable load. Suppose we have 5 processors and jobs with the following sizes:
[1, 3, 5, 7, 9, 11, 10, 8, 6, 4]
To ensure that the maximum load on any one processor is as small as possible, we can assign the jobs to the 5 processors this way:
[1, 3, 5, 7] [9] [11] [10] [8, 6, 4]
Notice that the maximum load on any processor is 18 — that’s the load on the last processor (8 + 6 + 4). With only 5 processors, this is the minimum achievable maximum load on any one processor, we can’t go lower than this!
Design and implement the most efficient algorithm you can think of for the following function:
static int findLoad(int jobSizes[], int p)
The function should return the minimum possible load for the given jobSizes and p.
Use the most efficient algorithm you can. State the running time of your algorithm in terms of n and M (where n is the number of jobs and M is the maximum individual size of jobs). Explain how you obtained the running time in one sentence.
Hint 2: Notice two facts about the “optimal” solution: its maximum load has to be at least as big as the biggest individual job, and its maximum load has to be at least as big as the sum of the job sizes divided by p. Using this fact, if you can show that the “optimal” solution is at least 1/2 of the answer returned by your greedy algorithm, then it is correct.
Hint 3: Can you give a bound on the cost of the greedy solution (from Hint 1) in terms of the biggest individual job size and the sum of the job sizes divided by p?
Hints for PS2
My code compiles and runs properly offline, but it does not work after uploading it to coursemlogy. There are a few possible scenarios:
1. Check that you have not included any unnecessary package imports
2. Check that you have included all helper functions needed by your code
3. Check that you have not included any unicode characters (e.g. −)
What are considered as invalid inputs? Depending on the context of the question, some invalid inputs can include empty arrays, negative numbers and so on.