C++编程讲解、辅导data编程、c/c++程序调试
- 首页 >> Matlab编程 Assignment 1
March 28, 2021
1 Assignment 1
Due: 5:00pm AEST Friday 16th of April
1.0 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.
1.1 Problem 1
A shortsighted cow, named Sam, cannot find enough grass on its current pasture. It remembers
that the pasture’s enclosing fence has a gap. Unfortunately, the fence is very long: for a full circle,
it takes Sam l steps to walk along the fence. Sam can only see the gap if it is right next to it
(remember the cow is shortsighted). In this question, you will design different algorithms that
will enable Sam to find the gap that is k steps away from its current position. Sam is always
located next to the fence. We call its start position origin. You may assume that l is much greater
than k.
1
1.1.1 Part A
We assume that the cow can go only in one direction along the fence. It has to pick one of the
two directions (say left or right) and continues until it has found the gap. Derive the worst case
complexity of this algorithm.
1.1.2 Part B
Sam’s best friend, an eagle called Indigo, can see the gap and knows the number of steps Sam has
to take, i.e., the value of k is known in this question. Unfortunately, Indigo is never sure whether
it saw the gap with its left or right eye. Hence, Indigo can tell Sam only the number of steps
Sam has to take but does not know the right direction. Design an algorithm with O(k) worst case
complexity such that Sam can find the gap. Explain why your has O(k) time complexity.
1.1.3 Part C
In this part, we assume that k is not known. Sam applies the following strategy: walk 1 step to
the right, turn around if no gap is found, and move to the start. Then walk 2 steps to the left and
return to the start if no gap is found. Then walk 3 steps to the right and return to the start, and so
forth.
2
1. First, work out the general algorithm and write it in pseudocode.
2. Second, work out the worst case time complexity of this algorithm in detail.
3. Explain whether or not this strategy is better than the one you analyzed in Part A.
1.1.4 Part D
Design an algorithm that requires O(k) time efficiency to find a gap and show that its efficiency is
indeed O(k). You do not need to write the algorithm in pseudocode (you can if you want) but you
have to describe the algorithm clearly.
1.2 Problem 2
An Internet service provider wants to deliver service to a village. They have two installation
options:
• Cabled installation. This means connecting the data center via underground cables. Connections
can be either made from the data center to a house or between houses. The cost is
equal to the distance between houses (or between a data center and a house).
• Radio-based installation. This means installing antennas in each house, which then receive
the internet signal through a satellite. The cost of an antenna installation is fixed per house
but can vary from village to village.
The figure below shows an example of a village, where distances are drawn as red arrows with
their corresponding value.
3
For this village, the corresponding textual format is shown below:
where:
• First line contains the antenna cost.
• Second line shows the number of houses followed by the number of connections in the
village.
• Remaining lines show connections where the first and second number are the houses (or 0 if
it is the data center) and the third number is the actual distance.
1.2.1 Part A
Devise a program in C that given a village map and antenna installation cost in the format described
above, returns the installation option with lower cost in total. Your program should output
the lowercase character c if cabled has the lower installation cost and r if radio-based has the
lower cost instead.
1.2.2 Part B
Explain why your program works. You can use pseudocode to help explain your solution.
1.2.3 Part C
Same as Part A, but now the company updated their infrastructure and it can now provide a mix
of cabled and radio-based installations for the village. This means that a house will have internet
access if any of the following are true:
1. There is a path to the data center,
2. The house has an antenna or
3. There is a path to a house with an antenna.
The figure below shows an example of each of the cases above. All houses below are considered
connected.
4
Modify your program in order to output the minimum total cost for this mixed installation.
1.3 Problem 3
A processor manufacturer has come up with a design for a new processor technology designed
for cryptography which is able to simultaneously check if any elements in an array of integers
are divisible by a particular number. In marketing this chip, the processor engineering team have
asked you to write a program to compare how the chip performs across two different benchmarks
which simplify a fraction.
The first of these benchmarks uses Euclid’s algorithm to find the greatest common factor between
the two numbers, the second works by dividing all common prime factors appearing in both numbers
until no more common factors remain. It finds these primes using the Sieve of Eratosthenes.
Both programs are given below in pseudocode.
First algorithm:
e u cli d ( numerator , denominator )
b ← numerator
a ← denominator
while b 6= 0
t ← b
b ← a mod b
a ← t
p ri n t ( numerator / a ) "/ " ( denominator / a )
Second algorithm:
e r a t o s t h e n e s ( numerator , denominator )
num ← numerator
den ← denominator
numCandidates ← min (num, den )
5
primes ← a r r ay with index 1 . . numCandidates , f i l l e d with 1 s
i ← 1
while i < numCandidates
i ← i + 1
i f primes [ i ]
primes [ j : j / i > 1 , j mod i = 0 ] = 0
while num mod i == 0 and den mod i == 0
num ← num / i
den ← den / i
p ri n t (num) "/ " ( den )
The two chips under comparison have the following properties:
1. Assignments cost 1 operation.
2. Divisions cost 5 operations.
3. Each modulo operation costs 5 operations.
4. An if branch costs 1 operation.
5. Every while branch check costs 1 operation.
6. Accessing an element of an array or a particular variable otherwise costs 0 operations.
7. All other operations are also 0 cost operations.
The new chip has the following difference: 1. The operation in the 13th line of the second algorithm,
primes[j: j / i > 1, j mod i = 0] = 0, costs 1 operation.
While on the old chip this must be implemented using a while loop. When calculating the operations
required for this, assume both conditions are always evaluated. So this will take 5 + 5 + 1
operations. Assume for a prime i that this is performed by jumping i steps forward.
To compare the performance, implement both algorithms in C, adding to the pseudocode the
number of operations required on each chip. For each algorithm find the number of operations
required on each chip for 10000 pairs of integers, varying the numerator and denominator from 1
to 100. Collect statistics on the minimum, average and maximum number of operations taken and
print these out. Your program should print out only these summary statistics. Add the summaries
of these tests to your report.
1.4 Completing the Programming Problems
We have provided you with some skeleton code for this assignment, you may freely change any
files but ensure output matches the form given in problem2a.c, problem2c.c and problem2d.c.
provided_files/
Makefile
problem2a.c
problem2c.c
problem3.c
utils.c
utils.h
6
graph.c
graph.h
pq.c
pq.h
list.c
list.h
tests/
p2a-in-1.txt
p2a-out-1.txt
p2a-in-2.txt
p2a-out-2.txt
...
p2c-in-3.txt
p2c-out-3.txt
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.
To run the programs you must first compile with make followed by one of problem2a, problem2c
or problem3. For problem2a and problem2c you can send the test case in via standard input
redirection. For problem3 you can simply run the program.
For example:
make problem2a
make problem2c
make problem3
./problem2a < p2a-in-1.txt
./problem2c < p2c-in-1.txt
./problem3
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, so must not print to stdout otherwise.
1.5 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. Further instructions on submitting your files will be provided
soon.
It is recommended that you test your program on dimefox before submitting to make sure that
your program compiles without warnings and runs as expected. If your program performs differently
on the server to how it performs locally, you may find the tool valgrind useful.
Note that programs which do not implement the algorithm they claim to or do not run within 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.
7
1.6 Completing the Written Problems
You will submit your solutions to Problems 1a, 1b, 1c, 1d, 2b, and the summary of Problem 3 via
the LMS.
For Problems 1 and 2, which ask 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 single .pdf file. Pseudocode
should be formatted similarly to lectures/workshops, or presented in a monospace font.
You should aim to keep each written problem part to less than one full page.
1.7 Mark Allocation
The total number of marks in this assignment is 10. The maximum marks for each problem are:
• Problem 1 4 marks (1 per part)
• Problem 2 3 marks (1 per part)
• Problem 3 2 marks
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 5 marks for the written problems (Problem 1 and Problem 2 (b)) and 5 marks for
the C programming problems (Problem 2 (a, c) and Problem 3).
We have provided 3 test cases for each part of Problem 2 (a, c).
The marks awarded for each part of Problem 2 will be calculated by:
Marks = max{1 − 0.5 × TestCasesFailed, 0}
So passing 0 or 1 of the test cases will award 0 marks, 2 test cases will award 0.5 marks and all 3
will award 1 mark (the maximum available).
1.8 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 also applies per component, i.e.,
Grade = max{ProgrammingGrade − 0.2 × DaysLate × 5, 0}+
max{WrittenSubmissionGrade − 0.2 × DaysLate × 5, 0}
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 × 5 = 2
and the grade for the analysis component will be reduced by 0.2 × 5 = 1.
8
1.9 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.
9
March 28, 2021
1 Assignment 1
Due: 5:00pm AEST Friday 16th of April
1.0 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.
1.1 Problem 1
A shortsighted cow, named Sam, cannot find enough grass on its current pasture. It remembers
that the pasture’s enclosing fence has a gap. Unfortunately, the fence is very long: for a full circle,
it takes Sam l steps to walk along the fence. Sam can only see the gap if it is right next to it
(remember the cow is shortsighted). In this question, you will design different algorithms that
will enable Sam to find the gap that is k steps away from its current position. Sam is always
located next to the fence. We call its start position origin. You may assume that l is much greater
than k.
1
1.1.1 Part A
We assume that the cow can go only in one direction along the fence. It has to pick one of the
two directions (say left or right) and continues until it has found the gap. Derive the worst case
complexity of this algorithm.
1.1.2 Part B
Sam’s best friend, an eagle called Indigo, can see the gap and knows the number of steps Sam has
to take, i.e., the value of k is known in this question. Unfortunately, Indigo is never sure whether
it saw the gap with its left or right eye. Hence, Indigo can tell Sam only the number of steps
Sam has to take but does not know the right direction. Design an algorithm with O(k) worst case
complexity such that Sam can find the gap. Explain why your has O(k) time complexity.
1.1.3 Part C
In this part, we assume that k is not known. Sam applies the following strategy: walk 1 step to
the right, turn around if no gap is found, and move to the start. Then walk 2 steps to the left and
return to the start if no gap is found. Then walk 3 steps to the right and return to the start, and so
forth.
2
1. First, work out the general algorithm and write it in pseudocode.
2. Second, work out the worst case time complexity of this algorithm in detail.
3. Explain whether or not this strategy is better than the one you analyzed in Part A.
1.1.4 Part D
Design an algorithm that requires O(k) time efficiency to find a gap and show that its efficiency is
indeed O(k). You do not need to write the algorithm in pseudocode (you can if you want) but you
have to describe the algorithm clearly.
1.2 Problem 2
An Internet service provider wants to deliver service to a village. They have two installation
options:
• Cabled installation. This means connecting the data center via underground cables. Connections
can be either made from the data center to a house or between houses. The cost is
equal to the distance between houses (or between a data center and a house).
• Radio-based installation. This means installing antennas in each house, which then receive
the internet signal through a satellite. The cost of an antenna installation is fixed per house
but can vary from village to village.
The figure below shows an example of a village, where distances are drawn as red arrows with
their corresponding value.
3
For this village, the corresponding textual format is shown below:
where:
• First line contains the antenna cost.
• Second line shows the number of houses followed by the number of connections in the
village.
• Remaining lines show connections where the first and second number are the houses (or 0 if
it is the data center) and the third number is the actual distance.
1.2.1 Part A
Devise a program in C that given a village map and antenna installation cost in the format described
above, returns the installation option with lower cost in total. Your program should output
the lowercase character c if cabled has the lower installation cost and r if radio-based has the
lower cost instead.
1.2.2 Part B
Explain why your program works. You can use pseudocode to help explain your solution.
1.2.3 Part C
Same as Part A, but now the company updated their infrastructure and it can now provide a mix
of cabled and radio-based installations for the village. This means that a house will have internet
access if any of the following are true:
1. There is a path to the data center,
2. The house has an antenna or
3. There is a path to a house with an antenna.
The figure below shows an example of each of the cases above. All houses below are considered
connected.
4
Modify your program in order to output the minimum total cost for this mixed installation.
1.3 Problem 3
A processor manufacturer has come up with a design for a new processor technology designed
for cryptography which is able to simultaneously check if any elements in an array of integers
are divisible by a particular number. In marketing this chip, the processor engineering team have
asked you to write a program to compare how the chip performs across two different benchmarks
which simplify a fraction.
The first of these benchmarks uses Euclid’s algorithm to find the greatest common factor between
the two numbers, the second works by dividing all common prime factors appearing in both numbers
until no more common factors remain. It finds these primes using the Sieve of Eratosthenes.
Both programs are given below in pseudocode.
First algorithm:
e u cli d ( numerator , denominator )
b ← numerator
a ← denominator
while b 6= 0
t ← b
b ← a mod b
a ← t
p ri n t ( numerator / a ) "/ " ( denominator / a )
Second algorithm:
e r a t o s t h e n e s ( numerator , denominator )
num ← numerator
den ← denominator
numCandidates ← min (num, den )
5
primes ← a r r ay with index 1 . . numCandidates , f i l l e d with 1 s
i ← 1
while i < numCandidates
i ← i + 1
i f primes [ i ]
primes [ j : j / i > 1 , j mod i = 0 ] = 0
while num mod i == 0 and den mod i == 0
num ← num / i
den ← den / i
p ri n t (num) "/ " ( den )
The two chips under comparison have the following properties:
1. Assignments cost 1 operation.
2. Divisions cost 5 operations.
3. Each modulo operation costs 5 operations.
4. An if branch costs 1 operation.
5. Every while branch check costs 1 operation.
6. Accessing an element of an array or a particular variable otherwise costs 0 operations.
7. All other operations are also 0 cost operations.
The new chip has the following difference: 1. The operation in the 13th line of the second algorithm,
primes[j: j / i > 1, j mod i = 0] = 0, costs 1 operation.
While on the old chip this must be implemented using a while loop. When calculating the operations
required for this, assume both conditions are always evaluated. So this will take 5 + 5 + 1
operations. Assume for a prime i that this is performed by jumping i steps forward.
To compare the performance, implement both algorithms in C, adding to the pseudocode the
number of operations required on each chip. For each algorithm find the number of operations
required on each chip for 10000 pairs of integers, varying the numerator and denominator from 1
to 100. Collect statistics on the minimum, average and maximum number of operations taken and
print these out. Your program should print out only these summary statistics. Add the summaries
of these tests to your report.
1.4 Completing the Programming Problems
We have provided you with some skeleton code for this assignment, you may freely change any
files but ensure output matches the form given in problem2a.c, problem2c.c and problem2d.c.
provided_files/
Makefile
problem2a.c
problem2c.c
problem3.c
utils.c
utils.h
6
graph.c
graph.h
pq.c
pq.h
list.c
list.h
tests/
p2a-in-1.txt
p2a-out-1.txt
p2a-in-2.txt
p2a-out-2.txt
...
p2c-in-3.txt
p2c-out-3.txt
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.
To run the programs you must first compile with make followed by one of problem2a, problem2c
or problem3. For problem2a and problem2c you can send the test case in via standard input
redirection. For problem3 you can simply run the program.
For example:
make problem2a
make problem2c
make problem3
./problem2a < p2a-in-1.txt
./problem2c < p2c-in-1.txt
./problem3
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, so must not print to stdout otherwise.
1.5 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. Further instructions on submitting your files will be provided
soon.
It is recommended that you test your program on dimefox before submitting to make sure that
your program compiles without warnings and runs as expected. If your program performs differently
on the server to how it performs locally, you may find the tool valgrind useful.
Note that programs which do not implement the algorithm they claim to or do not run within 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.
7
1.6 Completing the Written Problems
You will submit your solutions to Problems 1a, 1b, 1c, 1d, 2b, and the summary of Problem 3 via
the LMS.
For Problems 1 and 2, which ask 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 single .pdf file. Pseudocode
should be formatted similarly to lectures/workshops, or presented in a monospace font.
You should aim to keep each written problem part to less than one full page.
1.7 Mark Allocation
The total number of marks in this assignment is 10. The maximum marks for each problem are:
• Problem 1 4 marks (1 per part)
• Problem 2 3 marks (1 per part)
• Problem 3 2 marks
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 5 marks for the written problems (Problem 1 and Problem 2 (b)) and 5 marks for
the C programming problems (Problem 2 (a, c) and Problem 3).
We have provided 3 test cases for each part of Problem 2 (a, c).
The marks awarded for each part of Problem 2 will be calculated by:
Marks = max{1 − 0.5 × TestCasesFailed, 0}
So passing 0 or 1 of the test cases will award 0 marks, 2 test cases will award 0.5 marks and all 3
will award 1 mark (the maximum available).
1.8 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 also applies per component, i.e.,
Grade = max{ProgrammingGrade − 0.2 × DaysLate × 5, 0}+
max{WrittenSubmissionGrade − 0.2 × DaysLate × 5, 0}
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 × 5 = 2
and the grade for the analysis component will be reduced by 0.2 × 5 = 1.
8
1.9 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.
9