Skip Navigation CECS Home | ANU Home | Search ANU

COMP2300, COMP6300

Semester 1, 2009: Assignment 1

Deadline: 09:00 on Tuesday 31 March

(Please report any errors, mistakes and ambiguities to the course lecturer)

---

This assignment is worth 12% of your total course mark. It will be marked out of 48 as indicated below.

---

The estimated time we expect you to spend on this assignment is around 12 hours in total (1 hour per 4 assignment marks).

Submission

This assignment must be submitted electronically. This can be done using the submit comp2300 ass1 ... command. (or the submit comp6300 ass1 ... command, if you have a COMP6300 enrollment).

You should submit a separate file for each part of the assignment you are required to complete. The file names which you should use (and the only ones that will be accepted by the submit command) are:

    fun.txt
    shuffle.c
    shuffle2.c

As an example of what you should do

    submit comp2300 ass1 shuffle.c

All files submitted must include, at the beginning, a completed preamble. The proforma for this can be found in the files:

      /dept/dcs/comp2300/public/standard_preamble.txt

You have to copy the preamble from this files into the top of each file you intend to submit, and then complete your details. By submitting a file containing a completed preamble, you are making a declaration about the work you have submitted (see the text of the declaration in the preamble files. If you need to modify the text, e.g. you did in fact receive substantial assistance from another student, you should modify the text to say so).

Any file submitted without a completed preamble will be rejected without being marked.

Note you can submit any file multiple times, including after the deadline has expired. Note that if you submit any file after the deadline your entire submission will be considered as late and will attract a late penalty.

Extensions

See http://cs.anu.edu.au/student/comp2300/assessment.php.

Late Penalties

Late penalties are as follows

How Late	Penalty from 60 Marks
less than 1 hour	-1
between 1 and 6 hour	-2
between 6 and 24 hours (1 day)	-4
between 24 and 48 hours (2 days)	-8
between 48 and 72 hours (3 days)	-16
between 72 and 96 hours (4 days)	-32
more than 96 hours (4 days)	-64 (forget it!)

Note: late penalties apply even if you submit just one file after the deadline.

Plagiarism

See http://cs.anu.edu.au/student/comp2300/assessment.php.

---

Part 1 - Fundamental Concepts [18 marks]

Please show enough working to demonstrate how each answer is derived. Failure to do so may result in you being awarded partial or no marks for the question concerned (i.e. writing only the correct answer will give you NO marks). See the sample answers for Tute/Lab 01 as a guideline. Submit your answers as plain text in a file called fun.txt (make sure you have the completed preamble at the beginning).

1. Let x be the number whose decimal representation is the first digit of YOUR ANU student number multiplied by the second and third digits and then added to the last four digits. For example: stud_number=u1234567 -> x = 1*23 + 4567 = 4590.

   1.A What is the base 10 representation of x? [-2 marks if not given or wrong!!]

   1.B What is the base 16 representation of x? [1 mark]

   1.C What is the binary representation of -x in a 16-bit word, if the value is encoded as a two's complement number? [2 marks]

   1.D What is the bit pattern of x (x.0 (base 10) to be precise) when stored as an IEEE single precision floating point number. Represent the resulting 32-bit pattern as an 8 digit hexadecimal number. [3 marks]

   1.E Let x' be the number derived from taking the hexadecimal number from 1.B and padding digits O (base 16) to the right until the result is 8 hex digits long (and the leftmost digit is non-zero). For example, if x = 15f5_16, x' = 15f50000_16. Write x' in hexadecimal and binary. Interpreting the latter as a bit pattern for 32-bit floating point, write the corresponding value in binary (in form +/- 1.m * 2^e, where m is in binary and e is in decimal), and convert this to decimal (in form +/- d.m' * 10^e', where m' and e' are in decimal, and 1≤d≤9). A calculator may be used in the final stage (give your answer correct to 4 decimal places). [4 marks]

2. Let yyyy represent the 4 binary digits of the remainder of the last 2 digits of YOUR ANU student number when divided by 16. For example: stud_number=u1234567 -> 67 % 16 = 3_10 -> yyyy=0011 . Assume you are using an 8-bit computer. What would be the binary AND decimal results obtained from the following 2-complement operations? (show working for decimal to binary conversions and indicate if overflow occurred).

   2.A	0011 0101 +0010 yyyy
   2.B	1001 yyyy +1011 1010
   2.C	1110 0110 - 0011 yyyy
   2.D	0100 yyyy - 1010 1110

   [6 marks]

3. given the C code:

     int i, n;
     ...
     char c = 0;
     for (i=0; i<n; i++)
       c++; // increment c
     printf("%d\n", c);
   

   what number is output when (a) n = 127, (b) n = 128, (c) n = 255 and (d) n = 256. Explain your answers. [2 marks]

---

Part 2 - Simple C Programming [16 marks]

(*** minor corrections/additions 24/03 ***)

Over this course, we will study the algorithm which shuffle a vector (array of integers). This is a relatively simple algorithm but cam show interesting behavior when executed on a modern computer with a memory hierarchy, which we will investigate in future assignments. Furthermore, shuffle operations are used in algorithms such as the Fast Fourier Transform and bitonic sorting. Shuffles are also a kind of permutation and have some interesting mathematical properties.

A 2-way shuffle of a deck of cards involves cutting the deck into 2 (even) `cuts' and interleaving cards in the the top (perfectly) with those in the second. In the out-shuffle, this is done in a way so that the top card of the top cut remains on the top, and the bottom card of the bottom cut remains on the bottom. This is illustrated nicely in Wikipedia.

On a computer, the deck can be represented by an integer array. Furthermore, this can be generalized to a k-way out-shuffle, where the array is split into k even cuts, consecutively numbered as 0, 1, 2, ..., k-1. The shuffled array is produced by taking the remaining top elements of each cut, in a round-robin order cycling over cuts 0, 1, 2, ..., k-1, and placing these, in order, into the shuffled array.

For example, for k=4, n=16, and an original array of:

    0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15

the cuts are at indices 0, 4, 8 and 12. Hence, the shuffled array would be:

    0    4    8   12    1    5    9   13    2    6   10   14    3    7   11   15

Without loss of generality, we can make the restriction 1 ≤ k ≤ n (for k > n, the shuffle is an identity operation). For the moment, we will also assume that n is a multiple of k, for the sake of simplicity.

The program shuffle.c will be the first and simplest prototype (indeed, simple enough to translate into PeANUt assembler, which you will do in Assignment 2). It will use basic control structures, a simple function with parameters, simple arrays, and I/O via printf() and scanf(). The program:

1. statically allocates storage for an int array, sufficient for n<=64 (any other storage required for the shuffle is also statically allocated).
2. prints an introductory message, which prompts for n and k, and inputs the values of n and k. It can be assumed that two valid non-negative integers can be scanned from the standard input.
3. checks that n≤64; if not, it exits with an error message.
4. checks that n is a multiple of k. If not, it exits with an error message.
5. initializes the ith value of the array to i.
6. prints the array, with each entry printed (in order) with a " %4d" format, with 16 entries per line of output. This is preceded by a message signifying that this is the initial array.
7. performs the shuffle. The shuffled array may be in a separate storage array, or separate storage may be used to hold elements temporarily. Note that this step must perform explicit array element manipulations.
8. prints the shuffled array as per step 6, but preceded by a message signifying this is the shuffled array.

You should compile your program using the command gcc -Wall -o shuffle shuffle.c.

The printing of the array should be performed in a separate function (with the array address and n passed as parameters). Otherwise there are no constraints on how you implement the above steps, except that your program's output should match exactly that produced by the reference version of the program /dept/dcs/comp2300/public/ass1/shuffle. i.e. this program tells you the exact output messages etc that your program should produce. The command:

strings /dept/dcs/comp2300/public/ass1/shuffle

may be useful in getting the output messages correct; note that there are no tabs or trailing spaces.

By running the reference program followed by your own after each other in a command tool, it should be possible to spot most errors in formatting.

You cando a final check for correctness with the aid of the Unix sdiff utility:

echo "16 4" | ./shuffle > out1
echo "16 4" | /dept/dcs/comp2300/public/ass1/shuffle > out2
sdiff -s out1 out2

If the above sdiff command produces no output, then the output of your program and the reference version are identical (equivalently, you could check if the exit status of the above sdiff command is 0. For bash, use echo "sdiff exit status="$?, or, for tcsh, use echo "sdiff exit status="$?, immediately afterwards). The output of the above sdiff -s is a side-by-side comparison of the lines in your output (on the left) to that of the reference program (on the right). It will print the lines that are different (separated by a `|'), added (`>') or removed (`<'). You may need a widened command tool to see the output clearly.

Note that you should remove any trailing spaces from output messages ( you could check for these by loading out1 into a text editor, and moving the cursor to the end of each line), and do not use tabs. Closer to submission time, you may also use the previewAutoMark ass1 command to check your output format. Note that this will only test your program on a sample of the tests that will be used in the actual marking.

Your program should be written with good programming style (and so should not produce any warnings when compiled with the -Wall option!). I.e. it should be well commented, so as to enable the reader (this includes the tutor/marker!) to understand how it works. In particular, all functions (including main() should have a comment explaining what the function performs, as should all significant variables. Identifiers should be meaningful (e.g. MAX_SIZE rather than M), any constants should be named rather than hard-coded, and you are encouraged to use a coding style similar to that displayed in the examples given in lectures. Your program must compile and run correctly on the default gcc in DCS Linux Labs (use partch.anu.edu.au for remote access).

Note that your program will be automatically compiled and run using various test cases. The ability of your program to reproduce the required behavior will contribute to about 50% to your marks. The remaining 50% of the marks will be awarded based on inspection of your code (completeness, coding style).

As you will be translating shuffle.c into PeANUt in Assignment 2, keep it simple! That refers particularly to program structure (especially functions are hard to implement in assembler) and the use of external library calls - there will only be limited forms of printf() and scanf() available in PeANUt.

Finally, if you have trouble getting the shuffle correct for arbitrary values of k, try to concentrate on 2 or powers of 2, as these are the most important!

Part 3 - More Advanced C Programming [14 marks]

COMP2300 Version

The above program only performs a shuffle on an array of limited size. Given our aim of studying the memory hierarchy behavior of the shuffle computation, we will need to extend it to perform shuffles on very large arrays. However, it does not make sense to always print out the array if it is very large. When we do print it, it can be useful to be able to specify the number of elements to be displayed in each row of output. When we do not print the result, we should have some way of (at least partially) checking that the shuffle was performed correctly. This requires in turn a number of changes to be made.

• the program should get the values of various parameters from the command line (standard for C programs). The validity of the command line parameters should be checked.
• the printing will be made optional, only when the -p option is specified on the command line. We will also make the printing more flexible by specifying nPrRow, the number of elements to be displayed in each row of output (e.g. when n = 52, it is more readable to have nPrRow=13).
• storage for all arrays required by the shuffle will be dynamically allocated (on the heap).
• the restriction that k is a multiple of n is not necessary and will be dropped (for COMP6300). In this case, the first n % k cuts get an extra card.
• some checks for correctness (checksum matching and buffer over-write) will be performed.

Implementing this program will extend your C abilities in manipulating strings (and arrays of strings), command line parameters and ther exit status, the assert statement, dynamically allocated memory, and more complex control structures.

You should only proceed with this part if your program shuffle.c is working satisfactorily. None or very few marks will be allocated for this part if it is not!. You may use your code from shuffle.c as a starting point for shuffle2.c.

The program:

1. processes the command line parameters according to the usage: shuffle2 [-p nPrRow] [-P k0] n k, with the default value of k0 = 1 and the constraints k,k0 > 0 and n ≥ 0. This means the program can accept an optional parameter -p (which must be followed by an integer nPrRow), followed by the optional parameter -P (which must be followed by an non-negative integer k0). These are followed by a (non-negative) integer n and a positive integer k. Valid examples include:
   shuffle2 4 2 ; shuffle2 -p 4 8 4; shuffle2 -P 2 8 2
   The program should print out a `usage' message and exit with a status of 1 if the parameters are invalid. Invalid examples include:
   shuffle2; shuffle2 -p 4; shuffle2 -x 4 1; shuffle2 4 -1
   Note that your program may treat as valid or invalid the cases where the options are repeated or out of order. Your program may assume that, where integer values are expected, valid numbers were entered.
2. prints an introductory message, echoing the shuffle parameters.
3. dynamically allocates storage on the heap any arrays used to perform the shuffle. An assert statement should be used to check whether the allocation succeeded (it might not if a sufficiently large value of n is given). The storage should be deallocated before the program exits (and any errors found by the MCheck library, such as buffer over-writes, be corrected!).
4. initializes the ith value of the array to i.
5. if k0 > 1, performs a k0-way (pre-)shuffle of the array.
6. if nPrRow > 0, prints the (pre-shuffled) array, with each entry printed (in order) with a " %4d" format, with nPrRow entries per line of output. This is preceded by a message signifying that this is the initial array.
7. performs the k-way shuffle.
8. conditionally prints the shuffled array as per step 6, but preceded by a message signifying this is the shuffled array.
9. outputs a message determining if the checksums of the array(s) before and after the k-way shuffle match. The checksum is computed by summing all array elements. The program exits with an exit status of 2 if the checksums mismatch. Note that if your program does not handle the case where n % k != 0 (it is not expected to at this point), the check will probably fail.

You should compile your program using the command gcc -Wall -o shuffle2 shuffle2.c -lmcheck.

Similarly to before, your program's output should match exactly that produced by the reference version of the program /dept/dcs/comp2300/public/ass1/shuffle2. Thus, running this program can be used to determine the exact format of output messages etc. The reference version can also be used to resolve any ambiguity (but not inconsistency! - contact the lecturer if you think you find one) in the above specification.

Coding style and marking requirements for this part are as per Part 2. It is permissible to use global variables to record the values of command line parameters.

Hints:

• you need to include at the top of your program stdlib.h for the dynamic memory allocation libraries (as well as exit()). You also need to include assert.h.
• to begin with, it is recommended to implement the command line parameter processing and dynamic array allocation code first. If you run out of time, at least you will get some credit for getting that far!
• it makes sense to put your code to perform the shuffle in a function, so it can be used for the pre-shuffle and the main shuffle.

For an optional bonus mark (1 each):

• extend step 1 to treat as valid the cases where the options are repeated or out of order. If an option is repeated, the value from the last time should be used. (This is the standard convention for processing command-line parameters).
• check for invalid numbers where integers were expected in the command line. The action should be as for other errors in the command line.
• get the program working properly for the case n % k != 0.

COMP6300 Version

COMP6300 students should implement the COMP2300 version above, but getting the case n % k != 0 working is mandatory in the sense that it is worth 2 compulsory marks, rather than a bonus mark.

Copyright | Disclaimer | Privacy | Contact ANU