For each problems segment given below, do the following: Create an algorithm to

Question

For each problems segment given below, do the following:

Create an algorithm to solve the problem

Identify the factors that would influence the running time, and which can be known before the algorithm or code is executed. Assign names (such as n) to each factor.

Identify the operations that must be counted. You need not count every statement separately. If a group of statements always executes together, treat the group as a single unit. If a method is called, and you do not know the running time of that method, count it as a single operation.

Count the operations performed by the algorithm or code. Express the count as a function of the factors you identified in Step 2. If the count cannot be expressed as a simple function of those factors, define the bounds that can be placed on the count: the best case (lower bound) and worst case (upper bound).

Determine what the Best Case Inputs are, and the Worst Case Inputs are, and the efficiency of your implementation

Transform your count formula into big-O notation by:

Taking the efficiency with worst case input,

Dropping insignificant terms.

Dropping constant coefficients.

a. Determine if 2 arrays contain the none of the same elements elements (assume all elements are distinct)
b. Counting total number characters that have a duplicate within a string (i.e. "gigi the gato" would result in 7 (g x 3 + i x 2 + t x 2)
c. Finding a row where every entry is 'a' in a 2-D array.

Explanation / Answer

a.

Algorithm SameOrNot( A,B)

n=length(n)

if n != length(B)

return false

for i =1 to n

flag = false

for j =1 to n

if A[i]==B[j]

flag=true

If flag != true

return false

The factor that effects the running time is the length of the arrays.

·         If the lengths of two arrays are not same, then the program returns false and thus executes in two steps(constant time).

·         If the lengths are same, then the algorithm searches each element of first array in the second

array.

Counting operations:

Best and worst case inputs:

·         Two arrays with only one element is the Best case input, because the algorithm runs in constant time.

·         Two arrays with same and equal number of elements are the worst case input, because the two loops will be executed completely.

Big-O notation:

Count =2n2+3n+6 = O(n2) [ remove insignificant and constant coefficients]

b.

Here consider the string as a character array. Sort the given string and then compare side by side characters for finding count of duplicates.

Algorithm countDuplicates(str)

n=length(str)

for i=1 to n

for j=1 to n

if str(i)>str(j)

ch=str(i)

str(i)=str(j)

str(j)=ch

dup_count=0

equal=false

10. for i =1 to n-1

if str(i)==str(i+1)

dup_count= dup_count +1

If equal==false

dup_count= dup_count +1

equal=true

else

equal=false

return dup_count

The factor that effects the running time is the length of the string.

·         If the given string has length n and has some duplicate characters, the algorithm sorts the string first and then checks all side by side characters that whether are same or not.

·         whenever the side by side characters are same, it increments the count. Finally returns the count.

Counting operations:

Best and worst case inputs:

·         The string with one character is the Best case input.

·         The string with n same characters is the worst case input.

Big-O notation:

Count =5n2 +9n-1= O(n2) [ remove insignificant and constant coefficients]

Count of each statement n=length(n) 1 if n!=length(B) 1 return false 1 for i=1 to n n+1 flag = false n+1 for j=1 to n n*(n+1)=n2 if A[i] = B[j] n*n=n2 flag = true 0 or 1 if flag!=true n return false 1 total count 2n2+3n+6

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.