C-1.24 Suppose that each row of an n × n array A consists of 1\'s and 0\'s such
ID: 3881212 • Letter: C
Question
C-1.24 Suppose that each row of an n × n array A consists of 1's and 0's such that, in any row of A, all the 1's come before any O's in that row. Assuming A is already in memory, describe a method running in O(n) time (not O(n2) time) for finding the row of A that contains the most 1's. C-1.25 Suppose that each row of an n × n array A consists of 1's and 0's such that, in any row i of A, all the 1's come before any O's in that row. Suppose further that the number of 1's in row i is at least the number in row i + 1, for i = 0,1,.., n-2. Assuming A is already in memory, describe a method running in O(n) time (not O(n2) time) for counting the number of I's in the array A C 1.26 Describe, using pseudocode, a method for multiplying an n × m matrix A and an rn xp matrix B. Recall that the product C = AB is defined so that C[i][5] = 1 A|ilk] . B[k][5]. What is the running time of your method?Explanation / Answer
Assume the following matrix :
1 1 0 0 0 0
1 1 0 0 0 0
1 1 1 0 0 0
1 1 1 1 1 0
1 1 1 1 0
1 1 1 1 1
Now check the end position is a non - decreasing sequence, so we can end up checking from 1 - n.
Here is simple pseudo code :
count_ones ( A , N )
z = 0;
for ( i = 0 ; i<n ; ++i)
if(A[n - 1][i] ! = '1' ) break
++z
y = z
for ( j = n -2 ; j >= 0 ; --j)
y + = z
for ( i = z ; i < n ; ++i)
if ( A[j][i] ! = '1' ) break
++z
++y
return y
The comparisons made here can be represented as :
T(n) = T( n - 1 ) + 2
T(n - 1 ) = T(n - 2 ) + 2
T( n -2) = T( n - 3 ) + 2
Now substitute the values :
T( n - 1 ) = [T(N - 3 ) + 2 ] + 2 = T(n - 3 ) + 4
T(n) = [T(n - 3) + 4 ] + 2 = T(n - 3) + 6
Therefore , T(n ) = T( n - i ) + 2i
T(n) = T( n - ( n - 1) + 2 ( n - 1) = T(1) + 2n - 2 = 1 + 2n - 1 = O(n)
Which is O(n) + O(n) = O(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.