## Assignment 1

C语言代写 1.0 IntroductionThis assignment contains 3 problems. You will be required to write pseudocode and C code. As well as provide a detailed ···

**Assignment 1 c语言代写**

**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 fifinal grade for this subject.

**1.1 Problem 1 **

A shortsighted cow, named Sam, cannot fifind 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 fifind 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 c语言代写**

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 fifind 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.

- First, work out the general algorithm and write it in pseudocode.
- Second, work out the worst case time complexity of this algorithm in detail.
- Explain whether or not this strategy is better than the one you analyzed in Part A.

**1.1.4 Part D c语言代写**

Design an algorithm that requires *O*(*k*) time effificiency to fifind a gap and show that its effificiency 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 fifixed per house but can vary from village to village.

The fifigure below shows an example of a village, where distances are drawn as red arrows with their corresponding value.

### For this village, the corresponding textual format is shown below: c语言代写

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 fifirst 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 c语言代写**

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:

- There is a path to the data center,
- The house has an antenna or
- There is a path to a house with an antenna.

The fifigure below shows an example of each of the cases above. All houses below are considered connected.

Modify your program in order to output the **minimum total cost **for this mixed installation

**1.3 Problem 3 c语言代写**

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 fifirst of these benchmarks uses Euclid’s algorithm to fifind 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 fifinds these primes using the Sieve of Eratosthenes. Both programs are given below in pseudocode.

### First algorithm: **c语言代写**

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 )

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: **c语言代写**

- Assignments cost 1 operation.
- Divisions cost 5 operations.
- Each modulo operation costs 5 operations.
- An if branch costs 1 operation.
- Every while branch check costs 1 operation.
- Accessing an element of an array or a particular variable otherwise costs 0 operations.
- 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.

**c语言代写**

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 fifind 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 ****c语言代写**

We have provided you with some skeleton code for this assignment. You may freely change any fifiles 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

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 Makefifile so that your program can be compiled on dimefox using the make command.

To run the programs you must fifirst 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: C语言代写

make problem2a

make problem2c

make problem3

./problem2a < p2a-in-1.txt

./problem2c < p2c-in-1.txt

./problem3

The pXX-in-X.txt fifiles contain the input your program will be provided for each test case. And the pXX-out-X.txt fifiles contain the expected output. Your program must match the expected output exactly. So *must not print to stdout *otherwise.

**1.5 Programming Problem Submission C语言代写**

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 fifiles 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 fifind 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 specifific test cases we have provided will result in a mark of 0 for the whole assignment.

**1.6 Completing the Written Problems C语言代写**

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 suffificient 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 fifile. 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 C语言代写**

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 fifiles), and how you separate your types and functions across these fifiles.

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 C语言代写**

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.

**1.9 Academic Honesty C语言代写**

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.