## Description

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