Graphs

9.1 Introduction

A graph G consists of a set V, whose members are called vertices of G, together with a set E of pairs of distinct vertices from V. These pairs are called the edges of G. If the pairs are unordered then G is called undirected Graph and if they are in order they are called Directed or digraphs.

9.2 Computer Representation of Graphs

1. The set representation
2. Adjacency Table or Adjacency Matrix
3. Adjacency List
a. Linked Implementation
b. Contiguous List
c. Mixed Implementation

9.3 Operations on Graphs
1. Breadth First Traversal
2. Depth First traversal

Experiment 27

Aim –Write a program to execute a Breadth First search on a Graph G beginning at A

Algorithm -

1. Initialize all node to ready state (Status = 1)
2. Put the starting node A in Queue and change its state to waiting (status = 2)
3. Repeat steps 4 and 5 until queue is empty
4. Remove the first node N of queue. Process N and change its status to processed state (status=3)
5. Add to the rear of queue all the neighbors of N that are in the ready state (status=1)
and change their status to waiting (status=2)
[End of Step 2 Loop]
6. Exit

Experiment 28


Aim –Write a program to execute a Depth First search on a Graph G beginning at A

Algorithm –

1. Initialize all nodes to ready state (Status = 1)
2. Push the starting node A in Queue and change its state to waiting (status = 2)
3. Repeat steps 4 and 5 until stack is empty
4. Pop the Top node N of stack . Process N and change its status to processed state (status=3)
5. Push onto stack all the neighbors that are in the ready state (status=1)
and change their status to waiting (status=2)
[End of Step 3 Loop]
6. Exit


9.4 Viva Voice

1. Define graph, directed and undirected graph?
2. Define the following:
a. Adjacent vertices
b. Path
c. Cycle
d. Connected graph
e. Degree
f. Complete graph
g. Weighted graph
3. How the graph is represented in computers memory?
4. What do you mean by graph traversal? What are different traversal methods of graph?
5. Minimum spanning tree are designed on directed or undirected graph?
6. What must a graph look like if a row of its matrix consists only of zeros?

Trees

8.1 Introduction-
A binary tree is either empty or it consists of a node called the root together with two binary trees called the Left subtree and the right subtree of the root.

8.2 Operations on Binary trees.
1. Insertion in Binary Tree
2. Deletion in Binary Tree
3. Traversal of Trees
a. Pre-order Traversal ( Root-Left-Right )
b. In-order Traversal ( Left-Root-Right )
c. Post-order Traversal ( Left-Right-Root )

Applications

1. Comparison Trees
2. Expression Trees


Experiment 24

Aim –Write a program to create a binary tree

Algorithm -

Let create_tree (info,node) be a procedure where info is the information for which we have to create node and node is a structure type variable with pointers to point to both left and right child.

1. [check whether the tree is empty]
If node = NULL
Node=create a node
Left[node]=NULL
Right[node]=NULL
2. [Test for the left child]
If info[node] >= info
Left[node]=Call create_tree(info,left[node])
else
Right[node]=Call create_tree(info,right[node])
3. return (Node)

8.3 Viva Voice

1. What is a Tree
2. Define the following terms
a. Degree
b. Depth
c. Path
d. Forest
3. Differentiate between Terminal nodes and non-terminal nodes
4. What is Binary tree.
5. Mention the properties of binary tree
6. What is Strictly & completely binary Tree
7. How binary tree is represented in computers memory?
8. What is thearded binary tree? It’s advantages and disadvantages
9. Draw the binary tree using the given traversals?
10. What is AVL tree?
11. Whait if forest?

Searching

7.1 Introduction
Searching is used to find the location where element is available or not. There are two types of searching techniques as given below :
1. Linear or sequential searching
2. Binary searching


Experiment 22

Aim –Write a program to search the given element using linear search.

Theory
In linear search, we access each element of an array one by one sequentially and see whether it is desired element or not. A search will be unsuccessful if all the elements are accessed and the desired element is not found. In the worst case the number of average case we may have to scan half of the size of the array. Therefore, linear search can be defined as a technique which traverses the array sequentially to locate the given item.
The time taken or the number of comparisons made in searching a record in search table determines the efficiency of the technique. If the desired record is present in the first position then only one comparison is made. If the desired record is last one then n comparisons have to made.


Algorithms
Let A is a linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in A, or sets LOC=0 if the search is unsuccessful.

1. [Initialize counter]
set LOC = 1
2. [Serach for item]
repeat while A[LOC] != ITEM
set LOC=LOC+1
3.[Successful]
if LOC = N+1, then
set LOC=0
4. Exit.



Experiment 23

Aim –Write a program to search the given element using binary search.

Theory- The search technique searches the given item in minimum possible comparisons. To do the Binary search, first the array is sorted. The logic behind the technique is
1. First find the middle element of the array.
2. Compare the mid element with the item
3. There are three cases:
a. If it is the desired element search is successful.
b. If it is less than desired item, then search the first half of the array
c. If it is greater than desired item, then search the second half of the array
Repeat the same steps until the search is exhausted.


Algorithms
Let A is sorted array with lower bound LB and upper bound UB, and ITEM is a given ITEM of information. The variables BEG, END and MID denoted, respectively, the beginning, end and middle location of a segment of element of A. This algorithm finds the location LOC of ITEM in A or sets LOC = NULL.

1. [Initialize segment variables]
Set BEG = LB ,END = UB and MID = int (( BEG + End)) / 2
2. Repeat steps 3 and 4 while BEG <= END and A[MID] != ITEM
3. if ITEM < A [MID] , then
Set END = MID – 1
Else
Set BEG = MID +1
[end of if structure]
4. set mid = int ((BEG + END))/2
[End of step 2 loop]
5. if A[MID] = ITEM then
set LOC = MID
else
set LOC = NULL
[end of if structure]
6.exit


7.2 Viva voice

1.What is sorting? List different types of sorting techniques.
2. What are the factors to be considered during the selection of sorting technique.
3.Which of the following sorts will take longest time to execute and which will take the shortest time?
a) Merge sort
b) Heap sort
c) Selection sort
d) Shell sort
e) Quick sort
f) Insertion sort

4. How many comparisons are required to sort an array of 10 elements using selection sort , if the original array values already sorted?
5. What do you mean by efficiency of the algorithm?
6. What is the best case , average case and worst case complexity of following:
a) merge sort
b) heap sort
c) selection sort
d) shell sort
e) quick sort
f) insertion sort
7.What are the factors on which complexity of algorithm depends? Which factor is taken into consideration while determining the complexity of algorithm for searching and sorting?
8.Suppose name consist of following list of names with n= 5
Amit, jaswinder , chander, gagan, seema
Find the number of comparisons to sort name using radix sort.
9.What is searching?
10.Distinguish between the following
a) Internal search and external search
b) Primary key and secondary key
c) Internal key and external key
10. Which is efficient search technique?
11. What is hashing? What is the need for a hashing?
12. What is the need for an ordered table searching?
13. What are the techniques to resolve hash clashes?

Sorting

6.1 Introduction
Sorting of an array is the technique of arranging the array elements in a specified order i.e either in ascending or descending order. Sorting is one of the operation which make the job of retrieval of data from the storage devices, easier, speedier and efficient.

There are several sorting techniques available. They are :

1. Bubble sort
2. Selection sort
3. Shell sort
4. Heap sort
5. Insertion sort
6. Quick sort
7. Merge sort


6.2 Efficiency of Sorting Algorithms


Performance analysis & measurement
The time and space the algorithm uses are the two major measures of the efficiency of the algorithm. The complexity of the algorithm is the function which gives the running time and/or space in terms of the input size.
Space complexity
The space complexity of a program is the amount of memory it needed to fun to completion.
Time Complexity:
It is the amount of computer time needs to run to completion.

Big OH Notation
Big OH is a characterization scheme that allows to measure properties of algorithm complexity performance and/or memory requirements in a general fashion.

LINKED LIST

5.1 INTRODUCTION
Linked lists are special list of some data element pointing to one another.The logical ordering is represented by having each element pointing to the next element.Each element is called a node, which has two parts.INFO part which stores the information and POINTER which points to the next element.

5.2 OPERATIONS ON LINKED LIST
The basic operation to be performed on linked list are as follows :
1. Creation 2. Insertion
3. Deletion 4. Traversing
5. searching 6.Concatenation
7.Display

5.3 TYPES OF LINKED LIST
1. Singly linked list 2. Doubly linked list
3. Circular linked list 4. Circular Doubly linked list

SINGLY LINKED LIST
singly linked list are known as one way list. In this one pointer is maintained , which points to the next node called the NEXT pointer. One can traverse the list in forward direction.

DOUBLY LINKED LIST
Doubly linked list are known as two way list. In this two pointers are maintained :One which points to the next node called the NEXT pointer and other which points to previous node called the PREV pointer. One can traverse the list both in forward as well as backward direction.

CIRCULAR LINKED LIST
A Circular Linked List is one which has no beginning and no end. In this two pointers are maintained: One which points to the next node called the NEXT pointer and other which points to previous node called the PREV pointer. One can traverse the list both in forward as well as backward direction. It is very similar to doubly linked list except that in doubly linked list the prev pointer of the first node and the next pointer of the last node points to NULL where as in circular linked list the last node contains the address of the first node and the last node contains the address of the first node. All operation are similar to doubly linked list

Queues

4.1 INTRODUCTION

A queue is a non-primitive linear data structure .It is an homogeneous collection of elements in which new elements are added at one end called the Rear end , and the existing elements are deleted from other end called the Front end.

4.2 OPERATION ON QUEUES

The basic operations that can be performed on queue are:
To insert an element in the queue.
To delete an element from the queue.

4.3 DEQUEUES

It is homogeneous list of elements in which insertion and deletion operations are performed from both the ends.

4.4 Operations on Dequeue

1. Insertion of an element at the REAR end of the queue.
2. Deletion of an element from the FRONT end of the queue.
3. Insertion of an element at the FRONT end of the queue.
4. Deletion of an element from the REAR end of the queue

For an input-restricted deque only the operations specified in 1, 2, 3 and 4 are valid. And for out- restricted deque only the operations specified in 1, 2, 3 are valid.


4.5Application of arrays

1. Round robin technique for processor scheduling is implemented using queues.
2. All types of customer service (like railway ticket reservation) center software’s are designed using queues to store customers information.
3. Printer server routines are designed using queues.


Experiment 7

Aim- Write a program to perform add and delete operations in the linear queue

Algorithm (Insertion)
Let QUEUE be the array of some specified size say MAXSIZE, then the insertion algorithm will be as given below.While implementing a queue using arrays we must check underflow and overflow conditions for queue.

1. Initialize Front =0 and Rear = -1
2. If Rear b>= MAXSIZE [Check overflow condition]
Write Queue Overflow and return
Else
Set Rear = Rear + 1
3. QUEUE[Rear] = Item
4. If Front = -1 [Set the front pointer]
5. Return.

Algorithm (Deletion)

1. [Check underflow condition]
If Front < 0
Print : Queue is Empty and return
Else :
Item = QUEUE[Front] [Remove Element from front]
3. [Find new value of front.]
If (Front= = Rear) [Checking for empty queue]
Set front=0 , Rear = -1 [Re- initialize the pointers]
Else:
Front = Front +1
4. Return

4.7VIVA VOICE

1.What is a queue?
2.What does ‘front’ and ‘rear’ of the queue?
3. What is the full form of DEQUEUE?
4. How is queue different from stack?
5. Distinguish between LIFO and FIFO.
6. What is full queue and empty queue condition
7. What is circular queue and how do you represent it?
8. What is Dequeue?
9. What is meant by priority queues?

Stacks

3.1 Introduction

A Stack is a non-primitive linear data Structure. It is a ordered list in which addition and deletion of data items is done only from one end, known as top of stack (TOS). As all the deletions and insertions in a stack is done from the top of the stack the last added element will be the first to be removed from the stack that is the reason why stack is called Last in first out (LIFO) type of list.

3.2 Stack Implementation
Stack can be implemented in two ways:
(i) Static implementation: - It uses array to create stack.
(ii) Dynamic implementation: - Also called linked list representation and uses pointers to implement the stack type of data structure.

3.3 Operations on Stack
(i) PUSH
(ii) POP
(iii) PEEP

3.4 Applications of Stacks

1. Evaluation of Postfix Expression
2. Conversion of infix to Postfix
3. Conversion of infix to Prefix
4. Validity of an Expression

Experiment 1

Aim – Write a program to perform push and pop operations on stack.
Theory- The process of adding a new element to the top of stack is called PUSH operation and after every push operation the top of the stack is incremented by one. In case the array is full and no new element can be accommodated, it is called overflow condition.

The process of deleting an element from the top of the stack is called POP operation and after every pop operation the top of the stack is decremented by one.In case the array is empty , the condition is called underflow condition.
The process of accessing the elements is PEEP operation.

Algorithm- (PUSH)
Let stack [Maxsize] is an array for implementing the stack.

1. [Check for stack overflow]
If Top = Maxsize – 1, then : print : overflow and exit
2. [increment Top by one
Set Top = Top + 1
3. [Insert item in the new Top position]
Set stack[Top] = item
4. Exit

Algorithm- (POP)

Let stack[Maxsize] is an array for implementing the stack and assign to variable item.
2. [Check for stack underflow]
If Top < 0 then :
Print : “Stack overflow” and Exit
Else [Remove the top element]
Set Item = Stack[Top]
3. [decrement the Stack top]
Set Top = Top – 1
4. [Return the Deleted Item from the stack]
5. Exit

Arrays

2.1 Introduction

An array is defined as a set of finite number of homogeneous elements or data items. Some common operations performed on arrays are:
1. Creation of an array
2. Traversing an array (accessing array elements)
3. Insertion of new elements.
4. Deletion of required element.
5. Modification of an element
6. Merging of arrays.
7. Searching an element.
8. Sorting the elements.


2.2 Limitation of arrays
1.The prior knowledge of number of elements in the array is necessary.
2. These are static structures.
3. Since the elements of these arrays are stored in these arrays are time consuming. This is because of moving down or up to create a new space of a new element or to occupy the space vacated by the deleted item.



Experiment 1

Aim – Write a program to insert, delete and traverse an array

Theory –
Inserting an element at the end of array can be easily done, provided the memory space allocated for array is large enough to accommodate the additional element. For inserting the element at required position , elements must be moved downwards or rightwards to create space for the element to be inserted.

Deleting an element at the end of array presents no difficulties, but deleting element somewhere in the middle of the array would require to shift all the elements to fill the space emptied by the deletion of the element, then element following it are moved upward or left by one location.

Traversing means to access all the elements of array, starting from first element (Lower bound) upto the last element (Upper bound ) in the array one-by-one.


Algorithm (Insertion)

Assume len to be the length of the array A, NE be the total no. of elements, pos denotes index no. or position, num to be the element to be inserted.

1. [Initialize the value of I ]
Set I = NE
2. Repeat for I=NE to pos
[Shift the elements down by one element]
Set a[I+1]=a[I]
[end of Loop]
3. [Insert the element at required position]
Set A[pos]=num
4. [Reset len]
Set NE=len+1
5. display yhe new list of arrays
6. End




Algorithm (Deletion)
Assume len to be the length of the array A, NE be the total no. of elements, pos denotes index no. or position, num to be the element to be deleted.

1. Set item=A[pos]
2. Repeat for j = pos to NE-1
[Shifting elements 1 position upwards or left]
Set A[j] = A[j+1]
[End of loop]
3. Reset NE = NE -1
4. Display the new list of arrays
5. End


Algorithm (Traversal)
Let LB be the lower bound and UB be the upper bound of linear array A.

1. [Initialize counter.]
Set I at lower bound LB
2. Repeat for I=LB to UP
[visit element]
Display A[I]
[End of the loop]
3. Exit.


2.2 Viva Questions

1. What is meant by static implementation of the array
2. What is meant by dynamic implementation of the array
3. Name some Data structures, which can be implemented with the help of arrays.
4. Does deletion operation in static implementation, actually deletes the array element or it overwrites it.
5. What are the limitations of the array.

Data Structures

1 What is Data Structure
Data Structure is a representation of logical relationship existing between individual elements of data. In other words, a data structure is a way of organizing all data items that considers not only the elements stored but also their relationship to each other.
It is a mathematical or logical model for particular organization of data items.
It mainly specifies the following things:-
1. Organization of data
2. Accessing methods
3. Processing alternatives for information

1.1 Classification of Data Structures
Data structures are normally divided into two categories: -
1. Primitive Data Structure:- These are basic structures and are directly operated upon by the machine instructions.
2. Non-primitive Data structure:- These are derived from primitive data structures. It emphasize on structuring of a group of homogeneous or heterogeneous data items.

1.2 Operations on Data structure
The design of an efficient data structure must take operations to be performed on the data structure into account. The data structure is to be manipulated in a number of major program functions. After evaluating the operations to be performed on the data structure, an abstract data type is defined to use it in subsequent programs.
The most commonly used operations on data structure are :
1. Creation
2. Insertion
3. Deletion
4. Selection
5. Updation
6. Searching
7. Sorting
8. Merging

1.3 Algorithms
An algorithm is any well- formed –defined computational procedure that takes some value or set of values as input and procedure some values or set of values as output.

1.4 Analyzing algorithms
Analyzing an algorithm measuring computational time and memory space required during execution.

1.5 Performance analysis & measurement

1.5.1 Space complexity
The space complexity of a program is the amount of memory it needed to fun to completion.
1.5.2 Time Complexity:
It is the amount of computer time needs to run to completion.

1.6 Big OH Notation
Big OH is a characterization scheme that allows to measure properties of algorithm complexity performance and/or memory requirements in a general fashion.

1.7 Categories of Algorithms
Based on Big OH notation the algorithms can be categorized as follows:
• Constant time (O(1)) algorithm.
• Logarithmic time (O(log n)) algorithms.
• Linear time (O(n)) algorithms.
• Polynomial time (O(n**k),for k >1) algorithms
• Exponential time (O(k**n), for k >1) algorithms.
• Many algorithms are O(n log n).

How to Face Interview

1. Plan to arrive 10 minutes early. This will give you ample time to catch your breath, gather your thoughts and make a quick trip to the washroom to give your appearance one final check. To avoid unnecessary stress, choose your interview attire the night before.

2. Greet the interviewer by his or her last name. If you are unsure of the pronunciation, do ask the employer to repeat it. Or better still, check it with the front desk personnel or receptionist before walking into the interview room.

3. Let the interviewer lead the conversation but try to get him/her to describe the position and duties to you early in the interview. This will allow you to apply your background, skills and achievements to the position.

4. When asked: "Tell me about yourself?", focus your answers on your background and a few professional and personal accomplishments.

5. Stress on your achievements. For example: your sales records, the processes you have developed or systems installed, projects that you initiated, etc.

6. Show enthusiasm. This can be demonstrated through verbal and non-verbal cues (for example, appropriate body language like nodding can be used to support your interest). Enthusiastic feedback can enhance your chances of being further considered.

7. Answer questions by speaking in terms of the position. Emphasise what you can do for the company. Mention specific accomplishments that show your abilities and determination to succeed in this job. Your answers describe the position and duties to you early in the interview. This will allow you to apply your background, skills and achievements to the position. should tell the employer why you would be an asset to the company and not why you need a job.

8. Bring an extra copy of your resume.

9. Explain whenever possible; don't answer with a simple "yes" or "no."










Be prepared to answer questions such as:

* Tell me about yourself.
* Tell me about your background and accomplishments.
* What are your strengths? Weaknesses?
* How would you describe your most recent job performance?
* What interests you about our company?

Also, be prepared to ask questions such as:

* What would I be expected to accomplish in this position?
* What are the greatest challenges in this position?
* How do you think I fit the position?

Remember, your lack of questions may be mistaken as lack of interest in the job.

Summary

If you are interested in the position, stress this to the interviewer. If you get the impression that the interview is not going well and that you have already been rejected, do not let your discouragement show. Once in a while an interviewer who is genuinely interested in you may seem to discourage you as a way of testing your reaction. Remember to thank the interviewer for his/her time and end the session with a confident and firm handshake.