## Description

Consider the group G = (Z≥0, +) where + is the usual integer addition. The set {0, 1} is a

generating set for G, but you can also consider other generators. Note that 0 must be present in

every generating set for G. Therefore, we do not need to explicitly state 0 — we can implicitly

understand 0 to be in every generating set. Given a generating set S ⊆ Z≥0 and an i ∈ Z≥0, we

can ask: how efficiently can we generate i using the elements in S. For example, let S = {1, 5}

1

and i = 11. You can generate 11 by the sequence 1 → 2 → 3 → 4 → · · · → 10. More efficiently,

you can generate 11 by 1 → 2 → 4 → 8 → 10 → 11. Optimally (i.e., most efficiently) you can

generate 11 by 5 → 10 → 11 or 1 → 6 → 11. In general, you can define the efficiency of your

generation by the number of times you use the + operator. Thus, the problem is:

Given a set S ⊆ Z≥0 and an element i ∈ Z≥0, produce a sequence of elements

generated from S such that you reach i most efficiently (i.e., fewest number of

times you use the + operator).

(In this lab exercise, bulk of your grade is for getting your program to work when S = {1}.

Therefore, first focus on that simple case. This will also help you get an intuition for how to

solve the more general case when S can be an arbitrary subset of Z≥0.)

0.1 Command Line Arguments

Your command line argument for this assignment is a single input file name.

1Recall that 0 is implicitly in S

1

0.2 The Input File Format

Each input file should solve one instance of the problem. The format is as follows. First you

must have an integer n which represents the number of elements of the generating set S. Then,

you provide the elements in S one after another. Finally, you provide your value of i.

You should allow your input to be in free format. Confer Lab 10 for what I mean by free

format.

You may assume that i and the largest element in S are never more than 100 and the

cardinality of S is at most 10.

0.3 Output

The output should contain the following:

1. A sequence that leads to i.

2. The number of times you needed to use the + operator to reach the value i.

As an example, consider the input:

3 1 7 13 42

Then, the output format is:

13+7=20, 20+1 = 21, 21+21 = 42

Number of times we used the + operator = 3

The output format is not strict, but it should be very easy for the human reader to get the

above two pieces of information.

0.4 Grading

There will be NO viva for this exercise. You must upload your source file by Friday (Nov 9)

night (11:55PM). Getting your program to work for S = {1} constitutes 80% of your marks.

The rest 20% will be for getting your program to work for any S.

Since there is no viva component, we will check for plagiarism very carefully. You are

allowed to discuss ideas with each other, but you must write your own program. And, more

importantly, you must not share your program with others.

Uploading into MOODLE

Your code should be written as a single .c file. You must first compress the file using gzip -c

filename.c > filename.c.gz and then the compressed .gz file must be uploaded into moodle.

A link will be set up for this purpose in moodle.

2

Your TA for this lab

CS08B031, CS10B052, CS11B001 — CS11B009 Tejas Kulkarni

CS11B011 — CS11B021 Paresh Nakhe

CS11B022 — CS11B032 Shrikant Polawar

CS11B033 — CS11B042 Sai Sreenivas

CS11B043 — CS11B053 Nishaanth

CS11B054 — CS11B063 Saurav Kant Jha

3