We want to dial an N-digit number using a dial pad shown below. In every step,

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Problem 1: Linear Algebra

We want to dial an N-digit number using a dial pad shown below. In every step, we are just allowed to move either vertically or horizontally to one of the neighbor numbers. For example, the red lines in the figure show three possible paths from number 2 and blues show two possible paths from number 7. So, if we start from number 2 and want to dial a 2-digit number, we just need one move and can only dial 21, 23 and 25. Starting from number 0, we have only one pos- sible move to number 8. The question is if we start from number S and want to dial an N-digits number, how many distinct numbers, Ω(S, N ), can be dialed? For instance, Ω(0, 2) =  1, and Ω(2, 2) = 3.

Let’s solve this question step-by-step using linear algebra. Consider a 10 10 matrix which is defined as follows: 

1, if i to j is an allowed move

0, if i to j is a forbidden move

 For clarity, let’s identify all elements of the matrix. A00 = 0, since moving from number 0 to itself is forbidden. The only possible move from 0 is to 8, so A08 = 1 and A01 = A02 = A03 = A04 = A05 = A06 = A07 = A08 = 0. Keep doing it for all other rows of the matrix and construct A as follows:

Imagine we have started from number S, so N − 1 digits are left to be dialed. Starting from S, we can only dial an allowed set of numbers, {j|ASj  = 1}. Therefore, Ω(S, N ) can be calculated recursively by adding Ω(k, N − 1) values for k ∈ {j|ASj  = 1}.

Ω(S, N ) =

k∈{j|ASj=1}

 Ω(k, N − 1)

 Note that Ω(1) corresponds to the starting point before we move to the second digit of the number. So, It is a 10 × 1 matrix with all the elements equal to 1.

That’s it! We solved the problem. Let’s write a Python code to find Ω(N ) for a given N.

Let’s evaluate the algorithmic efficiency of our code. We can use Python’s time module to evaluate the time needed to execute the code for a given N. The figure below shows the execution time as  a function of N while running the code on my own laptop. The time increases linearly with the number of digits, so in Big O notation, its performance can be written as (N ).

f) Using time module of Python, evaluate the algorithmic efficiency of your code in part

d. You need to make the similar figure shown above on your computer.

g) How long will running your code for N = 107 take? You do not run your code for this big number of digits! Use extrapolation to estimate the running time. Do you think we need to improve the performance of our code to execute it for large numbers?

Let’s improve the performance of the code. We can express any number in the base-2 numeral system (”0” and ”1”). Any decimal number can be expressed with a series of zeroes and ones (ai):

Decimal number = ai2i

For example, 22 = 1 24 + 0 23 + 1 22 + 1 21 + 0 20. So, 22 in the binary system is 10110.

h) Write your own function which takes a decimal number and return the number in the binary system. Do not use bin() syntax of python.

In part b, you derived that Ω(N ) = AN−1 ×Ω(1), so writing N − 1 in the binary system, N − 1 =

i

Ω(N ) = AN−1 × Ω(1) = AΣ aj 2j × Ω(1) = Π(A2j )aj × Ω(1) = ... × (A4)a2 × (A2)a1 × Ω(1)

For clarity if we want to find Ω(23), it can be explained as follows:

Ω(23) = A22 × Ω(1) = (A16)1 × (A8)0 × (A4)1 × (A2)1 × Ω(1)

So, we just need to start from computing A2 and multiplying it by itself to get A4 and again multiply by itself to get A8 and so on. Instead of doing 22 matrix multiplications, we only do 6

 multiplications to get A22.

Problem 2: A simple dimensionality reduction

In this problem, we will use a principal component analysis (PCA) to map a 2-D data set to 1-D space. Consider a set of 10, 2-D data points given in a 10 × 2 matrix below:

The covariance matrix describes how the two variables (first column and second column of matrix D) change together. We want to map our data to a vector which directs towards the most variance. This direction can be translated to finding the eigenvector of covariance matrix with the largest eigenvalue.

Attachments:

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme