Answer Posted / tilak chandan

Lemma: A subtree rooted at node v has at least 2bh(v) − 1 internal nodes.
Proof of Lemma (by induction height):
Basis: h(v) = 0
If v has a height of zero then it must be null, therefore bh(v) = 0. So:
2bh(v) − 1 = 20 − 1 = 1 − 1 = 0
Inductive Step: v such that h(v) = k, has at least 2bh(v) − 1 internal nodes implies that v' such that h(v') = k+1 has at least 2bh(v') − 1 internal nodes.
Since v' has h(v') > 0 it is an internal node. As such it has two children each of which have a black-height of either bh(v') or bh(v')-1 (depending on whether the child is red or black, respectively). By the inductive hypothesis each child has at least 2bh(v') − 1 − 1 internal nodes, so v' has at least:
2bh(v') − 1 − 1 + 2bh(v') − 1 − 1 + 1 = 2bh(v') − 1
internal nodes.
Using this lemma we can now show that the height of the tree is logarithmic. Since at least half of the nodes on any path from the root to a leaf are black (property 4 of a red black tree), the black-height of the root is at least h(root)/2. By the lemma we get:

Therefore the height of the root is O(log(n)).

U hv to enter a range from a and b and search hw many no. of times a pattern n. occurs between the range a and b. Eg :i/p:enter range :0 100 Enter pattern: 13 o/p: the no. times 13 occurred betwwn 0 to 100:1 Eg :i/p:enter range :100 1000 Enter pattern: 13 o/p: the no. times 13 occurred betwwn 100 to 1000: (in this 13,113,131,132,133…139,213,313,…913 all these will be counted)

2225

---

find level of following tree (state, parent) " J,D I,D H,C E,B F,B G,C B,A D,A C,A A,& K,E L,E L,F M,F N,G O,H P,I P,H Q,I R,J S,K U,P T,L

2128

---

Question 1: Implement a base class Appointment and derived classes Onetime, Daily, Weekly, and Monthly. An appointment has a description (for example, “see the dentist”) and a date and time. Write a virtual function occurs_on(int year, int month, int day) that checks whether the appointment occurs on that date. For example, for a monthly appointment, you must check whether the day of the month matches. Then fill a vector of Appointment* with a mixture of appointments. Have the user enter a date and print out all appointments that happen on that date. *This Should Be Done IN C++

661

---

How to Split Strings with Regex in Managed C++ Applications?

3204

---

output for printf("printf");

2081

---

---

Performance Algorithm A performs 10n2 basic operations and algorithm B performs 300 lg n basic operations. For what value of n does algorithm B start to show its better performance?

7461

---

What output does this program generate as shown? Why? class A { A() { cout << "A::A()" << endl; } ~A() { cout << "A::~A()" << endl; throw "A::exception"; } }; class B { B() { cout << "B::B()" << endl; throw "B::exception"; } ~B() { cout << "B::~B()"; } }; int main(int, char**) { try { cout << "Entering try...catch block" << endl; A objectA; B objectB; cout << "Exiting try...catch block" << endl; } catch (char* ex) { cout << ex << endl; } return 0; }

676

---

Write a C++ program without using any loop (if, for, while etc) to print prime numbers from 1 to 100 and 100 to 1 (Do not use 200 print statements!!!)

3395

---

write a function that reverse the elements of an array in place.The function must accept only one pointer value and return void.

4108

---

write a program using virtual function to find the transposing of a square matrix?

2963

---

Teta-Omeg-Big-Oh Show that f(n) = n2 + 3n3 is ;(n3).

3278

---

how to take time as input in the format (12:02:13) from user so that controls remains between these columns?

1923

---

write a function that allocates memory for a single data type passed as a parameter.the function uses the new operator and return a pointer to the allocated memory.the function must catch and handle any exception during allocation

2499

---

write a program using 2 D that searches a number and display the number of items 12 inputs values input 15,20, 13, 30, 38, 40,16, 18, 20 ,18 ,20 enter no. to search : 20

3458

---

Implement a command console for changing settings on a particular object. The command console should allow you to enter a string and will return the response (very similar to a terminal session). The commands are as follows: SET propertyname=newvalue will change the target object’s member named “propertyname” to have a value equal to “newvalue”. If the input value is incompatible (i.e. an int being set to a string), print out an appropriate error message. GET propertyname will print out the current value of the target object’s member named “propertyname”. GET * will print out a list of all target object members and their current values. The system should be extensible for future commands and should accept an arbitrary object, such that another developer could insert another object into the system and rely on the command console to get and set the properties correctly.

3495

---