Algorithm Concepts

Assignment #1 (10 marks) (Due date: Feb 24)

Written:

1. Write the definition of 𝜃 (0.5 mark);

then prove that 𝜃(𝑓(𝑛)) = 𝑛3 when 𝑓(𝑛) = 5𝑛3 + 2𝑛2 − 4. Find𝐶0, 𝐶1,𝑛0. (1.5 marks)

2. Find 𝜃(𝑛) for the following recurrence for the running time:

2.1 𝑇(𝑛) = 𝛼𝑇(𝑛 − 1) + 1 (0.75 marks)

2.2 𝑇(𝑛) = 3𝑇 ( 𝑛

3 ) + 1 (0.75 marks)

2.3 𝑇(𝑛) = 𝑇 ( 𝑛

2 ) + 1 (0.75 marks)

3. In Chapter 4 of our reference book (Introduction to algorithms), read Strassen’s algorithm for

matrix multiplication and answer the following questions.

3.1 Write the recurrence for the running time of Strassen’s algorithm and find its 𝜃. (0.5 marks)

3.2 Use the algorithm to compute the matrix product:

( 7 4 1 3

) ( 5 3 2 5

)

Show your work. (0.25 marks)

Programming: (5 Marks)

1. Implement a divide and conquer algorithm for the following problem.

You have an 𝑛 × 𝑛 board, where 𝑛 = 2𝑘. One of the cells is black. You should fill the board with

an L shape which is a 2 × 2 tile with a missing cell without any overlaps with the black or L

shapes. You are allowed to rotate the L shape 90 degree multiple times. Explain your algorithm

and evaluate its time complexity.

(3,3)

(0,0) (1,0)

Given board and

index of its cells

L shape

Result

Input: n,a,b.

n: number of cells in rows and columns,

a: X index of the black cell,

b: Y index of the black cell.

For example for the above example, input is:

4,1,2. Since the board is 4 by 4 and the black cell is located at (1,2).

Output: a sequence of a,b,d for all the L shapes in the form of a0,b0,d0; a1,b1,d1;….;

ak,bk,dk.

a: X index of the yellow cell in L shape,

b: Y index of the yellow cell in L shape,

d: degree of the rotation.

For example: 0,0,270; 0,3,0; 2,1,180; 3,0,180; 3,3,90; is the output for the above example.

Both output and input are given as text files.

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.