4 Comments

1. 

   cs301 on February 7, 2019 at 10:55 am

   Nice Website and very good content

2. 

   Ayesha Mumtaz on February 7, 2019 at 11:06 am

   SUBJECTIVE QUESTIONS
   Question No:1
   Name of two divide and conquer algorithm (2 marks)
   Answer:- (Page 488)
    Merge Sort
    Quick Sort
    Heap Sort
   These three algorithms fall under ‗divide and conquer category‘
   Question No:2
   Difference between call by value n call by reference (2 marks)
   Answer:- (Page 202)
   In case of call by value, a copy of object is made and placed at the time of function calling in the activation record. By using the references, we are not making the copy but send the address of the variable that function can use the original value.
   Question No:3
   Heap and two types of heap(3)
   Answer:- (Page 333 )
   Heap is a data structure of big use and benefit. It is used in priority queue. ―The definition of heap is that it is a complete binary tree that conforms to the heap order‖. Here heap order means the min and max heap. Max heap: In max heap, each node has a value greater than the value of its left and right child nodes. Moreover, the value of the root will be largest and will become lesser at downward levels. Min heap: in a (min) heap for every node X, the key in the parent is smaller than (or equal to) the key in X. This means that the value in the parent node is less than the value on its children nodes.
   Question No: 4
   Here is an array with exactly 15 elements:
   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.
   Suppose that we are doing a binary search for an element. Indicate any elements that will be found by
   examining two or fewer numbers from the array. (Marks: 5)
   Answer: 
   If there is an array of 15 elements, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
   it wants to know which elements can be discovered by examining two or fewer elements. I want assume the divide and conquer aspect of a binary search, so that leads me to think these elements will be found
   1, 2, 14, 15, 7, 3
   rather; 1, 2, 3, 4, 6, 8, 14, 15
   1 and 15 for heads and tails
   2, and 14 for next elements (following or preceding)
   1/2 of 15 is either 6, or 8, from 7.5
   and 1/2 of 6 = 3
   1/2 8 = 4
   Question No: 4
   Write one example of hashing?
   Answer: (page 459)
   Hashing can be used to store the data. Suppose we have a list of fruits. The names of Fruits are in string. The
   key is the name of the fruit. We will pass it to the hash Function to get the hash key.
   HashCode (“apple”) = 5
   We pass it to the string ―apple‖. Resultantly, it returns a number 5.
   Question No: 5
   How do we carry out degeneration of Complete Binary Tree?
   Answer:
   Degeneration of the (original) binary tree is mainly reflected by degeneration of the internal infix trees and less by degeneration of the external height of the PPbin tree.
   Question No: 6
   How we can generate a maze with the help of union?
   Answer: (page 424)
   How can we generate maze? The algorithm is as follows:
    Randomly remove walls until the entrance and exit cells are in the same set.
    Removal of the wall is the same as doing a union operation.
    Do not remove a randomly chosen wall if the cells it separates are already I the same set.
   Question No: 7
   Write down the C++ code to implement insertion sort algorithm. ?
   Answer: (page 483)
   Following is the code of the insertion sort in C++.
   void insertionSort(int *arr, int N)
   {
   int pos, count, val;
   for(count=1; count = 0; pos–)
   if (arr[pos] > val)
   arr[pos+1]=arr[pos];
   else break;
   arr[pos+1] = val;}
   }
   Question No: 8
   What is Table ADT? Discuss any two implementations of table ADT. ?
   Answer: (page 427,428)
   The table, an abstract data type, is a collection of rows and columns of information.
   Implementation of Table
   o Unsorted Sequential Array
   o Sorted Sequential Array
   Question No: 9
   What is an Equivalent relation? Give any two examples. ?
   Answer: (page 387)
   A binary relation R over a set S is called an equivalence relation if it has following properties‘:
   1. Reflexivity: for all element x ȟ S, x R x
   2. Symmetry: for all elements x and y, x R y if and only if y R x
   3. Transitivity: for all elements x, y and z, if x R y and y R z then x R z
   Example; sets of peoples ,electric circuit domain.
   Question No: 10
   How heap sort works to set a set of data ?
   Answer: (page 334)
   Min heap and max heap are used to sort the data. Min heap convert the data in ascending sorted order and max heap convert the in descending order.
   Question No 11: How can we search an element in skip list? 2Marks
   Answer:- (Page 447)
   We search for a key x in the following fashion:
   We start at the first position of the top list
   • At the current position p, we compare x with y �key(after(p))
   • x = y: we return element(after(p))
   • x > y: we ―scan forward‖
   • x object = object; }; // set the value of the element
   Node* getNext() { return nextNode; }; // get the address of the next node
   void setNext(Node* nextNode) // set the address of the next node
   { this->nextNode = nextNode; };
   Node* getPrev() { return prevNode; }; // get the address of the prev node
   void setPrev(Node* prevNode) // set the address of the prev node
   { this->prevNode = prevNode; };
   private:
   int object; // it stores the actual value of the element
   Node* nextNode; // this points to the next node
   Node* prevNode; // this points to the previous node
   };
   Question No 27: What you conclude from the running time analysis of disjoint sets.
   Answer (page 405)
   We conclude that:
    union is clearly a constant time operation
    Running time of find(i) is proportional to the height of the tree containing node i.
    This can be proportional to n in the worst case (but not always).
    Goal: Modify union to ensure that heights stay small.
   Question No 28:what is c++ template.
   Answer:- (page 75)
   A template is a function or class that is written with a generic data type. when a programmer uses this function or class the generic data type is replaced with the data type needed to be used in the template function or in the template class. We only give the data type of our choice while calling a template function or creating an object of the template class. The compiler automatically creates a version of that function or class with that specified data type.
   Question No:29
   which three basic operations are performed on AVL trees (mark 3)
   Answer:- (page 457)
    Insert
    Delete
    search
   Question No: 30
   Write the applications of heap.
   Answer:- (page 84)
   The stack and heap are used in function calls. When we allocate memory dynamically in our programs, it is allocated from the heap. The use of priority queue with the help of heap is a major application. The priority queue is itself a major data structure, much-used in operating systems. Similarly priority queue data structure is used in network devices especially in routers. Heap data structure is also employed in sorting algorithms.
   Question No: 31 Which is Dynamic Equivalence Problem with an example? (5)
   Answer: – (page 395)
   We are using sets to store the elements. For this purpose, it is essential to remember which element belongs to which set. We know that the elements in a set are unique and a tree is used to represent a set. Each element in a tree has the same root, so the root can be used to name the set. The item (number) in the root will be unique as the set has unique values of items. We use this root as the name of set for our convenience. Otherwise, we can use any name of our choice. So the element in the root (the number) is used the name the set.
   The find operation will return this name. Due to the presence of many sets, there will be a collection of trees. In this collection, each tree will be representing one set. If there are ten elements, we will have ten sets initially. Thus there will be ten trees at the beginning. In general, we have N elements and initially there will be N trees. Each tree will have one element. Thus there will be N trees of one node. Now here comes a definition for this collection of trees, which states that a collection of trees is called a forest.
   The trees used for the sets are not necessarily binary trees. That means it is necessary that each node should have a maximum of two children nodes. Here a n may have more than two children nodes. To execute the union operation in two sets, we merge the two trees of these sets in such a manner that the root of one tree points to the root of other. So there will be one root, resulting in the merger of the
   trees. In the find operation, when we call find (x), it helps us to know which set this x belongs to. Internally, we find this x in a tree in the forest. When this x is found in a tree the find returns the number at root node (the name of the set) of that tree.
   Question No 32: “is a sibling of” set of all human beings is equivalence relation or not? Explain.
   Answer: (Page 387)
   Yes it is an equivalence relation
   First rule is reflexive i.e. for all element x �S, x R x. Suppose that x is Haris so Haris R Haris. This is true because everyone is related to each other. Second is Symmetry: for all elements x and y, x R y if and only if y R x. Suppose that y is Saad. According to the rule, Haris R Saad if and only if Saad R Haris. If two persons are related, the relationship is symmetric i.e. if I am cousin of someone so is he. Therefore if Haris is brother of Saad, then Saad is certainly the brother of Haris. The family relationship is symmetric. This is not the symmetric in terms of respect but in terms of relationship. The transitivity is: ‗for all elements x, y and z. If x R y and y R z, then x R z‘. Suppose x is Haris, y is Saad and z is Ahmed. If Haris ―is related to‖ Saad, Saad ―is related to‖ Ahmed. We can deduce that Haris
   ―is related to‖ Ahmed. This is also true in relationships. If you are cousin of someone, the cousin of that person is also related to you. He may not be your first cousin but is related to you.
   Question No 33: Linked memory
   (Answer: Page 18)
   Linked memory is a memory in which the various cells of memory are not located continuously. In this process, each cell of the memory not only contains the value of the element but also the information where the next element of the list is residing in the memory. It is not necessary that the next element is at the next location in the memory. It may be anywhere in the memory. We have to keep a track of it.
   Thus, in this way, the first element must explicitly have the information about the location of the second element.

3. 

   KHalid Hassan on February 18, 2019 at 9:15 am

   kia ye question past papers me se liye gye hen ???

   • 

     VU Assassins on February 18, 2019 at 3:13 pm

     g kuch 2,4