Description
Problem Definition 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
