Assignment 5
COMP 2080: Analysis of Algorithm
June 29, 2018
Due: July 6 11:59 PM
There are di erent multiple testsets for the following coding problems. Marks will be awarded accord-
ing to the testsets passed. Passing a testset will require matching the speci c output for an inputset
and having an execution time below a certain threshold. If there are 5 testsets and you passed 3 of
them then the nal score will be a minimum of 3.
Each program need to have runtimes < n2 to satisfy the runtime e ciency of some of the testsets.
The following things are required before submission:
The input of the programs need to be a text le passable by an argument.
public static void main(String[] args) {
Scanner sc = new Scanner(new File(args[0]));
...
}
All 4 .java les need to be zipped having the name representing the student ID (7788942.zip)
Do not include the class les or the project information
No need to handle the boundary conditions from the constraints
Check with multiple inputs whether the solution is correct
Do not consider the input reading complexity
Happy coding!
Question 1: The power is yours
Given three Integer numbers a;b; and N, compute pow(a;b)modN applying divide and conquer
methodologies.
Input:
n specifying the test cases
n line where each line with a;b;N three inputs
Output: Each line with the output value of pow(a;b)modN
Constraints:
1. 1 n 1000
2. 1 a;b;N 105
1
Input Output
3 13
3 18132 17 2
17 1765 3 36123
2374859 3029382 36123
Question 2: Understanding Orders
Given an array A of size N, nd the number of ordered pairs (i;j) such that i < j and A[i] < A[j].
Input:
First line contains one integer, N, size of array.
Second line contains N space separated integers denoting the elements of the array A.
Output:
Print the total number of ordered pairs (i;j) such that i < j and A[i] < A[j].
Constraints:
1. 1 N 106
2. 105 A[i] 106
Input Output
5 6
4 1 3 2 5
The 5 cases are: 4 < 5, 1 < 3, 1 < 2, 1 < 5, 3 < 5, 2 < 5.
Question 3: June and her Chocolates
June is a kindergarten teacher who wants to give some chocolates to the children of her class. All
the children are well behaved and sits in a line. However, each of them has a numeric rating score
according to their class performance. June wants to give at least 1 candy to each child.
However, if two children sit next to each other, the one with the higher rating must get more
candies. But June wants to minimize the total number of candies she needs to buy. For example, if
her students’ ratings are f4;6;4;5;6;2g, she can give the following minimal amounts: f1;2;1;2;3;1g.
She must buy a minimum of 10 candies.
Input:
The rst line contains an integer,n, the size of array A.
Each of the next n lines contains an integer A[i] indicating the rating of the student at each
position i.
Output:
The minimum number of candies June needs to buy
Constraints:
1. 1 n 105
2. 1 arr[i] 105
June can give in the following order: f1;2;1;2;1;2;3;4;2;1g
Input Output
Question 4: Shades for Summer 2
Our cool boy again goes for new shades for the summer. He goes to a shop which contains N shades,
where the prices are given in an array A. The price of ith shade is A[i]. This time we know how much
money m he has to spend to buy new shades and he likes to maximize this number.
For example, if A = f1;6;12;2;3;5;6;7g are the prices of the new shades at the store, and our boy
has 11$ in his pocket. Now, he can only buy 4 shades with pricesf1;2;3;5gas it totals to 11$. So the
output will be 4.
Input:
First line contains N which denotes the total number of shades available and the total money m
Next line contain N integers which construct the A
Output:
Output the total number of shades that our cool boy can buy.
Constraints:
1. 1 N 105
2. 1 A[i] 106
3. 1 m 107
Input Output
7 50 4
1 12 5 111 200 1000 10
Source Source of these problems will be disclosed after the deadline.