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

Analysis of Algorithms

(Computer Science 3340b)

ASSIGNMENT 1

Due date: Thursday, February 1, 2024, 11:55PM

1. Find the formula for the summation：1(n) i(i + 1). Hint: i(i + 1) = ( (i + 1)3  - i3  - 1 )/3.

2. The Lucas numbers is deined as follows: Ln  = Ln-1  + Ln-2 ,   n > 1;  L1  = 1;  L0  = 2. Prove that Ln  = Fn-1  + Fn+1,  n > 0 where Fi  is the Fibonacci number.

3.  Exercise 2.3-5 (pp. 44) in the textbook. See Figure 1.

4.  Problem 2-1, a., b., and c.  (pp. 45) in the textbook. See Figure 2.

5.  Read the textbook for the deinition of o and ω and answer Problem 3-2 (pp.  71) in the textbook. See Figure 3.

6.  Suppose that the running time of a recursive program is represented by the following recurrence relation:

T (2)         2c

T (n)         2T (n/2) + cn log2 (n)   n > 2

Determine the time complexity of the program using recurrence tree method (not using master theorem) and then prove your answer.

7.  Consider the Lucas numbers:

Ln  = Ln-1 + Ln-2 , n > 1; L1  = 1; L0  = 2.

a) Write a recursive function to compute Ln using the above deinition directly. Implement your solution and print Li*5, where 0     i     10, as output.

b) Write a recursive function/procedure to compute Ln  with time complexity O(n) (more precisely, the time complexity should be O(nA(n)) when n is large, where A(n) is the complexity of adding Ln-1  and Ln-2 ). Implement your solution and print Li*20, where 0     i     25, as output.  This program must be able to compute Ln  precisely for n      500. Hint 1:

Let Kn  =（ Ln(L)n  1  ) :  Kn  =（  1(1)   0(1) ) 根 Kn-1 , n ≥ 1;  K0  =（  21 )

With this formulation, design a recursive algorithm for Kn  such that the algorithm will return both Ln  and Ln-1  with input parameter n.

Hint 2: Can you use a primitive type to store L500 ?

For programs in 7 a) and 7 b) of this question, you are NOT allowed to use Python. For C++ and Java, you can only use primitive types such as char, int, long and long long. You are not allowed to use large integer, such as BigInteger in Java, from the language library. You have to write your own large integer class or data type, if needed.

c)  Use the Unix time facility (bash time command) to track the time needed for each algorithm. Compare the results and state your conclusion in two or three sentences.

d)  Can you use your program in 7 a) to compute L50  if int type of 4 bytes is used?  Briely explain your answer. Explain why your program in 7 b) can computes L500  precisely?

Algorithms and answers for 7 b) to 7 d) should be in asn1 solutions.pdf

For this question, for C++, when compiling option O2 could be considered and a makeile should be written such that the command ”make clean” will remove all the ”*.o” iles, the command ”make asn1 a” will generate an executable ile ”asn1 a” for 7 a) that can be run by typing ”asn1 a”; and the command ”make asn1 b” will generate an executable ile ”asn1 b” for 7 b) that can be run by typing ”asn1 b”.  If you are using Java, you may not need the makeile. In that case, you should have shell script iles, ”asn1 a” and ”asn1 b” such that by typing, ”asn1 a” and ”asn1 b”, your java programs will run .

You should use unix command ”script” to capture the screen of the execution of your program.

Your programs have to be able to run on compute.gaul.csd.uwo.ca as our TAs will be marking your programs there.