Assignment 2 2025
General
General
You must read fully and carefully the assignment specification and instructions.
Course: COMP20007 Design of Algorithms @ Semester 1, 2025
Deadline Submission: Monday 26th May 2025 @ 11:59 pm
Course Weight: 20%
Assignment type: individual
ILOs covered: 1, 2, 3, 4
Submission method: via ED
Purpose
The purpose of this assignment is for you to:
Design efficient algorithms in pseudocode.
Improve your proficiency in C programming and your dexterity with dynamic memory
allocation.
Demonstrate understanding of data structures and designing and implementing a set of
algorithms.
Task 1: Feeding and breeding eels: Episode II
You are, once again, an eel in the river systems of the Kulin Nation.
Iuk is fast approaching, and so you need to reach the ocean soon so to begin the journey to the Coral
Sea for breeding. You find yourself deep within the river system, and you need to reach the ocean in
a certain amount of time or else get left behind. However, you also need to stock up on as much fat
as possible so that you are able to survive the journey to the Coral Sea. This time around, you have
not found the great feeding grounds of yesteryear, and instead you must source your food from the
lakes as you travel back to the ocean.
Travelling down rivers costs fat, but lakes contain food in them which can increase fat supplies.
In this Task, first we will solve a relaxed problem, and then modify the solution to work on a slightly harder
problem.
Part A (Code)
As an eel, you are very interested in eating as much tasty seafood as you can, but want to be at the
ocean in time for the breeding season. You know that your journey from the ocean onwards will be
difficult, and thus it would be in your best interest to have the most possible fat upon reaching the
ocean within the time constraints you face. As such, you wish to know what the best path to take to
the ocean is.
Assume that for all parts in this task, despite being an eel, you have the ability to write C code and written
responses.
Design a dynamic programming algorithm which finds the path to the ocean that gives the largest fat
retained in your body upon reaching the ocean, limited by the amount of time you have left until
breeding season happens.
Initially, assume that traversing a river always takes exactly 1 day, and as before, you lose some
fat as you traverse a river. In addition, as you do not wish to be sick from overeating, there is a
maximum amount of fat you can have at any point. Similarly, running out of food will lead to your
demise, and so you also always want to have some fat. Of course, you cannot traverse a river if your
fat will drop to 0 or below whilst traversing it, even if there is a lot of food in the lake it flows into.
You may have lakes that actually decrease the fat you have stored as well, due to evading invasive
bird species in the area.
If there are multiple paths with the same maximal fat retained, choose the one with the earliest
arrival to the ocean. Amongst the solutions that have the same fat retained and same arrival day,
choose any of them.
Your program will receive two arguments, the first argument will be the part (always A for this task)
and the second argument will be the input filename.
Input Format:
Each input file comprises four sections:
1. The first line contains four integers: (number of lakes), (number of rivers), (starting lake
ID), and (ocean lake ID).
N M S
O
2. The second line contains three integers: (initial fat units), (maximum fat stored) and (the
time limit).
K F C
3. The third line contains integers describing the fat gain at each lake:
.
N
gain[0], gain[1],…, gain[N − 1]
4. The next lines each contain three integers: , , and , indicating a directed river from lake
to lake with cost (that is, is the fat lost from travelling between and ).
M u v w u
v w w u v
Output Format:
Your program should output the maximum fat at the ocean, as well as the path taken to get there. For
example:
Max fat: 17
Path: 0, 2, 1, 3, 6
If no safe path exists that keeps the eel alive (i.e. fat never drops to or below) which reaches the
ocean before breeding season, output:
0
No path :(
You may wish to review part C before attempting this task, as your solution will have to align with what you
write in part C. Ideally, read this entire slide before beginning.
Part B (Code)
Though you were initially happy with your plan to get to the ocean, you have realised a fatal error:
namely, you cannot traverse every river in only a single day. Now assume you believe that the time
it takes to traverse a river is equal to the fat lost in the river.
You wish to develop a new dynamic programming solution (or a modification of the previous) to
solve this new problem.
As in Part A, your program will receive two arguments, the first argument will be the part (always B
for this task) and the second argument will be the input filename.
The input and output format will be identical to Part A.
Part C (Written)
In Part C, you must create a PDF format document called written-1C.pdf , which explains your
solution in Part A & B according to the points below.
The document must clearly describe the following for your Part A solution:
1. State Representation: Precisely define what each state in the Dynamic Programming solution is,
and all relevant parameters associated with a state. Note how you manage the fat level (ensuring it
never exceeds and never falls to ) and ensure that you have never travelled beyond the
maximum time limit.
F 0
2. Recurrence: State formulaically the recurrence rule associated with your Dynamic Programming
solution. Include your base case(s) and justify the correctness of your recurrence and the base case.
3. Time Complexity: A briefly describe the time and space complexity of your approach. Provide an
upper bound in Big-O notation. Where multiple variables are used in your time complexity, make
sure to define each term clearly.
4. Backtrace: Explicitly state where or how the final answer to the original problem can be found in
your Dynamic Programming table, and briefly describe how the optimal solution can be found
through backtracing.
For your Part B solution, only describe the elements that are different from your description for Part
A. Clearly indicate which of the above points have changed and provide the updated explanation for
those specific points. Where elements of your Part A & B solutions overlap, you are very welcome to
mention as such rather than duplicating the same written response.
A page or two is a reasonable length for this response.
Remember: The time complexity of a dynamic programming algorithm is usually not the closed form
function of the recurrence of the problem being solved.
Task 1: Assignment Submission
Both parts must implement a Dynamic Programming Solution for this task to receive any marks.
To compile: make -B
What each of the numbers in the test cases mean is provided in the source folder.
To run Part A:
./eel A input/t1a-0.txt
To run Part B:
./eel B input/t1b-0.txt
The feedback for test cases is given in the standard unified diff format, you can see info on this format
online (such as at here). A minus means you have a line that is not in the expected output, a plus means you
are missing a line. The diff does not show all output you have produced, only the relevant snippet.
Expected outputs are given in the expected_output folder, should you wish to test your code on one
of the later test cases.
Task 1: Test Case Visualisation
1 Automatic Zoom
Task 2: Bird Tracking
Avid bird-watchers use an app to keep track of the birds they have seen during a bird-watching (or
birding) trip. Every trip, a bird-watcher will see a variety of birds, including some they have seen
before, and some they have not seen. Birds previously unseen are referred to as "Lifers", and there is
some element of competition amongst bird watching enthusiasts to see the most birds, and thus
gather the most lifers, possible. There are certain rules of course, to recording what birds can be
recorded:
Only real birds can be recorded - specifically, it has to be a bird that is within the Clement's
Checklist of Birds of the World.
Each bird can be recorded multiple times, and it is best practice to keep track of how many
times a bird has been seen. This is so that citizens can help to contribute to science and
monitoring bird populations.
Of course, given that birds are usually some distance away and tend not to stay still, it is important to
be able to quickly record birds and check if you have seen them. Some examples of Australian birds
are given below:
Left and Middle: Little Wattlebirds, Right: Crimsonwing Rosella
Part A (Code)
A regular bird-watching group has invited some tourists to go birding with them. The tourists really
wanted to find some new birds the group has not seen but were not confident as it was their first
time going birding. Fortunately, there is a list of birds the group has seen available, and the tourists
thought to ask online to see if anyone would be willing to put together a system to help with quickly
checking if the birds they spot have been seen by the group before or not.
Part B (Code)
Hooked on birding, the tourists realise that they really want to contribute to citizen science and track
how many of each bird they have seen, in a very fast way. They also realise that due to naming
differences in different countries, they sometimes input the wrong bird name and would like to
delete it so that they can replace it with a more accurate name. Seeing no reason to let the previous
work go to waste, the tourists once again reach out online to find someone who can modify the
previous system to allow for counting how many birds have been seen, and deleting birds from the
list.
Part C (Written)
The tourists realise that there may be some issues with deletion but are unsure and are asking for
your thoughts on whether there are any possible issues with deletion. They also wish to know if there
has been any significant change in the runtime and size of the system after the modification in Part B
compared to Part A. How have the time and space complexity changed from going from a standard
system of Part A to the modified system in Part B?
Part D (Code)
The tourists have come upon a fatal flaw in the system from Part B: it seems there is a limit to how
many birds they can add. They once again ask online for help in making a system that efficiently
allows them to do all of the previous tasks, but also can add as many birds as they like.
Part E (Written)
Similar to before, the tourists are interested in any significant change in the runtime and size of the
system after the modification in Part D compared to Part A. How have the time and space complexity
changed from going from the basic system of Part A to the modified system in Part D?
Task 2: Bloom Filters
Background - Bloom Filters
Bloom Filters offer a fast and space-efficient way of checking the existence of an item in a set.
Previously we saw that using hash tables, we a best case look-up, but if you have collisions,
you would have an worse case look-up.
O(1)
O(n)
Bloom Filters are a probabilistic data structure that work by storing hash values, rather than the
underlying keys. In addition, we tend to store more than one hash value per key.
Initially, every entry in the Bloom Filter is set to . To insert in a Bloom Filter, we first hash our key
with different functions, and we set the table entry associated with each of those values to ,
irrespective of their previous value. Here, is a parameter we can tune, and the hash function will be
provided.
0
k 1
k
To check if a key is in our set, we simply need to check if the positions given by hashing the key are
non-zero. If any of them are zero, then the key is "definitely not in the set". Otherwise, the key is
"probably in the set". This approach allows us to have an look-up, at the cost of some
uncertainty.
k
O(k)
In addition, if we assign individual bits to or , we can represent entries in the Bloom filter more
efficiently. Recall that a single integer is bits, meaning we significantly reduce the amount of space
we use when using a Bloom filter. This is important when we are dealing with large datasets, and
want a very fast look-up.
0 1
32
We will use bloom filters to check if we have seen certain birds before.
All three Bloom Filter variants must use a bit array for this task to receive any marks (i.e. A single int length
value must contain 32 entries in the initial Bloom filter and should contain entries for the other
tasks).
BUCKET_SIZE
32
Part A (Code)
Part A will implement a simple Bloom Filter and relevant functionality in bf.c , such as the functions
of:
Adding an element (done in addBF ).
Searching for membership in the set (done in checkBF and birdCheckBF ).
To support checking, you will search your Bloom Filter and perform necessary bit operations. For
each query, you must return the query (i.e. the bird's name) followed by whether or not it is within
the filter.
The first argument for each part will be the type of Bloom filter implemented ( B for Part A, C for Part
B and D for Part D).
Part A will take two filenames from the command line:
The first filename is the name of the list of birds seen by the group.
The second filename is the name of the birds to be queried.
The format of the file with the first given filename will be similar to this example:
10 0.01
Abbott's Babbler
Abbott's Booby
Abbott's Starling
Abd al Kuri Sparrow
Abdim's Stork
Aberdare Cisticola
Aberrant Bush Warbler
Abert's Towhee
Abyssinian Catbird
Abyssinian Crimsonwing
Where all files follow the format:
The first line specifies the number of birds that have previously been seen ( in this example),
and the desired false positive rate ( ).
10
0.01
All following lines specify names of birds that have been previously seen.
The format of the file with the second given file name will be similar to this example:
Abbott's Booby
Abyssinian Catbird
Abyssinian Crimsonwing
Blyth's Frogmouth
Emerald-chinned Hummingbird
Lemon Dove
Where each line is simply the name of the bird, seen on the current bird-watching trip.
The output must be the list of words ordered by input of birds, and whether or not they are in the list.
For the given example this would be:
...Reading...
...Checking...
Abbott's Booby : Possibly in the list
Abyssinian Catbird : Possibly in the list
Abyssinian Crimsonwing : Possibly in the list
Blyth's Frogmouth : Definitely not in the list
Emerald-chinned Hummingbird : Definitely not in the list
Lemon Dove : Definitely not in the list
Hint: For the spacing, use the %-30s format specifier
Part B (Code)
Though Bloom filters can be quite efficient, they prevent us from knowing characteristics about the
data such as "how many items do we have in our filter?". They also do not allow us to delete items,
which can be something we desire.
In Part B, the first argument will be C , the first two file inputs which follow are the same as in the
prior part, but there will be additional third file input specified by an additional argument given on
the command line. This input will be the name of the file storing a list of birds to remove from the
Bloom Filter (as they were mistakenly recorded by the bird watcher). For example, if Wompoo Fruit
Dove was in the list of birds to delete, we would want to remove it from the Bloom Filter.
To do this, Part B will implement a counting Bloom filter. The new counting Bloom filter is almost
identical to the standard filter used in part A, except that instead of each entry in the Bloom filter
being a single bit, it is now bits. Instead of changing a to at each hash value, we instead have the
relevant buckets incremented each time something is added. That is to say, we have buckets ranging
from to in binary representation ( to in decimal), and we assume that the maximal
number of birds in any single bucket must be capped at . Deleting an item involves decrementing
the associated entries.
4 0 1
0000 1111 0 15
15
You will need to implement in cbf.c :
Adding elements to counting Bloom filters.
Reading in elements.
Finding how many times an item has (probably) been seen (via a minimum selection algorithm).
Deleting an element.
The output must be a list of the birds, presented in the same order they appeared in the input, along
with a value indicating how many times each bird has probably been seen. For the given example this
would be:
...Reading...
...Checking...
Abbott's Booby : Probably 1 in the list
Abyssinian Catbird : Probably 1 in the list
Abyssinian Crimsonwing : Probably 1 in the list
Blyth's Frogmouth : Definitely not in the list
Emerald-chinned Hummingbird : Definitely not in the list
Lemon Dove : Definitely not in the list
...Deleting...
Abbott's Babbler : Deleted, and now definitely not in the list
Abbott's Booby : Deleted, and now definitely not in the list
Part B Notes
If adding an item will exceed your limit for each binary counter, then you must output
"Overflow occurred." and immediately terminate the function (but not the program) - see the
following slides for more details.
See the diagrams in the following two slides for what to output upon deletion.
Part C (Written)
In Part C, you must create a PDF format document called written-tasks2.pdf , which explains
potential issues with item deletion in counting Bloom filters. Your answer must state an upper-bound
on the time and space complexity reflecting the impact of having counters over a basic Bloom Filter,
with each term used explained clearly.
In order to avoid trivial answers, you must assume that the number of bits dedicated to counting is
variable, which we will call c. Include all relevant parameters.
A paragraph or two is sufficient for a response to this part.
Part D (Code)
The Bloom filters above are limited in scalability as we must know the number of items we read in, in
advance. In Part D, you must implement a dynamic counting bloom filter. This variant of the bloom
filter effectively layers counting bloom filters like layers of a cake. When one gets full (or an overflow
occurs in a bucket), a new one is made and further data is stored there.
The first argument for Part D, is D . The following input files will be the same as in Part B, except
there is no longer the number of birds listed at the start, and instead a desired capacity of each
Bloom filter. In addition, for Part D, you can assume that the input will always be alphabetically
ordered, and that birds will only be inserted during the initial input (i.e. there will be no ad hoc
insertions).
Insertion involves inserting an item at the current active (latest created) filter. Thus, there will also be
the need to track the current utilization alongside the maximum capacity of each filter.
Look-up involves checking all k positions of the relevant s counting Bloom filters, so long as we keep
track of where items are inserted. A Bloom filter is considered relevant where a bird could possibly
have been inserted in that Bloom filter, given that you have tracked insertions, it is possible to more
precisely determine relevant Bloom filters. You must implement an O(s) space complexity method
of tracking item insertions. Deletion also requires you to keep track of where each item was inserted,
and then deleting from that filter. Your deletion operation should be O(k + s) worst case, and
lookup should be O(ks) worst case, with average case O(k + s) assuming uniform distribution of
all possible bird sightings (and assuming non-limited bird varieties to avoid saturation). You should
also assume that the bucket size is a constant.
The above functions should be implemented in dbf.c . The output will be similar to Part B as well.
Part E (Written)
In Part E, discuss the change in complexity in having a dynamic Bloom filter as opposed to a basic
Bloom filter. Briefly describe how you implemented an O(k + s) deletion. Note assumptions around
what factors can reasonably be held constant (these are similar to the assumptions we would need to
make for a hash table). Add this discussion to your report named written-tasks2.pdf .
A paragraph or two is sufficient for a response to this part.
Task 2: Bit Operation Implementation Tips
To implement the Bloom Filter, a recommended approach is to use the functions provided below.
If you want to understand the task, and the bit operations to implement in bit.c , you need to
understand the following bit operators over numbers a and b:
Operator
a & b
a | b
˜a
a |= b
a &= b
a << b
a >> b
Meaning
Where both corresponding bits in a and b are 1,
output a 1 in that bit position, otherwise give a 0 in that position.
Where either corresponding bit in a and b is 1,
output a 1 in that bit position, otherwise give a 0 in that position.
Where the corresponding bits in a are 1,
output a 0 in that bit position, otherwise give a 1 in that position
Compute a | b and assign the result of the operation to a.
Compute a & b and assign the result of the operation to a.
For all bits in a, move each bit b positions to the left.
For all bits in a, move each bit b positions to the right.
In addition, we will define:
a+=b as compute a+b and assign the result of the operation to a . Remember to only do this if
adding will not cause an overflow.
a-=b as compute a-b and assign the result of the operation to a . Remember to only do this if
subtracting will not cause an underflow.
Example: Basic Operations
Basic Bit Functions Diagrams and Hints
initBits
This function initialises all our bits to zero.
/* Initialise bits */
initBits(A[], arraySize):
for each bit in A[]:
bitOff(A)
addBits
This function finds the section of our Bloom Filter associated with bucketIndex , and increases the
value at that bucket by one, so long as this does not cause an overflow.
addBits(A[], bucketIndex):
if the bucket is full:
return 1
increment the binary value in the bucket by 1.
return 0
subtractBits
This function finds the section of our Bloom Filter associated with bucketIndex , and decreases the
value at that bucket by one, so long as this does not cause an underflow.
subtractBits(A[], bucketIndex):
if the bucket is empty:
return 1
decrement the binary value in the bucket by 1.
return 0
Task 2: Function Diagrams and Hints
This slide has several diagrams to help you through the logic of how these functions should work -
the same function for different Bloom filter variants are presented alongside each other so that you
can easily see how they slightly change between variants. Please start off by implementing the
standard Bloom Filter in bf.c and then move on to cbf.c , for the Counting Bloom filter, and
dbf.c for the Dynamic Bloom Filter.
We have provided two printing functions, one which prints the Bloom filter and one which prints the bits that
have changed in the filter through the previous step, for debugging purposes. These can be found in
utils.h.
Reading a list of birds and adding them to the (Regular / Counting)
Bloom Filter
These functions read in the datafile and sets up the Bloom filter.
Reading a list of birds and adding them to the Dynamic Bloom Filter
This function reads in the datafile and sets up the Bloom filters.
Adding a single bird to a (Regular/ Counting / Dynamic) Bloom Filter
In terms of how we implement the add functions, we will also have an argument to the function which is the
number of hashes. In addition, the diagram shows just the array of the Bloom filter, but we pass the entire
Bloom filter structure in reality (that is, including things such as the number of bits).
Checking if a single bird is in a (Regular/ Counting / Dynamic) Bloom
Filter
In terms of how we implement the check functions, we will also have an argument to the function which is the
number of hashes. In addition, the diagram shows just the array of the Bloom filter, but we pass the entire
Bloom filter structure in reality (that is, including things such as the number of bits).
Checking if a list of birds is in a (Regular/ Counting / Dynamic) Bloom
Filter
Counting how many of a bird there are in a Counting / Dynamic Bloom
Filter
In terms of how we implement the counting functions, we will also have an argument to the function which is
the number of hashes. In addition, the diagram shows just the array of the counting and dynamic Bloom
filters, but we pass the entire Bloom filter structure in reality (that is, including things such as the number of
bits).
You may wish to use the countBucket function.
Deleting from a Counting / Dynamic Bloom Filter
The "relevant lines" are "[Birdname]: Deleted, but still possibly in the list", "[Birdname]: Deleted, and now
definitely not in the list" and "[Birdname]: ERROR - Trying to delete an item definitely not in the list".
When implementing the deletion for the DBF - ensure to only delete from the first Bloom filter the bird has
definitely been seen in - not subsequent ones. This means that you will have to have a way to navigate to this
Bloom Filter. Of course, in the CBF case we only have one, and so we only need to operate on that.
Also to note is that in deleteBirdsCBF we take in the CBF, and in deleteBirdsDBF we take in the DBF.
Task 2: Assignment Submission
All three Bloom Filter variants must use a bit array for this task to receive any marks (i.e. A single int length
value must contain 32 entries in the initial bloom filter and should contain entries for the other
tasks).
BUCKE
32
T_SIZE
To compile: make -B
A list of commands used for the test cases is provided (in order) in run.txt
To run Part A (standard Bloom Filter):
./birds B datafiles/t2a_data_1.txt test_cases/t2_1.txt
To run Part B (counting Bloom Filter):
./birds C datafiles/t2b_data_1.txt test_cases/t2_1.txt delete_cases/t2_delete_1.txt
To run Part D (dynamic Bloom Filter):
./birds D datafiles/t2d_data_50.txt test_cases/t2_1.txt delete_cases/t2_delete_10.txt
The feedback for test cases is given in the standard unified diff format, you can see info on this format
online (such as at here). A minus means you have a line that is not in the expected output, a plus means you
are missing a line. The diff does not show all output you have produced, only the relevant snippet.
Output Example (Part A):
...Reading...
...Checking...
Abbott's Booby : Possibly in the list
Abyssinian Catbird : Possibly in the list
Abyssinian Crimsonwing : Possibly in the list
Blyth's Frogmouth : Definitely not in the list
Emerald-chinned Hummingbird : Definitely not in the list
Lemon Dove : Definitely not in the list
Hint: For the spacing, use the %-30s format specifier
Output Example (Part B and D):
...Reading...
...Checking...
Abbott's Booby : Probably 1 in the list
Abyssinian Catbird : Probably 1 in the list
Abyssinian Crimsonwing : Probably 1 in the list
Blyth's Frogmouth : Definitely not in the list
Emerald-chinned Hummingbird : Definitely not in the list
Lemon Dove : Definitely not in the list
...Deleting...
Abbott's Babbler : Deleted, and now definitely not in the list
Abbott's Booby : Deleted, and now definitely not in the list
Academic Honesty
This is an individual assignment. The work must be your own work.
While you may discuss your program development, coding problems and experimentation with your
classmates, you must not share files, as doing this without proper attribution is considered
plagiarism.
If you have borrowed ideas or taken inspiration from code and you are in doubt about whether it is
plagiarism, provide a comment highlighting where you got that inspiration.
If you refer to published work in the discussion of your experiments, be sure to include a citation to
the publication or the web link.
“Borrowing” of someone else’s code without acknowledgment is plagiarism. Plagiarism is considered
a serious offense at the University of Melbourne. You should read the University code on Academic
integrity and details on plagiarism. Make sure you are not plagiarizing, intentionally or
unintentionally.
You are also advised that it will be necessary to write pseudocode in the final examination. Students
who do not program their own assignments will be at a disadvantage for this part of the examination.
Late Policy
The late penalty is 20% of the available marks for that project for each working day (or part thereof)
overdue.
If you wish to apply for an extension, please review the FEIT Extensions and Special consideration
page on the subject LMS. Requests for extensions on medical grounds will need to be supported by a
medical certificate. Any request received less than 48 hours before the assessment date (or after the
date!) will generally not be accepted except in the most extreme circumstances. In general, extensions
will not be granted if the interruption covers less than 10% of the project duration. Remember that
departmental servers are often heavily loaded near project deadlines, and unexpected outages can
occur; these will not be considered as grounds for an extension.
Students who experience difficulties due to personal circumstances are encouraged to make use of
the appropriate University student support services, and to contact the lecturer, at the earliest
opportunity.
Finally, we are here to help! Frequently asked questions about the project will be answered on Ed.
Requirements: C Programming
The following implementation requirements must be adhered to:
You must write your implementation in the C programming language.
Your code should be easily extensible to multiple data structure instances. This means that the
functions for interacting with your data structures should take as arguments not only the values
required to perform the operation required, but also a pointer to a particular data structure, e.g.
search(dictionary, value) .
Your implementation must read the input file once only.
Your program should store strings in a space-efficient manner. If you are using malloc() to
create the space for a string, remember to allow space for the final end of string character, ‘ \0 ’
( NULL ).
Your approach should be reasonably time efficient.
Your solution should begin from the provided scaffold.
Hints:
• If you haven’t used make before, try it on simple programs first. If it doesn’t work, read the error messages
carefully. A common problem in compiling multifile executables is in the included header files. Note also that
the whitespace before the command is a tab, and not multiple spaces.
• It is not a good idea to code your program as a single file and then try to break it down into multiple files.
Start by using multiple files, with minimal content, and make sure they are communicating with each other
before starting more serious coding.
Programming Style
Below is a style guide which assignments are evaluated against. For this subject, the 80 character
limit is a guideline rather than a rule — if your code exceeds this limit, you should consider whether
your code would be more readable if you instead rearranged it.
/** ***********************
* C Programming Style for Engineering Computation
* Created by Aidan Nagorcka-Smith (aidann@student.unimelb.edu.au) 13/03/2011
* Definitions and includes
* Definitions are in UPPER_CASE
* Includes go before definitions
* Space between includes, definitions and the main function.
* Use definitions for any constants in your program, do not just write them
* in.
*
* Tabs may be set to 4-spaces or 8-spaces, depending on your editor. The code
* Below is ``gnu'' style. If your editor has ``bsd'' it will follow the 8-space
* style. Both are very standard.
*/
/**
* GOOD:
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_STRING_SIZE 1000
#define DEBUG 0
int main(int argc, char **argv) {
...
/**
* BAD:
*/
/* Definitions and includes are mixed up */
#include <stdlib.h>
#define MAX_STING_SIZE 1000
/* Definitions are given names like variables */
#define debug 0
#include <stdio.h>
/* No spacing between includes, definitions and main function*/
int main(int argc, char **argv) {
...
/** *****************************
* Variables
* Give them useful lower_case names or camelCase. Either is fine,
* as long as you are consistent and apply always the same style.
* Initialise them to something that makes sense.
*/
/**
* GOOD: lower_case
*/
int main(int argc, char **argv) {
int i = 0;
int num_fifties = 0;
int num_twenties = 0;
int num_tens = 0;
...
/**
* GOOD: camelCase
*/
int main(int argc, char **argv) {
int i = 0;
int numFifties = 0;
int numTwenties = 0;
int numTens = 0;
...
/**
* BAD:
*/
int main(int argc, char **argv) {
/* Variable not initialised - causes a bug because we didn't remember to
* set it before the loop */
int i;
/* Variable in all caps - we'll get confused between this and constants
*/
int NUM_FIFTIES = 0;
/* Overly abbreviated variable names make things hard. */
int nt = 0
while (i < 10) {
...
i++;
}
...
/** ********************
* Spacing:
* Space intelligently, vertically to group blocks of code that are doing a
* specific operation, or to separate variable declarations from other code.
* One tab of indentation within either a function or a loop.
* Spaces after commas.
* Space between ) and {.
* No space between the ** and the argv in the definition of the main
* function.
* When declaring a pointer variable or argument, you may place the asterisk
* adjacent to either the type or to the variable name.
* Lines at most 80 characters long.
* Closing brace goes on its own line
*/
/**
* GOOD:
*/
int main(int argc, char **argv) {
int i = 0;
for(i = 100; i >= 0; i--) {
if (i > 0) {
printf("%d bottles of beer, take one down and pass it around,"
" %d bottles of beer.\n", i, i - 1);
} else {
printf("%d bottles of beer, take one down and pass it around."
" We're empty.\n", i);
}
}
return 0;
}
/**
* BAD:
*/
/* No space after commas
* Space between the ** and argv in the main function definition
* No space between the ) and { at the start of a function */
int main(int argc,char ** argv){
int i = 0;
/* No space between variable declarations and the rest of the function.
* No spaces around the boolean operators */
for(i=100;i>=0;i--) {
/* No indentation */
if (i > 0) {
/* Line too long */
printf("%d bottles of beer, take one down and pass it around, %d
bottles of beer.\n", i, i - 1);
} else {
/* Spacing for no good reason. */
printf("%d bottles of beer, take one down and pass it around."
" We're empty.\n", i);
}
}
/* Closing brace not on its own line */
return 0;}
/** ****************
* Braces:
* Opening braces go on the same line as the loop or function name
* Closing braces go on their own line
* Closing braces go at the same indentation level as the thing they are
* closing
*/
/**
* GOOD:
*/
int main(int argc, char **argv) {
...
for(...) {
...
}
return 0;
}
/**
* BAD:
*/
int main(int argc, char **argv) {
...
/* Opening brace on a different line to the for loop open */
for(...)
{
...
/* Closing brace at a different indentation to the thing it's
closing
*/
}
/* Closing brace not on its own line. */
return 0;}
/** **************
* Commenting:
* Each program should have a comment explaining what it does and who created
* it.
* Also comment how to run the program, including optional command line
* parameters.
* Any interesting code should have a comment to explain itself.
* We should not comment obvious things - write code that documents itself
*/
/**
* GOOD:
*/
/* change.c
*
* Created by Aidan Nagorcka-Smith (aidann@student.unimelb.edu.au)
13/03/2011
*
* Print the number of each coin that would be needed to make up some
change
* that is input by the user
*
* To run the program type:
* ./coins --num_coins 5 --shape_coins trapezoid --output blabla.txt
*
* To see all the input parameters, type:
* ./coins --help
* Options::
* --help Show help message
* --num_coins arg Input number of coins
* --shape_coins arg Input coins shape
* --bound arg (=1) Max bound on xxx, default value 1
* --output arg Output solution file
*
*/
int main(int argc, char **argv) {
int input_change = 0;
printf("Please input the value of the change (0-99 cents
inclusive):\n");
scanf("%d", &input_change);
printf("\n");
// Valid change values are 0-99 inclusive.
if(input_change < 0 || input_change > 99) {
printf("Input not in the range 0-99.\n")
}
...
/**
* BAD:
*/
/* No explanation of what the program is doing */
int main(int argc, char **argv) {
/* Commenting obvious things */
/* Create a int variable called input_change to store the input from
the
* user. */
int input_change;
...
/** ****************
* Code structure:
* Fail fast - input checks should happen first, then do the computation.
* Structure the code so that all error handling happens in an easy to read
* location
*/
/**
* GOOD:
*/
if (input_is_bad) {
printf("Error: Input was not valid. Exiting.\n");
exit(EXIT_FAILURE);
}
/* Do computations here */
...
/**
* BAD:
*/
if (input_is_good) {
/* lots of computation here, pushing the else part off the screen.
*/
...
} else {
fprintf(stderr, "Error: Input was not valid. Exiting.\n");
exit(EXIT_FAILURE);
}
Some automatic evaluations of your code style may be performed where they are reliable. As
determining whether these style-related issues are occurring sometimes involves non-trivial (and
sometimes even undecidable) calculations, a simpler and more error-prone (but highly successful)
solution is used. You may need to add a comment to identify these cases, so check any failing test
outputs for instructions on how to resolve incorrectly flagged issues.
Mark Breakdown
There are a total of 20 marks given for this assignment.
Your C programs for both tasks should be accurate, readable, and observe good C programming
structure, safety and style, including documentation. Safety refers to checking whether opening a file
returns something, whether mallocs do their job, etc. The documentation should explain all major
design decisions, and should be formatted so that it does not interfere with reading the code. As
much as possible, try to make your code self-documenting, by choosing descriptive variable names.
Note that marks related to the correctness of your code will be based on passing various tests. If your
program passes these tests without addressing the learning outcomes (e.g. if you fully hard-code
solutions or otherwise deliberately exploit the test cases), you may receive less marks than is
suggested but your code marks will otherwise be determined by test cases.
Marking is based on threshold testing, gaining marks for later tests requires passing earlier tests first.
Mark Breakdown
Task
Task 1
Task 2
Mark Distribution
3 Marks (Part A) + 3 Marks (Part B) + 4 Marks (Part C)
3 Marks (Part A) + 3 Marks (Part B)
+ 1 Mark (Part C) + 2 Marks (Part D) + 1 Mark (Part E)
Note that not all marks will represent the same amount of work, you may find some marks are easier
to obtain than others. Note also that the test cases are similarly not always sorted in order of
difficulty, some may be easier to pass than others.
Additional Support
Your tutors will be available to help with your assignment during the scheduled workshop times.
Questions related to the assignment may be posted on the Ed discussion forum, using the folder tag
Assignments for new posts. You should feel free to answer other students’ questions if you are
confident of your skills.
A tutor will check the discussion forum regularly, and answer some questions, but be aware that for
some questions you will just need to use your judgment and document your thinking.
If you have questions about your code specifically which you feel would reveal too much of the
assignment, feel free to post a private question on the discussion forum.
Acknowledgements
Some tables and diagram designs were adapted from the work of previous tutors.
Photos of birds were taken by Danielle.

請加QQ：99515681  郵箱：99515681@qq.com   WX：codinghelp