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. Con- nections 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:
25
6 10
0 1 40
0 2 20
1 2 15
1 3 68
2 4 33
2 5 28
3 5 19
3 6 31
4 5 52
5 6 77
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 de- scribed above, returns the installation option with lower cost in total. Your program should out- put 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 num- bers until no more common factors remain. It finds these primes using the Sieve of Eratosthenes.
Both programs are given below in pseudocode. First algorithm:
euclid ( numerator , denominator ) b ← numerator
a ← denominator while b ̸= 0
t←b
b ← a mod b a←t
print (numerator / a) “/” (denominator / a)
Second algorithm:
eratosthenes ( numerator , denominator ) num ← numerator
den ← denominator numCandidates ← min (num, den )
5
primes ← array with index 1..numCandidates, filled with 1s
i←1
while i < numCandidates
i←i+1
if 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
print (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 algo- rithm,primes[j: j/i>1,jmodi=0]=0,costs1operation.
While on the old chip this must be implemented using a while loop. When calculating the oper- ations 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
Youwillsubmityourprogramviadimefox submit.Instructionsforhowtoconnecttothedimefox 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 differ- ently 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. Pseu- docode 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 compo- nent. 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 sim- ilarity 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