xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

微信客服：xiaoxionga100

微信客服：ITCS521

latex代写-CSC263

时间：2022-02-07

CSC263 Winter 2022 Problem Set 1

Michelle Craig and Samar Sabie

Due: February 7, 2022 4pm ET on MarkUs

Instructions

• Your problem sets are graded on both correctness and clarity of communication. Solutions that

are technically correct but poorly written will not receive full marks.

• Each problem set may be completed as an individual or in a group of two students. Partners do

not need to be registered in the same section of the course.

• Solutions must be typeset electronically, and submitted to MarkUs as a PDF with the filename

ps1.pdf. Handwritten submissions will receive a grade of zero.

• Your submitted file should not be larger than 9MB. Your file might exceed this limit if you use

a word processor like Microsoft Word to create a PDF; if it does, you should look into PDF

compression tools to make your PDF smaller, although please make sure that your PDF is still

legible before submitting!

• The work you submit must be that of your group; you may not use or copy from the work of

other groups, or from external sources like websites or textbooks. We recognize that although

it should not be necessary to do so, students may wish to read a different textbook or

reference material about course topics. This is not prohibited, but you must declare it. (See the

next bullet). All the information you need has been covered in lectures and/or in our textbook.

• On the front page of your submission, you must list every source of information you used to

complete this homework (other than your lecture notes, our textbook, or conversations from office

hours or lectures). For example, indicate clearly the name of every student from another group

with whom you had any discussions, the title and sections of every textbook you consulted

(excluding the course textbook), the source of every web document you used or website you

visited (other than our own CSC263 site.)

1

Question 1 [15 marks]

Consider the following Python code:

1. def find_position(A: List[object], target: object) -> int:

2. """Return the index of target in A or -1 if target not found"""

3. for i in range(len(A)):

4. if A[i] == target:

5. return i

6. return -1

7. def encode(L: List[int], M: List[int], k: int) -> int:

8. """Return an integer based on L, M and k

9. Precondition: len(M) >= len(L) """

10. result = 0

11. for i in range(len(L)):

12. if L[i] == k:

13. result += M[i]

14. else:

15. result += find_position(M, L[i])

16. return result

In this question you will perform a best-case, a worst-case, and two average-case analyses of method

encode. Count item comparisons and give exact counts before you simplify to an asymptotic

expression. You may assume that the python operation len() takes constant time and does not

involve any comparisons that need to be counted in your analyses.

(a) Provide a best-case analysis.

(b) Provide a worse-case analysis.

(c) For the first average-case analysis, assume that the elements of both L and M , and the value for

k, are each chosen independently and uniformly at random from the integers 0 through 9.

(d) For the second average-case analysis, assume that lists L and M are both length n and are

random permutations of the lists [0, 1, 2, ..., n − 1]. k is chosen uniformly at random from the

set {0, 1, 2, ..., n.} Notice that when k = n, it will not match any values in L or M since these

lists do not contain n.

Question 2 [6 marks]

This problem deals with the challenge of re-distributing Covid-19 vaccination doses to match need.

Suppose that there are a very large number of distribution centres (pharmacies, doctors’ offices, hospi-

tals, clinics, etc.) and each one has either a surplus of dosages or a shortage. The central office requests

that each centre reports their status, but many distribution centres are short staffed and so the reports

arrive over a period of days. During that time, the central office staff member wants to start to address

the imbalance. So they do the following: After some initial waiting period, the staff member finds the

centre with the largest surplus and the centre with the largest shortage. They contact these centres

and arrange for some number of dosages to be transferred from one to the other. (For the sake of

this problem, we aren’t worried about how much they decide to transfer.) Once this is arranged, they

repeat this process many times. For the repeats, there are two important constraints:

2

1. Although this may be unrealistic and non-optimal, once a distribution centre has participated in

a transfer (either as a supplier or a recipient), they are not considered for any future transfers.

2. More distribution centres may have filed their status reports during the time that has elapsed

while the staff member was processing the previous transfer. Each time a staff member starts to

plan a new transfer, they consider all the centres that have filed reports at that time (other than

those disregarded because of constraint 1.)

(a) Describe the ADT that can be used to represent this problem.

(b) Describe a data-structure to efficiently implement your ADT. For each operation, give a brief

explanation (in English sentences). Provide and justify the complexity of each operation.

Question 3 [9 marks]

We define a ExtractMin-Insert-Stable (EIS) heap as a min heap with no duplicate elements where the

result of calling ExtractMin and immediately re-inserting that same element is the original heap.

(a) Provide an example of an EIS min heap with seven elements. Display both the original heap

(which is of course also the final heap) and the intermediate heap (after the call to ExtractMin)

as trees.

(b) Provide an example of a min heap with seven distinct elements that is not an EIS heap. Display

the original heap, the intermediate heap and the final heap all as trees.

(c) Formally describe the relationship between the elements that must hold for a heap to be an EIS

min heap.

(d) Prove that your description in part (c) describes all EIS min heaps and does not hold for min

heaps that are not EIS.

Question 4 [15 marks]

Consider a complete binary-tree with 2k−1 nodes and no duplicate keys. The keys in the tree obey the

binary-search-tree ordering property. Suppose that you are searching the tree for the data associated

with key v which is in the tree.

(a) What is the best-case number of nodes which must be examined to find the data associated with

v? Briefly justify your answer.

(b) What is the worst-case number of nodes which must be examined to find the data associated

with v? Prove your answer.

(c) Calculate the average-case number of nodes which must be examined. Assume that key v is in

the tree and is equally likely to be in any location in the tree. Hint: Do a sanity check on your

final formula by calculating by hand the expected number of nodes to be examined for a small

complete binary tree (say height 2 or 3).

(d) Redo the average-case analysis, under a different assumption about the probability distribution

over possible locations for v. Now assume that there is a 40% chance that v is not in the tree

and a 20% chance that it is at the root of the tree. If neither of these are the case, v is equally

likely to be in any other (non-root) location in the tree.

3

Question 5 [5 marks]

Consider that you have a binary max heap that holds the consecutive integers from 1 to n inclusive.

If the value y is in the second level of the heap, i.e. y is a child of the root, what is the possible range

of n (expressed as a function of y)? Carefully justify your answer.

4

Michelle Craig and Samar Sabie

Due: February 7, 2022 4pm ET on MarkUs

Instructions

• Your problem sets are graded on both correctness and clarity of communication. Solutions that

are technically correct but poorly written will not receive full marks.

• Each problem set may be completed as an individual or in a group of two students. Partners do

not need to be registered in the same section of the course.

• Solutions must be typeset electronically, and submitted to MarkUs as a PDF with the filename

ps1.pdf. Handwritten submissions will receive a grade of zero.

• Your submitted file should not be larger than 9MB. Your file might exceed this limit if you use

a word processor like Microsoft Word to create a PDF; if it does, you should look into PDF

compression tools to make your PDF smaller, although please make sure that your PDF is still

legible before submitting!

• The work you submit must be that of your group; you may not use or copy from the work of

other groups, or from external sources like websites or textbooks. We recognize that although

it should not be necessary to do so, students may wish to read a different textbook or

reference material about course topics. This is not prohibited, but you must declare it. (See the

next bullet). All the information you need has been covered in lectures and/or in our textbook.

• On the front page of your submission, you must list every source of information you used to

complete this homework (other than your lecture notes, our textbook, or conversations from office

hours or lectures). For example, indicate clearly the name of every student from another group

with whom you had any discussions, the title and sections of every textbook you consulted

(excluding the course textbook), the source of every web document you used or website you

visited (other than our own CSC263 site.)

1

Question 1 [15 marks]

Consider the following Python code:

1. def find_position(A: List[object], target: object) -> int:

2. """Return the index of target in A or -1 if target not found"""

3. for i in range(len(A)):

4. if A[i] == target:

5. return i

6. return -1

7. def encode(L: List[int], M: List[int], k: int) -> int:

8. """Return an integer based on L, M and k

9. Precondition: len(M) >= len(L) """

10. result = 0

11. for i in range(len(L)):

12. if L[i] == k:

13. result += M[i]

14. else:

15. result += find_position(M, L[i])

16. return result

In this question you will perform a best-case, a worst-case, and two average-case analyses of method

encode. Count item comparisons and give exact counts before you simplify to an asymptotic

expression. You may assume that the python operation len() takes constant time and does not

involve any comparisons that need to be counted in your analyses.

(a) Provide a best-case analysis.

(b) Provide a worse-case analysis.

(c) For the first average-case analysis, assume that the elements of both L and M , and the value for

k, are each chosen independently and uniformly at random from the integers 0 through 9.

(d) For the second average-case analysis, assume that lists L and M are both length n and are

random permutations of the lists [0, 1, 2, ..., n − 1]. k is chosen uniformly at random from the

set {0, 1, 2, ..., n.} Notice that when k = n, it will not match any values in L or M since these

lists do not contain n.

Question 2 [6 marks]

This problem deals with the challenge of re-distributing Covid-19 vaccination doses to match need.

Suppose that there are a very large number of distribution centres (pharmacies, doctors’ offices, hospi-

tals, clinics, etc.) and each one has either a surplus of dosages or a shortage. The central office requests

that each centre reports their status, but many distribution centres are short staffed and so the reports

arrive over a period of days. During that time, the central office staff member wants to start to address

the imbalance. So they do the following: After some initial waiting period, the staff member finds the

centre with the largest surplus and the centre with the largest shortage. They contact these centres

and arrange for some number of dosages to be transferred from one to the other. (For the sake of

this problem, we aren’t worried about how much they decide to transfer.) Once this is arranged, they

repeat this process many times. For the repeats, there are two important constraints:

2

1. Although this may be unrealistic and non-optimal, once a distribution centre has participated in

a transfer (either as a supplier or a recipient), they are not considered for any future transfers.

2. More distribution centres may have filed their status reports during the time that has elapsed

while the staff member was processing the previous transfer. Each time a staff member starts to

plan a new transfer, they consider all the centres that have filed reports at that time (other than

those disregarded because of constraint 1.)

(a) Describe the ADT that can be used to represent this problem.

(b) Describe a data-structure to efficiently implement your ADT. For each operation, give a brief

explanation (in English sentences). Provide and justify the complexity of each operation.

Question 3 [9 marks]

We define a ExtractMin-Insert-Stable (EIS) heap as a min heap with no duplicate elements where the

result of calling ExtractMin and immediately re-inserting that same element is the original heap.

(a) Provide an example of an EIS min heap with seven elements. Display both the original heap

(which is of course also the final heap) and the intermediate heap (after the call to ExtractMin)

as trees.

(b) Provide an example of a min heap with seven distinct elements that is not an EIS heap. Display

the original heap, the intermediate heap and the final heap all as trees.

(c) Formally describe the relationship between the elements that must hold for a heap to be an EIS

min heap.

(d) Prove that your description in part (c) describes all EIS min heaps and does not hold for min

heaps that are not EIS.

Question 4 [15 marks]

Consider a complete binary-tree with 2k−1 nodes and no duplicate keys. The keys in the tree obey the

binary-search-tree ordering property. Suppose that you are searching the tree for the data associated

with key v which is in the tree.

(a) What is the best-case number of nodes which must be examined to find the data associated with

v? Briefly justify your answer.

(b) What is the worst-case number of nodes which must be examined to find the data associated

with v? Prove your answer.

(c) Calculate the average-case number of nodes which must be examined. Assume that key v is in

the tree and is equally likely to be in any location in the tree. Hint: Do a sanity check on your

final formula by calculating by hand the expected number of nodes to be examined for a small

complete binary tree (say height 2 or 3).

(d) Redo the average-case analysis, under a different assumption about the probability distribution

over possible locations for v. Now assume that there is a 40% chance that v is not in the tree

and a 20% chance that it is at the root of the tree. If neither of these are the case, v is equally

likely to be in any other (non-root) location in the tree.

3

Question 5 [5 marks]

Consider that you have a binary max heap that holds the consecutive integers from 1 to n inclusive.

If the value y is in the second level of the heap, i.e. y is a child of the root, what is the possible range

of n (expressed as a function of y)? Carefully justify your answer.

4