Dont comment if you have no solution What is the big O notation\'s primary purpo

Question

Dont comment if you have no solution

What is the big O notation's primary purpose? In the big O notation functions, describe the growth rate of the function g(n) = nlog2n Explain how having multiple constructors for a class is beneficial. What is the Big O of the following bit of code: The categories of classes , private, public and protected are called reference parameter (T/F). In the big O notation functions, describe the growth rate of the function g(n) = nlog2n It is good practice to initialize private member variables in the function definition of the function they are being used? (T/F). What is the output of the following code? Explain each step! Briefly describe containers, iterators, and algorithms in the context of the STL Write code allocating a dynamic 2D array. Write code to delete your dynamic 2D array. In any program concerning a deck of playing card, it is important to output to the user what the card's rank and suit are. What operator would you overload to accomplish this, and in a short pseudocode, describe what the overloaded operator would do.

Explanation / Answer

1. to give the worst time analysis so that the programmer could have an estimate how long will it take the processor to compute large inputs and how program behaves with large inputs

2.ogab means "what power do I have to raise a to in order to get b?" So, one example of where this would come up would be a question like "If I have a balanced binary tree with n nodes, then how deep is it?" Well, each level has twice as many nodes as the previous level. So, the first level has 1 (2^1 - 1). The second level has 1+2 = 3 (2^2 - 1). The third level has 1+2+4 = 7 (2^3 - 1). The fourth has 1+2+4+8 = 15 (2^4 - 1). So, ignoring the -1 part, we can then just ask 2^what = n? The other way to write this is log2n. So the depth of the tree is log2n. So if we're finding a node in a balance binary search tree, then we must traverse at most a number of nodes equal to the depth. Hence this is O(log2n).

Likewise we can say ask something like "If I have n items and each time through the loop I can throw out half of them, how many times do I have to go through the loop until there's only one remaining?" This is the analysis for binary sort. If I've gone through the loop k times, then I have 1/2^k items remaining. So I want to find k such that n/2^k = 1. This is the same as n=2^k or k = log2n.

With merge sort each time we go through a combination step, we're going to touch every item, but how many combination steps do we need? Well, if we have n items, we start with n lists of 1 item. For the second step, we'll combine those in pairs and have n/2 lists with 2 items each. For the third step, we'll combine those in pairs and have n/4 lists with 4 items each, and so forth. So we'll have n/2^k lists after each step. So how many steps do we need until we have 1 list left? n/2^k = 1. n=2^k. k=log2n. Then the total timing analysis is to multiply the number of steps by the time for each step. O(n*log2n).

Note that by the properties of logarithms, logab = lognb/logna. So we can convert logs of any base using only a constant factor, and thus anything which is O(log2n) is also O(log10n) and O(log173n), so we often leave off the subscript inside of the big/litte-O/Theta/Omega notation.

3.It benefits since class dont have to form its own default constructor and it allows the user to initialize the data members of class in various formats.

4. n^2

5.false

6.already explained.see 2

7.false

8. p is an array of 10 integers.

we are assigning p[0]=4

now coming in loop,

{

x= *p which means x=4 for the first time

next statement is p++ which moves the pointer to point to p[1]

now *p= x+j i.e 4+(the value of j) i.e 4+0=4 when j=0

}

since there is no output statement basically it should give no output..but assuming there is an output statement, the output will be,

4,4,5,7,10,14,19,25,32,40,49

9.

A container is an object that represents a group of elements of a certain type, stored in a way that depends on the type of container (i.e., array, linked list, etc.). An iterator is a pointer-like object (that is, an object that supports pointer operations) that is able to "point" to a specific element in the container.

The interesting (and brilliant!) detail about the STL containers, is that the STL introduces the idea of a generic type of container, for which the operations and element manipulations are identical regardless the type of container that you are using (for example, you would (or could) code exactly the same algorithm to find the highest element in an array as you would to find the highest element in a linked list. This sounds like easy to say, but not-so-easy to implement.

The STL takes advantage of the operator overloading feature of the C++ language to provide class definitions for the iterators to represent pointer-like objects. In general, the basic operations required for pointers are: assigning a value (to make it point to a specific data item), dereferencing it (to access the data element - in read or write mode), pointer arithmetic (in particular, incrementing or decrementing the pointer with the ++ or -- unary operators), and comparison of the values. (in particular, for equality or inequality)

If we are given class definitions that provide the assignment operator, comparison operators, the unary * operator and the (also unary) ++ and -- operators, we can indeed write code that use these types of objects as if they were pointers (provided that each operator's definition perform an operation that corresponds to its intuitive equivalent for pointers).

At this point, you have seen the basic idea of the Standard Template Library. Now let's see the specifics, and a few examples:

First of all, containers are implemented via template class definitions. This allows us to define a group of elements of the required type. For example, if we need an array in which the elements are simply integers (as in the example above), we would declare it as:

vector<int> values;

(yes, the name of the container to represent arrays is vector - it follows the mathematical idea that a vector is a group of values in a multi-dimensional space)

The iterator is container-specific. That is, the iterator's operations depend on what type of container we are using. For that reason, the iterator class definition is inside the container class; this has a good side effect, which is that the syntax to declare an iterator suggests that the definition type belongs in the context of the container definition. Thus, we would declare an iterator for the values object as follows:

vector<int>::iterator current;

With this, we are almost ready to translate the example shown above to find the highest value in an array, using the STL tools. I will first present the implementation, and then explain the details:

vector<int>::iterator current = values.begin();

int high = *current++;

while (current != values.end())

{

if (*current > high)

{

high = *current;

}

current++;

}

10.

// contains code for creating and deleting 2d array

#include <stdlib.h>

#include <stdio.h>

extern int **alloc_array(int rows, int columns);

int **alloc_array(int rows, int columns)

{

int i;

int j;

int **twoDary = (int**) (malloc(rows * sizeof(int *)));

int **twoDaryStart = twoDary;

int *currentrow;

for ( i = 0; i < rows; i++ ){

*(twoDary + i) = (malloc(columns * sizeof(int)));

}

for (j = 0; j < rows; j++) {

currentrow = *(twoDary + j);

for ( i = 0; i < columns; i++ ) {

*(currentrow + i) = i;

printf("%d ", *(currentrow+i));

}

}

return twoDary;

}

int main(void)

{

int **d2 = alloc_array(5, 10);

for (int i = 0; i < 5; i++)

free(d2[i]);

free(d2);

return(0);

}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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