Assignment 3- Diet Helper

Computer Science 320SC –
Programming Assignment 3

Requirements
This third assignment lets you get familiar with greedy and divide-and-conquer design and development.
There are two algorithms/programs required. It is worth 5% of your total course marks. Please try and
test with your own generated input cases before submitting to the automated marker.
Task 1: Diet Helper
One of the lecturers is going on a carrot and celery diet. Depending on the season a carrot stick and a
celery stick can be consumed in m and n seconds, respectively. Furthermore, this diet has an allocated
eating period of t seconds for a given day to consume food. We want to know the maximum number
of sticks that can be consumed in t seconds. Your lecturer doesn’t want to waste time not eating, so
prefers to have the combination of carrot and celery sticks take up as much of the t seconds allocated.
He is also not allowed to eat part of a food item (once a stick has been bitten into he must have enough
time to finish it).
Since the values of m, n and t change daily we want a program to help him decide the maximum number
of sticks that could be eaten, where we first minimize the number of seconds spent not eating.
Your input will be a sequence of daily diet triples 1 ≤ m, n, t ≤ 1000000, given on a line separated by
one space, and terminated by a line containing m = n = t = 0, which isn’t processed.
Sample Input:
3 2 10
5 41 112
253 234 1919
0 0 0
For each diet triple (m, n, t), you should output the maximum number of carrot and celery sticks that
can be consumed provided that the maximum amount of time t
0 ≤ t is used eating. Also on the same
line print the minimum time t − t
0
that is wasted to get this count (separated by one space).
Sample Output for program name diet.ext
5 0
8 0
8 9
1
Task 2: k-selection
You have been asked by the obnoxious and impatient statistician to write a program that given a data
set (an array of 32-bit integers of size n ≤ 108
) and an integer k in the range 1..n will output the k-th
smallest element. If a long delay occurs when the program is running, this person will start yelling
serious abuse at you (but won’t destroy your career outright). He is just as likely to give you data that
is already sorted as data that is completely random-looking, and there may be many duplicate entries
in the data.
Input format: The first line gives the value of n followed by the value of k. The next n lines give the
integers in the array, one per line. This repeats and a case where n = 0 terminates the file.
Sample Input:
2 2
1
3
5 1
5
8
4
12
10
5 3
7
1
6
8
9
0 0
Sample Output for program name select.ext
Data set 1: element 2 is 3
Data set 2: element 1 is 4
Data set 3: element 3 is 7
Submission Procedure
For this assignment, there are two marks awarded for Task 1 and three marks awarded for Task 2,
where Task2 has an easy test case (one mark) and harder test case (two marks). Submit your program
solutions to https://www.automarker.cs.auckland.ac.nz. There will be a penalty of %20 (per test
case) if you exceed the submission limit of 8 for Task 1 and submission limit of 6 for each of the two
cases for Task 2 (applied if you eventually solve them).
2