COMP20007代写、代做Algorithms、C++程序语言调试、C/C++代写

日期：2020-04-18 11:20

2020 Semester 1

COMP20007 Design of Algorithms

School of Computing and Information Systems

The University of Melbourne

Assignment 1

Due: 5:00 PM AEST Wednesday 29 April

Introduction

This assignment contains 3 problems. You will be required to write pseudocode and C code, as well as

provide a detailed analysis of your algorithms. You will submit your solutions for the C programming

component of this assignment via dimefox submit and the written component via the LMS.

This assignment has a total of 10 marks and will contribute 10% to your final grade for this subject.

Problem 1

2 Marks – 0.5 - 1 Page

In this task you need to design an algorithm to evaluate arithmetic expressions that consist of integer

numbers, opening and closing parentheses and the operators +, -, * and /. Here / is integer division.

A well-defined arithmetic expression is defined as:

• A digit d ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is a well-formed arithmetic expression.

• If X and Y are well-formed arithmetic expressions, then the four expressions (X + Y), (X - Y),

(X * Y) and (X / Y) are also well-formed arithmetic expressions.

Examples of well-formed arithmetic expressions are "((8+7)*3)", "(4-(9-2))" and "0". However,

the expressions ) "3+) 2 (())", "(9 + ())", "-4", "5-8", "108" or "(8)" are not well-formed

arithmetic expressions.

For this problem you will be required to write pseudocode, i.e., human understandable “code” which

provides enough detail to make it clear which operations your algorithm is performing but doesn’t

let the syntax get in the way of presenting your algorithm – the lecture slides and solutions to the

workshops contain good examples of pseudocode.

You must write an algorithm, in pseudocode, which checks whether an input string is a well-formed

arithmetic expression. If it is not well-formed then your algorithm must return NotWellFormed,

otherwise it must evaluate the expression and return the integer result.

Your algorithm does not have to deal with division by 0.

Your algorithm should process the input from left to right, one character at a time. You should make

use of two stacks, one stack for operators (including ( and )) and another stack for values. Algorithms

which do not make use of the stack abstract data structure will not be awarded full marks.

1

Problem 2

In this problem you will be implementing three functions in C. These functions deal with the abstract

data type called a deque, pronounced deck. A deque is a double-ended queue in which elements can

be inserted and removed from both ends (which we’ll call the top and the bottom). In particular a

deque must provide the following functions:

• Push(x) – inserts the element x at the top of the deque,

• Insert(x) – inserts the element x at the bottom of the deque,

• Pop() – removes and returns the element at the top of the deque, and

• Remove() – removes and returns the element at the bottom of the deque.

In the provided C code we have implemented the type Deque for you in the deque module (consisting

of deque.h and deque.c) using a doubly-linked list.

Your task is to read and understand how the deque module works and implement the functions

described in Parts (a), (b) and (c).

Your implementations must go in deque.c. You can add any additional functions required to solve

this problem.

In each of these functions you should not return a new Deque but rather alter the original Deque data

structure. You may make use of additional data structures during these functions, however they must

be freed before your function returns.

Part (a)

1 Mark

You must implement the function iterative_reverse(Deque *deque) which takes a pointer to a

Deque and reverses this deque using an iterative approach.

For example if the deque initially looks like:

Top 4 8 9 0 1 Bottom

Then after calling iterative_reverse() the deque should look like:

Top 1 0 9 8 4 Bottom

For full marks your function must run in O(n) time for a deque with n elements.

Part (b)

1 Mark

As in Part (a) you must write a function to reverse the deque, although this time you must use a

recursive approach. The function you must implement is recursive_reverse(Deque *deque).

Again, your function must run in O(n) time for a deque with n elements.

Part (c)

1 Mark

Write a function split(Deque *deque, int k) that rearranges the elements in the deque such that

each element with a value greater than or equal to the critical value (i.e., ≥ k) precedes (i.e., is closer

to the top of the deque) each element with a value less than k.

2

Within the two groups of elements (i.e., ≥ k and < k) the elements must be in their original order.

For example if we were to split the following deque with a critical value k = 3,

Top 1 4 3 2 5 Bottom

then the resulting deque would be,

Top 4 3 5 1 2 Bottom

This function must run in O(n) time, where n is the number of elements in the deque.

Problem 3

A park ranger has to trim all the trees on a mountain slope. Since it is winter, the slope is covered in

snow and it is not safe to climb it directly. Therefore, the ranger plans to chairlift to the top of the

mountain and ski down the slope, trimming the trees as they go down.

You are provided with a map of the trees on the ski slope with the possible routes between trees. You

must write an algorithm to answer the following question: can the park ranger trim all of the

trees using the chairlift only once? In other words, is there a single run the park ranger can

perform from the top of the mountain which goes past every tree, or does the park ranger require

multiple trips down the mountain?

For example, the ski slope map on the left indicates which routes between trees are possible (with the

mountain icon indicating the top of the mountain where the park ranger must begin his traversal of

the mountain). The answer in this case is yes, the park ranger can trim all trees in one run.

This run is shown on the right.

Note that your algorithm doesn’t need to produce the order in which the trees should be visited, only

determine whether or not there does exist a valid run from the top of the mountain that visits all the

trees.

3

The following two maps, however, do not have a single run from the top to the bottom which visits

all trees.

You will notice that these trees and the possible routes between them form a directed graph. Since

the park ranger can only ski down the mountain (and cannot climb up it during a run) the graph will

not have any cycles. Thus, the graph is a directed acyclic graph (DAG).

Part (a)

2 Marks

Devise a linear time algorithm which determines whether or not the park ranger can ski down and

trim all of the trees in a single run. If there are n trees and m edges between trees then your algorithm

must run in O(n + m).

You must implement your algorithm in C by completing the function is_single_run_possible() in

the park ranger module provided for you (parkranger.c and parkranger.h). You should add any

types and functions required to solve this problem.

Your program must provide an appropriate data structure to store the directed graph.

Your program will be provided with the ski slope map via stdin in the following format:

• One line containing integers n and m. n indicates the number of trees, and m indicates the

number of possible routes (i.e., edges) between trees (or between the top of the mountain and a

tree).

• m lines containing two integers u and v, which indicates that it’s possible for the park ranger to

ski from u directly to v.

The trees are labelled 1 to n, while the top of the mountain is always labelled 0.

Your function must perform the following steps:

• Read in the data from stdin.

• Store the data in an appropriate data structure.

• Determine whether the park ranger can trim all the trees in a single run.

• Do any clean up required (e.g., free any allocated memory).

4

• Return true or false depending on the result of your algorithm. Note that true and false

are of type bool, which is included from the stdbool.h library.

The following ski slope is an example of the input format your program will be given.

Part (b)

2 Marks – 0.5 - 1 Page

Explain your algorithm, and explain why your algorithm runs in linear time.

Clear pseudocode may help you convey your algorithm to the reader, but is not required for full marks

for this part. You should not include very detailed pseudocode if you do decide to present this, just

an overview of your algorithm.

Completing the Programming Problems

We have provided you with the skeleton code for this assignment. The provided files has the following

directory structure:

provided_files/

Makefile

main.c

deque.c

deque.h

parkranger.c

parkranger.h

util.c

util.h

tests/

p2a-in-1.txt

p2a-out-1.txt

...

p3a-in-6.txt

p3a-out-6.txt

You must not change the main.c file, however you are allowed to change any of the other files (without

changing the existing type declarations and function signatures).

If you create new C modules (which you are encouraged to do) then you must change the Makefile

so that your program can be compiled on dimefox using the make command.

5

To run the program you must first compile with make, and then run the a1 command with one of

these command line arguments: p2a, p2b, p2c, p3a.

For example:

$ make

$ ./a1 p2a < tests/input.txt

$ ./a1 p2b < tests/input.txt

$ ./a1 p2c < tests/input.txt

$ ./a1 p3a < tests/input.txt

The pXX-in-X.txt files contain the input your program will be provided for each test case, and the

pXX-out-X.txt files contain the expected output. Your program must match the expected output

exactly.

Your functions must not print to stdout. Your program should change the Deque provided and

return nothing in the case of Problem 2 and return true or false in the case of Problem 3.

Testing your Program

Problems 2 (a) and 2 (b) can be tested by using ./a1 p2a and ./a1 p2b respectively. The program

expects input via stdin which is a list of integers (one per line). These integers will be inserted into

the deque (inserting each element at the bottom), then your function will be called.

For example if tests/input.txt contains the numbers 10, 15, 20, 30 on their own lines then after

implementing iterative_reverse() your program should behave like so:

$ ./a1 p2a < tests/input.txt

read 4 elements into the deque

original deque: [10, 15, 20, 30]

reversed deque: [30, 20, 15, 10]

successfully freed the deque

Again, note that your program should not print this output, this is handled by test_reverse() in

main.c which has been written for you.

Testing Problem 2 (c) is similar, you should use the p2c option for ./a1. Here the text input includes

a list of integers on their own lines as well, with the first integer being the critical value, and the

remaining integers being inserted into the deque before it is split.

Testing Problem 3 (a) requires the input to be provided to stdin as described in the problem description.

If the example input from the problem description is in tests/input.txt then your program

should behave like so:

$ ./a1 p3a < tests/input.txt

the trees on the ski slope CAN be trimmed in one run

Again, your function should just return true or false and should not write to stdout. The output

is handled by main.c.

Programming Problem Submission

You will submit your program via dimefox submit. Instructions for how to connect to the dimefox

server can be found on the LMS.

6

You should copy all files required to compile and run your code to dimefox, this includes the Makefile

and all .c and .h files.

It’s recommended that you test your program on dimefox before submitting to make sure that your

program compiles without warnings and runs as expected.

From the directory containing these files you should run submit and list all files required to compile

and run your program. For example, to submit only the provided files we would run:

$ submit comp20007 a1 Makefile main.c deque.c deque.h

... util.c util.h parkranger.c parkranger.h

Note that you can also list all .c and .h files in the current directory with *.c and *.h, so the following

command will be equivalent:

$ submit comp20007 a1 Makefile *.c *.h

For this to work correctly you should have your Assignment 1 code in its own subdirectory (i.e., the

only files in the directory should be the files you wish to submit).

You must then verify your submission, which will provide you with the outcome of each

of the tests, and the number of marks your submission will receive.

$ verify comp20007 a1 > a1-receipt.txt

To view the result of the verify command you must run:

$ less a1-receipt.txt

less is a tool which allows you to read files using the command line. You can press Q on your keyboard

to exit the less view.

You can submit as many times as you would like.

Note that programs which do not implement the algorithm they claim to (e.g., a solution for iterative_

reverse() which uses recursion) or does not run the required time bound will receive fewer marks

than the receipt may suggest.

Any attempt to manipulate the submission system and/or hard-code solutions to pass the specific test

cases we have provided will result in a mark of 0 for the whole assignment.

Completing the Written Problems

You will submit your solutions to Problems 1 and 3 (c) via the LMS.

For Problem 1, which asks for pseudocode, we expect you to provide the same level of detail as the

lectures and workshops do. Pseudocode which lacks sufficient detail or is too detailed (e.g., looks like

C code) will be subject to a mark deduction.

Your submission should be typed and not handwritten and submitted as a .pdf file. Pseudocode

should be formatted similarly to lectures/workshops, or presented in a monospace font.

The page limit for each problem is given (half to one full page per written problem).

7

Make sure you confirm that your written submission has been submitted correctly.

Mark Allocation

The total number of marks in this assignment is 10. The maximum marks for each problem are:

Problem 1 2 marks

Problem 2 3 marks (1 per part)

Problem 3 4 marks (2 per part)

There is one additional mark awarded for “structure and style” for the C programming component.

Of particular importance will be the structure of your C program in terms of modules (.c and .h

files), and how you separate your types and functions across these files.

In total there are 4 marks for the written problems (Problem 1 and Problem 3 (b)) and 6 marks for

the C programming problems (Problem 2 and Problem 3 (a)).

We have provided 3 test cases for each part of Problem 2 and 6 test cases for Problem 3 (a).

The marks awarded for each part of Problem 2 will be calculated by:

Marks = max {1 − 0.5 × Test Cases Failed, 0} .

So passing 0 or 1 of the tests results in a mark of 0, passing 2 results in a mark of 0.5 and passing all

three results in 1 mark (the maximum available).

For Problem 3 the marks are calculated by:

Marks = max {2 − 0.5 × Test Cases Failed, 0} .

So your submission will get 0.5 marks for passing 3 tests, 1 mark for passing 4 tests, 1.5 for 5 and a

maximum of 2 marks for passing all 6.

Late Policy

A late penalty of 20% per day will be applied to submissions made after the deadline. The 20% applies

to the number of total marks. This applies per component, i.e.,

Grade = max n

Programming Grade − 0.2 × Days Late × 6, 0o+ max n

Written Submission Grade − 0.2 × Days Late × 4, 0o.

For example, if you are 2 days late with the programming component but only 1 day late with the

analysis component your grade for the programming component will be reduced by 0.4 × 6 = 2.4 and

the grade for the analysis component will be reduced by 0.2 × 4 = 0.8.

Academic Honesty

You may make use of code provided as part of this subject’s workshops or their solutions (with proper

attribution), however you may not use code sourced from the Internet or elsewhere. Using code from

the Internet is grounds for academic misconduct.

All work is to be done on an individual basis. All submissions will be subject to automated similarity

detection. Where academic misconduct is detected, all parties involved will be referred to the School

of Engineering for handling under the University Discipline procedures. Please see the Subject Guide

and the “Academic Integrity” section of the LMS for more information.

8