# Need Someone Good Expert In Data Structure And Algorithm Also Discrete Math And Convex Hull Need someone good expert in data structure and algorithm also d

**Need someone good expert in data structure and algorithm also discrete math and convex hull**

CMPSC 465 Data Structures & Algorithms

Spring 2022 Chunhao Wang and Mingfu Shao Assignment 03

Due: Friday 11:59 am, Feb. 04, 2022

Instructions: You may work in groups of up to three people to solve the homework. You must write your

own solutions and explicitly acknowledge everyone whom you have worked with or who has given you any

significant ideas about your solutions. You may also use books or online resources to help solve homework

problems. All consulted references must be acknowledged. The acknowledgements need to be made by

answering Problem 1 below.

You are encouraged to solve the problem sets on your own using only the textbook and lecture notes as a

reference. This will give you the best chance of doing well on the exams. Relying too much on the help of

group members or on online resources will hinder your performance on the exams.

Submissions being late in 2 hours will be accepted with a 20% penalty. Submissions late more than 2 hours

will receive 0. There will be no exceptions to this policy, as we post the solutions soon after the deadline.

For the full policy on assignments, please consult the syllabus.

Formatting: Start a new page for each problem.

Describing an Algorithm: Please make sure you use plain wording to explain your algorithm. It is always

a good practice to start with a summary of the high-level idea of your algorithm to ease graders understand

your solution quickly. Then, explain your algorithm, using plain wording and including enough details.

The use of pseudo-code is optional, and it is your decision. No matter you use it or not, above description in

words is always required. The pseudo-code has its own advantage in explaining structured (i.e., if-else, for-

loop, recursive functions, etc) algorithms and in putting details in the right place. If you think pseudo-code

better explains your algorithm, and/or helps graders understand your solution, and/or contains more details

not included in the plain-wording description, then use pseudo-code. If you think everything is already

clearly explained in the description with words, then you don’t need to include pseudo-code. An algorithm

that is only written in pseudo-code (i.e., missing above plain-wording description) is not acceptable, as it is

extremely hard to read just pseudo-code without any explanation.

Here is a general situation that may help you decide whether to use pseudo-code or not. An algorithm could

be “designed from scratch”, i.e., you will need to come up with the step-by-step procedure. This usually

involves in implementing a function with clear input and output. In this case, including pseudo-code usually

helps. All algorithm we’ve seen so far (e.g., merge-two-sorted-arrays, merge-sort, etc) falls in this category.

Second, an algorithm could also be ”transformed into another algorithm”, i.e., you use an existing algorithm

to solve this problem. In this case you usually don’t need to include pseudo-code but to describe how to

transform one problem into the other. We will see such examples soon.

CMPSC 465, Spring 2022, Assignment 03 1

0. (0 pts.) Acknowledgements. The assignment will receive a 0 if this question is not answered.

1. If you worked in a group, list the members of the group. Otherwise, write “I did not work in a group.”

2. If you received significant ideas about your solutions from anyone not in your group, list their names

here. Otherwise, write “I did not consult anyone except my group members”.

3. List any resources besides the course material that you consulted in order to solve the material. If you

did not consult anything, write “I did not consult any non-class materials.”

1. (15 pts.) Run the combine step of the divide-and-conquer algorithm for convex hull on the instance given

below. You are given C1 = (p1, p10, p9, p3, p5) and C2 = (p8, p6, p4, p2, p7, p11).

1. Find the lowest point p∗ in C1 ∪C2.

2. Transform C1 into C′1 so that points in C

′

1 is sorted in increasing angle w.r.t. p

∗.

3. Partition C2 into two lists C2a and C2b so that each list is sorted in increasing angle w.r.t. p∗.

4. Give list C′2 by merging C2a and C2b so that each points in C

′

2 is sorted in increasing angle w.r.t. p

∗.

5. Give list C′ by merging C′1 and C

′

2 so that each points in C

′ is sorted in increasing angle w.r.t. p∗.

6. Run Graham-Scan-Core algorithm to find convex hull of C′. Show stack operations at each step (to

deal with each point). For example, you need to write like ”For A: push A; pop B”, which indicates

when you process point A, push A into stack and also pop B out.

p1

p2

p4

p6

p7

p3

p9

p10

p5

p8

p11

2. (10 pts.) Given n points p1, p2, …, pn in 2D-plane and a slope a, we want to find two closest lines with

functions y = ax + b1 and y = ax + b2, b1 ≤ b2, so that all n points are in or on between these two

lines. Construct an algorithm with the time complexity O(n) and justify your algorithm. Describe your

algorithm (you do not need to give a pseudo code) and analyze the running time of your algorithm.

3. (10 pts.)

1. Let P be a set of n points (p1, p2, · · · , pn) in a plane. A point pi ∈ P is maximal if no point in P is

both above and to the right of pi. Give a set P with 6 points such that there is only one point on the

CMPSC 465, Spring 2022, Assignment 03 2

convex hull of P but this point is not maximal, and there is only one point that is maximal but not on

the convex hull of P . Include a visual illustration of these 6 points and the convex hull. Specifically,

point out which is the point that is on the convex hull but not maximal, and which is the maximal point

but not on the convex hull.

2. Design an instance of convex hull problem with 6 points, such that if Graham-Scan algorithm runs on

your instance, the sequence of stack operations is (push, push, push, push, pop, push, pop, pop, push).

Include a visual illustration of these 6 points and the convex hull.

4. (10 pts.) You are given n points P = {p1, p2, · · · , pn} on 2D plane, represented as their coordinates. You

are informed that the convex hull of P contains O(

√

log n) points in P . Design an algorithm to compute

the convex hull of P in O(n ·

√

log n) time. Describe your algorithm and analyze its running time. You may

assume that no three points in P are on the same line.

5. (0 pts.) (NOTE: you don’t need to submit your solution for this problem.) Given two sorted arrays A and

B of size m and n respectively, and an integer k, 1 ≤ k ≤ m + n, design an algorithm to find the k-th

smallest number in A and B. Describe your algorithm and analyze the running time of your algorithm. Your

algorithm should run in O(log(m + n)) time.

Solution: We cannot afford merging A and B, as it takes linear time rather than the desired logarithmic

time. The idea of the algorithm is to reduce k by half using a single comparison. Specifically, each time

we compare A[mid1 − 1] and B[mid2 − 1], where mid1 = min(m, k/2) and mid2 = min(n, k/2). If

A[mid1−1] > B[mid2−1], we eliminate all the elements before B[mid2], because it is impossible for the

k-th smallest value to be located before and including B[mid2−1]; otherwise, we eliminate all the elements

before A[mid1].

Define function find-kth-smallest(A, m, B, n, k) return the k-th smallest number of A[0 · · ·m) and B[0 · · ·n).

We assume A and B start with index 0. We also assume A and B represent “pointers” to the array, i.e., we

will use A + 3 to represents the array shifted 3 elements. The pseudocode is shown below:

function: find-kth-smallest(A, m, B, n, k)

if m == 0 then

return B[k − 1]

end

if n == 0 then

return A[k − 1]

end

if k == 1 then

return min(A[0], B[0])

end

mid1 = min(m, k/2), mid2 = min(n, k/2);

if A[mid1 − 1] > B[mid2 − 1] then

return find-kth-smallest(A, m, B + mid2, n−mid2, k −mid2)

end

return find-kth-smallest(A + mid1, m−mid1, B, n, k −mid1)

In above algorithm, at each recursive level, either k is halved, or one array is completely eliminated (and

then in the next recursive call the algorithm terminates). The running time is T (k) = T (k/2) + Θ(1) ⇒

T (k) = Θ(log k).

CMPSC 465, Spring 2022, Assignment 03 3