Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


Assignment 1, COMP252, Winter 2022



Exercise 1.  A question related to Fibonacci sequences. A Fibonacci-like sequence of integers is dened as follows: x0 =  = x9 = 1, xn = xn  5 + xn  10 , n  10.

(i) Show that xn = (cn) for some positive constant c and determine c.                

(ii) Give an algorithm that, under the ram model, computes xn in time O(log n).

Exercise 2.  Bit complexity. Give an ecient bit-level algorithm for computing 73n , and determine a good upper bound for its bit complexity in O( ) format.

 

Exercise 3.  Algorithm design: Finding the polygon that contains the origin.


Consider n lines in the plane all described by equa- tions of the form aix+biy = 1, 1  i  n. For sim- plicity, assume that all coecients are strictly pos- itive and dierent. Assume also that no three lines

meet in one point. The n lines partition the pos- itive quadrant in the plane plane into a quadratic number of polygonal regions.  The goal is to nd the collection of lines that determine the polygon that contains the origin.  These are all the lines whose union covers the border of the polygon. As- suming a ram model of computation and an oracle for nding the intersection point of two lines, give a recursive O(nlog n) algorithm for solving this problem.  Hint: Refer to the convex hull problem seen in class.


Exercise 4.  Algorithm design:  a dating service.  You are running a dating service with three groups of people, A, B and C. Each group has n individuals.  Each individual has answered yes or no to n questions in a questionnaire.  For uniformity of notation, let the i-th person’s answers in group A be denoted by a vector [A1[i],...,An[i]], and similarly for B and C, and let all answers be 0 or 1.  We dene the compatibility between person i in group A and person j in group B as the number of identical answers they gave.  Similarly, for a threesome i (from A), j (from B) and ℓ (from C), the compatibility of the threesome is the number of questions on which all three answered in the same manner.

(i) Give an algorithm for nding all pairs that have maximal compatibility.  In a ram model, it should take time O(n) with α < 3.

(ii) Give an algorithm for nding all threesomes that have maximal compatibility. In a ram model, it should take time O(n) with α < 4.