本次澳洲代写主要为算法设计相关的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 ﬁnal grade for this subject.

1.1 Problem 1

A shortsighted cow, named Sam, cannot ﬁnd 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 ﬁnd 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 ﬁnd 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 efﬁciency to ﬁnd a gap and show that its efﬁciency 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.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** itcsdx@outlook.com **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。