Assignment 1 – review questionsDue date June 16, 2020In this assignment we review the basic algorithms and data structures. Youhave five problems, marked out of a total of 100 marks.NOTE: Your solutions must be typed, machine readable .pdf files. Allsubmissions will be checked for plagiarism!1. You are given an array A of n distinct integers.(a) You have to determine if there exists a number (not necessarilyin A) which can be written as a sum of squares of two distinctnumbers from A in two different ways (note: m2 +n2 and n2 +m2counts as a single way) and which runs in time n2 log n in theworst case performance. Note that the brute force algorithmwould examine all quadruples of elements in A and there are n4 =O(n4) such quadruples. (10 points)(b) Solve the same problem but with an algorithm which runs in theexpected time of O(n2). (10 points)2. Suppose that you bought a bag of n bolts with nuts screwed on them.Your 5 year old nephew unscrewed all the nuts from the bolts and putboth the nuts and the bolts back into the bag. The bolts are all ofsimilar quite large size but are actually of many different diameters,differing only by at most a few millimetres, so the only way to see if anut fits a bolt is to try to screw it on and determine if the nut is toosmall, if it fits or if it is too large. Design an algorithm for matchingeach bolt with a nut of a fitting size which runs in the expected timeO(n log n). (20 points)3. You are given 1024 apples, all of similar but different sizes and a smallpan balance which can accommodate only one apple on each side. Yourtask is to find the heaviest and the second heaviest apple while makingat most 1032 weighings. (20 points)4. You are in an orchard which has a quadratic shape of size 4n by 4nwith equally spaced trees. You purchased apples from n2 trees whichalso form a square, but the owner is allowing to choose such a squareanywhere in the orchard. You have a map with the number of appleson each tree. Your task is to chose such a square which contains thelargest total number of apples and which runs in time O(n2). Note thatthe brute force algorithm would run in time Θ(n4). (20 points)15. Determine if f(n) = O(g(n)) or g(n) = O(f(n) or both (i.e., f(n) =Θ(g(n))) or neither of the two, for the following pairs of functions
(a) f(n) = (log2(n))2; g(n) = log2(nlog2 n)2;
(6 points)
(b) f(n) = n10; g(n) = 2 10 pn;(c) f(n) = n1+(-1)n; g(n) = n:
(6 points)(8 points)
2
[Button id=”1″]
Quality and affordable writing services. Our papers are written to meet your needs, in a personalized manner. You can order essays, annotated bibliography, discussion, research papers, reaction paper, article critique, coursework, projects, case study, term papers, movie review, research proposal, capstone project, speech/presentation, book report/review, and more.
Need Help? Click On The Order Now Button For Help
What Students Are Saying About Us
.......... Customer ID: 12*** | Rating: ⭐⭐⭐⭐⭐"Honestly, I was afraid to send my paper to you, but splendidwritings.com proved they are a trustworthy service. My essay was done in less than a day, and I received a brilliant piece. I didn’t even believe it was my essay at first 🙂 Great job, thank you!"
.......... Customer ID: 14***| Rating: ⭐⭐⭐⭐⭐
"The company has some nice prices and good content. I ordered a term paper here and got a very good one. I'll keep ordering from this website."
