代写program、代做c++编程设计

日期：2025-05-18 10:15

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.