2023年11月25日

算法设计代写 | Algorithm Design Assignment 1

本次澳洲代写主要为算法设计相关的assignment

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 10marks 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 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.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.