 8 May 2017 - 6:03pm

Where? As I understood. 76 is correct answer.

more less
8 May 2017 - 5:15pm

(a) x1 ≥ 1, so equation will be x1 + x2 + x3 + x4 + x5 = (21 - 1) = 20.

So, total number of solutions = C((20+5-1), 20) = C(24, 20) = C(24, 4) = 10626.

(b)

xi ≥ 1, so equation will be x1 + x2 + x3 + x4 + x5 = (21 - 2 - 2 - 2 - 2 - 2) = 11.

So, total number of solutions = C((11+5-1), 20) = C(15, 11) = C(15, 4) = 1365.

(c) 0 ≤ x1 ≤ 10 . In other words, if we x1 ≥ 11 from total number of solution, then we get number of solutions between 0 ≤ x1 ≤ 10.
Possible solutions = C((21+5-1), 21) - C(((21-11)-5-1), (21-11)) = C(25, 21) - C(14, 10) = C(25, 4) - C(14, 4) = 12650 − 1001 = 11649.

(d) First, satisfy x3 ≥ 15, and x2 ≥ 1 then equation will be

x1 + x2 + x3 + x4 + x5 = (21 - 15 - 1) = 5.
So, total number of solutions = C((5+5-1), 5) = C(9, 5) = 126

Case 1: Now satisfy x2 ≤ 2, (since 2 and 3. 1 is already satisfied). Then situation will be same as part (c), and we subtract x2 > 3 solutions from total number of solution as given in above equation:
Total number of solutions = 126 - C(((5-2)+5-1), 5-1) = 126 - C(7, 4) = 126 - 35 = 91.

Case 2: Now satisfy x1 ≤ 3. Then situation will be same as part (c), and we subtract x1 > 4 solutions from total number of solution as given in case 1.

So, number of solutions = 91 - C(((5-3)+5-1), 5-1) = 91 - C(6, 4) = 91 - 15 = 76.

more less
8 May 2017 - 4:07pm

Note:
1. You have given n elements from 1 to n.
2. In BST(binary search tree), inorder traversal is always sorted ordered.

Algorithm to build binary tree from inorder and postorder traversal:

1. Take the last element from postorder as root element of binary tree. This takes O(1) time.
2. Perform binary search on given sequence 1 to n to find that element in inorder traversal. This takes O(log n) time.
3. Now divide inorder traversal using that element using pivot selection.
4. Repeat for both split part. This takes T(k) and T(n-k-1) time.

The recurrence relation would be T(n) = T(k) + T(n-k-1) + O(log n) = O(n log n). This is time complexity to build binary tree using inorder and postorder/preorder traversal.

As you have given that tree is binary search tree, so there is no need to perfrom binary search. Simply, we take pivot and split given list from 1 to n element. The recurrence relation would be T(n) = T(k) + T(n-k-1) + O(1) = O(n). This is time complexity to build binary search tree using inorder and postorder/preorder travarsal.

more less
8 May 2017 - 2:27am

There is nothing wrong with given code. If you compile and run this code you will get some output.

The problem is only that you have allocated memory(using malloc), but you have forgotten to deallocate it. This situation is known as memory leak problem. That should be deallocated after using memory block at run time.

int *x = malloc(sizeof(int));


See reference: http://c-faq.com/malloc/mallocnocast.html

Dangling pointer situation occurs when a pointer is pointing a memory location that has been deleted (using free). However, there is no free in given code.
See difference: http://stackoverflow.com/questions/13132798/difference-between-dangling-...
Therefore, option (d) is correct.

more less