xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

java代写-CO3002/7002-Assignment 1

时间：2021-02-23

CO3002/7002 Assignment 1

Released Feb 4, 2021 Deadline Feb 22, 2021 5:00 pm

This assignment consists of two questions. The first question is to be completed individually.

The second question can be completed in groups of size up to three. Further instructions about

group work will be provided separately.

Submit your work on Blackboard, as a pdf file.

Question 1 (35 marks)

This question is to be attempted individually.

Consider the following pseudocode:

int f(int n) {

if (n>1) {

f(n/2);

f(n/2);

for(int i = 1; i <= g(n); i++) {

println("Hello world!");

}

f(n/2);

}

}

int g(int n) {

int sum = 0;

for(int i = 1; i <= n; i++) sum += i;

return sum;

}

Here println() is a function that prints a line of text. Assume n is a power of 2.

(a) Express the return value of g(n) in terms of n. [5 marks]

(b) What is the time complexity of g(n), in terms of n and in big-O? [5 marks]

(c) Let T (n) be the number of lines printed by f(n). Write down a recurrence formula for

T (n), including the base case. [5 marks]

(d) Solve the recurrence in (c), showing your working steps. For full credit give the exact

answer (not big-O) and do not use Master Theorem. [20 marks]

1

Question 2 (65 marks)

This question can be attempted in groups.

There are n samples that need to be tested for coronavirus. The testing process (known

as PCR) involves using a special machine, testing one sample at a time, which is both time-

consuming and expensive. Thus, we would like to have a method that is better than the trivial

method of testing each sample one by one sequentially. Fortunately this is possible because

we expect most samples to return a negative result (not containing the virus), and so we can

‘combine’ multiple samples to be tested together. For example, we can take one drop from each

of the samples 1, 2, 3 to form a new sample, and test this mixed sample. If it returns a negative

result, then all samples 1, 2, 3 are negative. But if it returns a positive result, we only know

some of them contain the virus and not which one(s), or indeed how many of them, contain the

virus, and further tests are needed.

Assume each individual sample contains sufficient contents so many drops can be taken from

each of them, and that if a sample contains the virus, any drop taken from it will contain the

virus.

(a) Suppose we know that exactly one of the n samples contains the virus. Design an algorithm

for identifying it that takes O(log n) tests. [20 marks]

(b) Suppose instead we know that at most one of the n samples contains the virus. Design

an algorithm for identifying the positive sample (or determine that there are none) using

as few tests as you can. [20 marks]

(c) Suppose instead we know that at most two of the n samples contain the virus. Repeat

(b). [25 marks]

In each part, you should:

• state the algorithm in pseudocode;

• explain (in words) some intuition behind your algorithm, and/or why it correctly identifies

the positive samples;

• explain mathematically (e.g. via solving a recurrence formula) the number of tests taken

by your algorithm;

• explain whether you think your algorithm is optimal by proving as good a lower bound

as you can.

You can assume n is some “nice” number such as powers of 2; state your assumptions. (You

can have different assumptions in each part if you want.)

Marking criteria

Question 1 will be marked based on correctness, according to the given mark distribution.

Partially correct answers will get partial marks. Correct steps following earlier wrong results

(e.g. stating the wrong recurrence but solving the wrong one correctly) will still yield most of

the allocated marks.

Each part of Question 2 will be marked roughly according to this table:

2

0-20% Barely any idea about the algorithm.

20-40% There are some ideas towards a correct algorithm (i.e. it will identify the

correct positive samples) but they would not lead to anywhere near the upper

bounds expected. Pseudocode / explanation / analysis all very wrong or

missing.

40-50% Some correct ideas but incomplete, or would not lead to the upper bounds

expected. Pseudocode or explanation missing or wrong. Analysis missing,

or wrong, or follows the incomplete ideas “correctly” to lead to sub-optimal

bounds.

50-60% Have the correct main ideas that would lead to the upper bounds expected,

but this is not matched by the analysis. Some of pseudocode / explanation /

analysis missing or wrong, while the others are in the right direction but have

errors.

60-70% Ideas mostly correct. At most one of the required elements missing or wrong.

Analysis have errors or do not lead to the required bounds.

70-80% Ideas mostly correct. Pseudocode have some errors. Analysis lead to correct

bounds but have errors.

80-90% Everything is mostly correct, with some small mistakes. Upper and lower

bounds match asymptotically (up to big-O).

90-100% Everything is mostly correct, with some small mistakes. Upper and lower

bounds match including multiplicative constants.

In both questions, you can use the Master Theorem unless otherwise stated (but you should

show the steps in using it). Where manual solving of recurrence is required, solving with Master

Theorem instead (and correctly) will yield 40% of the allocated marks.

3

学霸联盟

Released Feb 4, 2021 Deadline Feb 22, 2021 5:00 pm

This assignment consists of two questions. The first question is to be completed individually.

The second question can be completed in groups of size up to three. Further instructions about

group work will be provided separately.

Submit your work on Blackboard, as a pdf file.

Question 1 (35 marks)

This question is to be attempted individually.

Consider the following pseudocode:

int f(int n) {

if (n>1) {

f(n/2);

f(n/2);

for(int i = 1; i <= g(n); i++) {

println("Hello world!");

}

f(n/2);

}

}

int g(int n) {

int sum = 0;

for(int i = 1; i <= n; i++) sum += i;

return sum;

}

Here println() is a function that prints a line of text. Assume n is a power of 2.

(a) Express the return value of g(n) in terms of n. [5 marks]

(b) What is the time complexity of g(n), in terms of n and in big-O? [5 marks]

(c) Let T (n) be the number of lines printed by f(n). Write down a recurrence formula for

T (n), including the base case. [5 marks]

(d) Solve the recurrence in (c), showing your working steps. For full credit give the exact

answer (not big-O) and do not use Master Theorem. [20 marks]

1

Question 2 (65 marks)

This question can be attempted in groups.

There are n samples that need to be tested for coronavirus. The testing process (known

as PCR) involves using a special machine, testing one sample at a time, which is both time-

consuming and expensive. Thus, we would like to have a method that is better than the trivial

method of testing each sample one by one sequentially. Fortunately this is possible because

we expect most samples to return a negative result (not containing the virus), and so we can

‘combine’ multiple samples to be tested together. For example, we can take one drop from each

of the samples 1, 2, 3 to form a new sample, and test this mixed sample. If it returns a negative

result, then all samples 1, 2, 3 are negative. But if it returns a positive result, we only know

some of them contain the virus and not which one(s), or indeed how many of them, contain the

virus, and further tests are needed.

Assume each individual sample contains sufficient contents so many drops can be taken from

each of them, and that if a sample contains the virus, any drop taken from it will contain the

virus.

(a) Suppose we know that exactly one of the n samples contains the virus. Design an algorithm

for identifying it that takes O(log n) tests. [20 marks]

(b) Suppose instead we know that at most one of the n samples contains the virus. Design

an algorithm for identifying the positive sample (or determine that there are none) using

as few tests as you can. [20 marks]

(c) Suppose instead we know that at most two of the n samples contain the virus. Repeat

(b). [25 marks]

In each part, you should:

• state the algorithm in pseudocode;

• explain (in words) some intuition behind your algorithm, and/or why it correctly identifies

the positive samples;

• explain mathematically (e.g. via solving a recurrence formula) the number of tests taken

by your algorithm;

• explain whether you think your algorithm is optimal by proving as good a lower bound

as you can.

You can assume n is some “nice” number such as powers of 2; state your assumptions. (You

can have different assumptions in each part if you want.)

Marking criteria

Question 1 will be marked based on correctness, according to the given mark distribution.

Partially correct answers will get partial marks. Correct steps following earlier wrong results

(e.g. stating the wrong recurrence but solving the wrong one correctly) will still yield most of

the allocated marks.

Each part of Question 2 will be marked roughly according to this table:

2

0-20% Barely any idea about the algorithm.

20-40% There are some ideas towards a correct algorithm (i.e. it will identify the

correct positive samples) but they would not lead to anywhere near the upper

bounds expected. Pseudocode / explanation / analysis all very wrong or

missing.

40-50% Some correct ideas but incomplete, or would not lead to the upper bounds

expected. Pseudocode or explanation missing or wrong. Analysis missing,

or wrong, or follows the incomplete ideas “correctly” to lead to sub-optimal

bounds.

50-60% Have the correct main ideas that would lead to the upper bounds expected,

but this is not matched by the analysis. Some of pseudocode / explanation /

analysis missing or wrong, while the others are in the right direction but have

errors.

60-70% Ideas mostly correct. At most one of the required elements missing or wrong.

Analysis have errors or do not lead to the required bounds.

70-80% Ideas mostly correct. Pseudocode have some errors. Analysis lead to correct

bounds but have errors.

80-90% Everything is mostly correct, with some small mistakes. Upper and lower

bounds match asymptotically (up to big-O).

90-100% Everything is mostly correct, with some small mistakes. Upper and lower

bounds match including multiplicative constants.

In both questions, you can use the Master Theorem unless otherwise stated (but you should

show the steps in using it). Where manual solving of recurrence is required, solving with Master

Theorem instead (and correctly) will yield 40% of the allocated marks.

3

学霸联盟