answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
ozzi
2 years ago
15

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 0’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 1’s in the array A.
Computers and Technology
1 answer:
Anna71 [15]2 years ago
8 0

Answer:

Check the explanation

Explanation:

  •    Each row of nxn array A consists of 1’s and 0’s such that , in any row of A, all the 1’s come before any 0’s in that row.
  •    Use binary search algorithm to find the index of the last 1 in a row.
  •    Perform this process for each row.
  •    Now, searching for last occurrence of 1 in a row will take O (log n) time.
  •    There are n such rows, therefore total time will be O (n log n).

Complexity analysis:

   The method would be to use binary search for each row to find the first zero starting with index of A[i][n/2+1].

   Let’s say j=n/2.

   The number of 1’s in a row would be j+1.

   This would take O (log n).

   An algorithm that divides by 2 until the number gets sufficiently small then it terminates in O (log n) steps.

   As there are n rows the complexity would be O (n log n).

Pseudo-code:

A = [[1,0,0,0],[0,0,0,0],[1,1,1,1],[1,1,0,0]]

n=4

c=0

for i in range(n): # Loop in rows

  j = n/2 # Search from middle index

  while j>0: # Loop in column

      if(A[i][j]==0): # search for first zero

          if(A[i][j-1]==1): # confirm first zero

              c = c+j # add 1's count to c

              break

          else: # reduce index by 1 or j/2

              if(j/2 == 0):

                  j = j-1

              else:

                  j = j - j/2

      else: # increase index by 1 or j/2

      if(j/2 == 0):

      j = j+1

      else:

          j = j + j/2

      if(j==n): # For all 1's

      c = c+n

      break  

print c

You might be interested in
The tuna marketers' task in the "tunathewonderfish.com" website and related campaign was to ________.
Wewaii [24]
The answer to this question is "to monitor all the elements of the marketing mix for a Oregon winery". This is the main task of the tuna marketer's task in the emailing or website which is very known s tunwonderfish.com and this compaign was exclusively related to the elements of mixing in a large Oregon winery but not including the production.
4 0
2 years ago
Write a function named shout. The function should accept a string argument and display it in uppercase with an exclamation mark
Andrei [34K]

Answer:

void shout(String w) {

System.print.out(w + "!")

}

3 0
1 year ago
Program MATH_SCORES: Your math instructor gives three tests worth 50 points each. You can drop one of the test scores. The final
Simora [160]

Answer:

import java.util.Scanner;

public class num5 {

   public static void main(String[] args) {

       Scanner in = new Scanner(System.in);

       //Prompt and receive the three Scores

       int score1;

       int score2;

       int score3;

       do {

           System.out.println("Enter first Score Enter score between 1 -50");

           score1 = in.nextInt();

       } while(score1>50 || score1<0);

       do {

           System.out.println("Enter second Score.The second score must be between 1 -50");

           score2 = in.nextInt();

       } while(score2>50 || score2<0);

       do {

           System.out.println("Enter Third Score Third score must between 1 -50");

           score3 = in.nextInt();

       } while(score3>50 || score3<0);

       //Find the minimum of the three to drop

       int min, min2, max;

       if(score1<score2 && score1<score3){

           min = score1;

           min2 = score2;

           max = score3;

       }

       else if(score2 < score1 && score2<score3){

           min = score2;

           min2 = score1;

           max = score3;

       }

       else{

           min = score3;

           min2 = score1;

           max = score2;

       }

       System.out.println("your entered "+max+", "+min2+" and "+min+" the min is");

       int total = max+min2;

       System.out.println("Total of the two highest is "+total);

       //Finding the grade based on the cut-off points given

       if(total>=90){

           System.out.println("Grade is A");

       }

       else if(total>=80){

           System.out.println("Grade is B");

       }

       else if(total>=70){

           System.out.println("Grade is C");

       }

       else if(total>=60){

           System.out.println("Grade is D");

       }

       else{

           System.out.println("Grade is F");

       }

   }

}

Explanation:

  • Implemented with Java
  • Use the scanner class to receive user input
  • Use a do.....while loop to validate user input for each of the variables. A valid score must be between 0 and 50 while(score>50 || score<0);  
  • Use if and else to find the minimum of the three values and drop
  • Add the two highest numbers
  • use if/else if /else statements to print the corresponding grade
8 0
2 years ago
Write a program that has the following String variables: firstName, middleName, and lastName. Initialize these with your first,
Licemer1 [7]

Answer:

The programming language is not stated; However, I'll answer your question using C++ programming language.

Comments are used for explanatory purpose

Program starts here

#include<iostream>

#include <string>

using namespace std;

int main()

{

//Declare Variables

string firstName, middleName, lastName;

char firstInitial, middleInitial, lastInitial;

/*Initialize firstName, middleName and lastName (Replace values with your details)*/

firstName = "First Name";

middleName = "Middle Name";

lastName = "Last Name";

 

// Get Initials

firstInitial = firstName.at(0);

middleInitial = middleName.at(0);

lastInitial = lastName.at(0);

 

//Print Results

cout<<"Lastname: "<<lastName<<endl;

cout<<"Firstname: "<<firstName<<endl;

cout<<"Middlename: "<<middleName<<endl;

cout<<"Last Initial: "<<lastInitial<<endl;

cout<<"First Initial: "<<firstInitial<<endl;

cout<<"Middle Initial: "<<middleInitial<<endl;

return 0;

}

3 0
2 years ago
A computer’s memory is composed of 8K words of 32 bits each. How many bits are required for memory addressing if the smallest ad
victus00 [196]

Answer:

The minimum number of bits necessary to address 8K words is 13.

Explanation:

You have the number of words to address that is 8000 words, a word is the smallest addressable memory unit.  

8000 words can be addressed with 2^{n}  units. Now you have to find the value of n that approximates to the number of words.  

2^2=4\\2^4=16\\2^7=128\\2^{10}=1024\\2^{12}=4096\\2^{13}=8192

So you can see that 13 bits are needed to address 8K words.

7 0
2 years ago
Other questions:
  • Instructions:Type the correct answer in the box. Spell all words correctly.
    5·2 answers
  • Which of the following best describes the concept behind Web 2.0
    5·1 answer
  • Which perspective is usually used in process simulations?
    6·1 answer
  • Which one of the following is NOT true about energy conversion devices? Group of answer choices Total Energy Input = Energy Diss
    8·1 answer
  • dam is writing a program that: 1) has the user guess a number, and 2) tells the user how many guesses it took to get the correct
    9·1 answer
  • Choose the attribute used to provide accessibility by configuring a text alternative that is available to browsers and other use
    14·1 answer
  • You'd like to change the minimum password length policy in the Default Domain Policy group policy preference (GPO). What's the b
    10·1 answer
  • Look at the following array definition:
    11·1 answer
  • Define a method printAll() for class PetData that prints output as follows with inputs "Fluffy", 5, and 4444. Hint: Make use of
    13·1 answer
  • For a data structure, such as a stack, who is responsible for throwing an exception if the stack is empty and a pop() is called:
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!