6. For the following pseudo-code for i 1 to n for j 1 to i fork- 1 to j print \"
ID: 668869 • Letter: 6
Question
6. For the following pseudo-code for i 1 to n for j 1 to i fork- 1 to j print "Hello world" (a) Exactly how many times is the print statement on line 4 executed? Your answer should be a function of n. (b) What is the run-time complexity of the code? 7. Given the following events (assuming two fair six-sided dice): HW 1 CS557B Algorithms Rivier University Fall 2015 E1 The first die has a odd number a The second die has an odd numbe E2 E3 The sum of the two values is odd Show whether the following events are independent or not: (a) E1 and E2 (b) E2 and E3 (c) E1 and E3 (d) E1 and E2 and E3 8. Given a set of 4 integers, how would you go about determining if the sum of any subset of these 4 integers is equal to 42? 9. What is the run-time complexity of your solution to problem 8? 10. Do you think you method is feasible if you are given a set of 100 integers?Explanation / Answer
6]
The algorithm written as a C/C++ code:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
int main()
{ int count = 0, n ;
clrscr();
cout << "Enter value of n";
cin >> n;
for (int i = 1; i<= n; i++)
for (int j = 1; j<=i; j++)
for (int k = 1; k<= j; k++)
printf(" Hello word, count = %d", ++count);
return 0;
} // end main
The above code produced a count of 9 when n = 3
Value of n
Value of count
Expressed as a function of n
Log n base 2
1
1
n
2
4
N^2
3
9
N^3
4
20
N*4+n
5
35
N*7
6
56
9*n+n/3
7
84
8
120
9
165
10
220
11
286
12
364
when n=5, count = 35
When n = 10, count = 220
The run time complexity will reach O(n^3) in worst case
In best case it can be O(n^2)
Average case it may run in O(n log n)
7]
Events: A die with siz sides from 1,2,... to 6
E1: The first die has an odd number {1,3,5}
E2: The second die has an odd number {1,3,5}
E3: The sum of the 2 values is odd = zero probability because the sum of two odd number is always an even number
a) E1 and E2 are independant
b) E2 and E3 are dependant because E3 may become odd only when E2 fails and becomes an even number
c) E1 and E3 are dependant because E3 may become odd only when E1 fails and becomes an even number
d) E1 and E2 and E3 are dependant because E3, the sum will be odd, only when one of E1 or E2 is even and other is odd
E3 = E1 + not E2
E3 = not E1 + E2
E3 will become true if E1 is true and E2 is false
or vice versa
that is
E2 will become true if E1 is false and E2 is true
E3 will be odd when E1 is odd and E2 is even
or
E3 will be odd when E1 is even and E2 is odd
8]
4 integers:
sum of any sub set of these 4 integers = 42
example:
set = 2, 10, 30, 5
sub set = 2+10+30 = 42
//given a set of 4 integers like set = { 2, 10, 30, 5}, the method to find whether the
//sum of any subset of these 4 integers = 42
// 2+10+30=42
/*
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
int main()
{
clrscr(); // Siva
int aray[4], i,j,k,l; // 4 variables for 4 subsets
int subSet1[1], subSet2[2], subSet3[3], subSet4[4]; // ok for small set of integers
for ( i=0; i<=3;i++) // 0 to 3 is 4
cin >> aray[i]; // fill up initial sample data set {2,10,30,5}
for ( i=0; i<=3;i++) // i loop
for (j=0; j<= i; j++) { // j loop
// populate each subset with all permutation and combination of data
// from the main set in aray[]
// and then check if any single subset addsup to 42
// this logic involves lots of for loops and if conditions
if ( subSet1[j] == 42 ) return TRUE; // compare
} // end for
return 0;
} // end main
*/
9]
Run time complexity: Best case: O(n^3)
Average case: Omega(n^3)
Worst case: Theta(n^n) = more than O(n^n)
10]
// this method is certainly not feasible for large set of integers like 100 integers.
// We need to use dynamic allocation mechanisms like linked lists, pointers etc to cater for larger sets of integers
// instead of creating 100 subSet array names like subSet1[1], subSet2[2], ... , subSet97[97], ..., subSet99[99]
// we can create the following structures and linked lists:
/*
struct tagSiva {
int dataSiva;
struct tagSiva *nextSiva;
} nodeSiva;
cin >> n; // the set of integers say n = 100
for (i = 0; i<=n; i++) {
// struct tagSiva subSet;
// subSet->dataSiva = 1;
// subSet->nextSiva = NULL;
// struct tagSiva temp;
// temp->dataSiva = 2;
// temp->nextSiva = subSet;
} // end for loop
*/
Value of n
Value of count
Expressed as a function of n
Log n base 2
1
1
n
2
4
N^2
3
9
N^3
4
20
N*4+n
5
35
N*7
6
56
9*n+n/3
7
84
8
120
9
165
10
220
11
286
12
364
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.