DEPARTMENT OF INFORMATION TECHNOLOGY
EE2204 DATA STRUCTURES AND ALGORITHMS
(Common to EEE, EIE & ICE)
1. LINEAR STRUCTURES 9
Abstract Data Types (ADT) – List ADT – array-based implementation – linked list implementation – cursor-based linked lists – doubly-linked lists – applications of lists – Stack ADT – Queue ADT – circular queue implementation – Applications of stacks and queues
2. TREE STRUCTURES 9
Need for non-linear structures – Tree ADT – tree traversals – left child right sibling data structures for general trees – Binary Tree ADT – expression trees – applications of trees – binary search tree ADT
3. BALANCED SEARCH TREES AND INDEXING 9
AVL trees – Binary Heaps – B-Tree – Hashing – Separate chaining – open addressing – Linear probing
4. GRAPHS 9
Definitions – Topological sort – breadth-first traversal - shortest-path algorithms – minimum spanning tree – Prim's and Kruskal's algorithms – Depth-first traversal – biconnectivity – Euler circuits – applications of graphs
5. ALGORITHM DESIGN AND ANALYSIS 9
Greedy algorithms – Divide and conquer – Dynamic programming – backtracking – branch and bound – Randomized algorithms – algorithm analysis – asymptotic notations – recurrences – NP-complete problems
L = 45 Total = 45
TEXT BOOKS
1. M. A. Weiss, “Data Structures and Algorithm Analysis in C”, Pearson Education Asia, 2002.
2. ISRD Group, “Data Structures using C”, Tata McGraw-Hill Publishing Company Ltd., 2006.
REFERENCES
1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, “Data Structures and Algorithms”, Pearson Education, 1983.
2. R. F. Gilberg, B. A. Forouzan, “Data Structures: A Pseudo code approach with C”, Second Edition, Thomson India Edition, 2005.
3. Sara Baase and A. Van Gelder, “Computer Algorithms”, Third Edition, Pearson Education, 2000.
4. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to algorithms", Second Edition, Prentice Hall of India Ltd, 2001.
UNIT-I LINEAR STRUCTURES
1. Define data structure.
The organization, representation and storage of data is called the data structure. Since all programs operate on data, a data structure plays an important role in deciding the final solution for the problem.
2. Define non-linear data structure.
Data structure which is capable of expressing more complex relationship than that of physical adjacency is called non-linear data structure.
3. What are the operations of ADT?
Union, Intersection, size, complement and find are the various operations of ADT.
4. What is meant by list ADT?
List ADT is a sequential storage structure. General list of the form a1,2,a3.…., an and the size of the list is 'n'. Any element in the list at the position I is defined to be ai, ai+1 the successor of ai and ai-1 is the predecessor of ai.
5. What are the different ways to implement list?
• Simple array implementation of list
• Linked list implementation of list
6. What is meant by a linked list?
Linear list is defined as, item in the list called a node and contains two fields, an information field and next address field. The information field holds the actual element on the list. the next address field contains the address of the next node in the list.
7. What are the advantages of a linked list?
· It is necessary to specify the number of elements in a linked list during its declaration.
· Linked list can grow and shrink in size depending upon the insertion and deletion that occurs in the list.
· Insertion and deletion at any place in a list can be handed easily and efficiently.
· A linked list does not waste any memory space.
8. What is a singly listed list?
The singly linked list , in which each node has a single link to its next node. This list is also referred as a linear linked list. The head pointer points to the first node in the list and the null pointer is stored in the link field of the last node in the list.
9. How is an element of a linked list called? What will it contain?
Linked list or list is an ordered collection of elements. Each element in the list is referred as a node. Each node contains two fields namely,
· Data field
· Link field
The data field contains actual data of the element to be stored in the list and the link field referred as the next address field contains the address of the next node in the list.
10. What is the use of header in a linked list?
A linked list contains a pointer, referred as the head pointer, which points to the first node in the list that stores the address of the first node of the list.
11. What are the disadvantages of a singly linked list?
In a singly linked list, you can traverse (move) in a singly linked list in only one direction (i.e. from head to null in a list). You can’t traverse the list in the reverse direction (i.e. ., from null to head in a list.)
12. What are the operations can we perform on a linked list?
The basic operations that can be performed on linked list are,
· Creation of a list.
· Insertion of a node.
· Modification of a node.
· Deletion of a node.
· Traversal of a node.
13. What are the applications of linked list?
Linked list form the basis of many data structures, so it’s worth looking at some applications that are implemented using the linked list. Some important application using linked list are
· Stacks
· Queues
14. What is a singly linked circular list?
The next field in the last node contains a pointer back to the front node rather than the null pointer such a list is called a circular list.
15. What is a double linked list?
Doubly linked list is an advanced form of a singly linked list, in which each node contains three fields namely,
· Previous address field.
· Data field.
· Next address field.
The previous address field of a node contains address of its previous node. The data field stores the information part of the node. The next address field contains the address of the next node in the list.
16. What are the basic operations in a circular doubly linked list?
The basis operations that can be performed on circular doubly linked lists are,
· Creation of a list.
· Insertion of a node.
· Modification of a node.
· Deletion of a node.
17. What is the advantage of doubly linked list?
For some applications, especially those where it is necessary to traverse list in both direction so, doubly linked list work much better than singly linked list. Doubly linked list is an advanced form of a singly linked list, in which each node contains three fields namely,
· Previous address field.
· Data field.
· Next address field.
18. Define Stack.
A stack is an ordered collection of elements in which insertions and deletions are restricted to one end. The end from which elements are added and/or removed is referred to as top of the stack.
19. Give some applications of stack.
Some important applications using stacks are
· Conversion of infix to postfix
· Expression evaluation
· Backtracking problem
· Towers of Hanoi.
20. What are the postfix and prefix forms of the expression?
A+B*(C-D)/(P-R)
Postfix form: ABCD-*PR-/+
Prefix form: +A/*B-CD-PR
21. Explain the usage of stack in recursive algorithm implementation?
In recursive algorithms, stack data structures is used to store the return address when a recursive call is encountered and also to store the values of all the parameters essential to the current state of the procedure.
22. Write down the operations that can be done with queue data structure?
Queue is a first - in -first out list. The operations that can be done with queue are addition and deletion.
23. What is a circular queue?
The queue, which wraps around upon reaching the end of the array is called as circular queue.
24. What does a Priority Queue mean?
Queue is a kind of data structure, which stores and retries the data as First In First Out. But priority queue disturbs the flow of FIFO and acts as per the priority of the job in the operating system.
Del-min (H)
Priority queue. H Insert(H)
25. State Tower of Honoi.
The objective is to transfer the entire disk to tower 1 to entire tower 3 using tower2. The rules to be followed in moving the disk from tower1 to tower 3 using tower 2 are as follows,
· Only one disc can be moved at a time
· Only the top disc on any tower can be moved to any other tower.
· A larger disc cannot be placed on a smaller disc.
26. Define Queue.
A Queue is an ordered collection of elements in which insertions are made at one end and deletions are made at the other end. The end at which insertions are made is referred to as the rear end, and the end from which deletions are made is referred to as the front end.
27. Give some applications of queue.
Queues have many applications in computer systems. Most computers have only a singly processor, so only one user may be served at a time. Entries from other users are placed in a queue. Each entry gradually advances to the front of the queue as users receive their service. Queues are also used to support print spooling.
28. What is abstract data type?(AU NOV 2011)
An Abstract data type (ADT) is a set of operations. Abstract data types are Mathematical abstractions. Example:Object such as set, list, and graphs along their operations can be viewed asADT. Union, intersection, size, complement and find are the various operations of ADT.
General list: A1, A2, A3,…………..An
· A1-> first element
· An-> last element
· In general Ai is an element in a list I
· Ai-> current element position
· Ai+1-> predecessor
29. List any applications of queue. (AU NOV 2011)
Batch processing in an operating system
* To implement Priority Queues.
* Priority Queues can be used to sort the elements using Heap Sort.
* Simulation.
* Mathematics user Queueing theory.
* Computer networks where the server takes the jobs of the client as per the queue strategy.
30. Define non linear data structure. (AU NOV 2011)
Data structure which is capable of expressing more complex relationship than that of physical adjacency is called non-linear data structure.
31. Mention the advantages of representing stacks using linked list than arrays.(AUT NOV 2011)
· It is necessary to specify the number of elements in a linked list during its declaration.
· Linked list can grow and shrink in size depending upon the insertion and deletion that occurs in the list.
· Insertion and deletion at any place in a list can be handed easily and efficiently.
· A linked list does not waste any memory space.
32. Mention the applications of list.(AUT NOV 2011)
1.Polynomial ADT
2. Radix Sort
3. Multilist
Part B:
1. Explain with example the insertion & deletion in doubly linked list
Doubly Linked List
A Doubly linked list is a linked list in which each node has three fields namely data field, forward link (FLINK) and Backward Link (BLINK). FLINK points to the successor node in the list whereas BLINK points to the predecessor node.
STRUCTURE DECLARATION : -
Struct Node
{
int Element;
Struct Node *FLINK;
Struct Node *BLINK
};
ROUTINE TO INSERT AN ELEMENT IN A DOUBLY LINKED LIST
void Insert (int X, list L, position P)
{
Struct Node * Newnode;
Newnode = malloc (size of (Struct Node));
If (Newnode ! = NULL)
{
Newnode ->Element = X;
Newnode ->Flink = P Flink;
P ->Flink ->Blink = Newnode;
P ->Flink = Newnode ;
Newnode ->Blink = P;
}
}
ROUTINE TO DELETE AN ELEMENT
void Delete (int X, List L)
{
position P;
P = Find (X, L);
If ( IsLast (P, L))
{
Temp = P;
P ->Blink ->Flink = NULL;
free (Temp);
}
else
{
Temp = P;
P ->Blink ->Flink = P->Flink;
P ->Flink ->Blink = P->Blink;
free (Temp);
}
}
Advantage
* Deletion operation is easier.
* Finding the predecessor & Successor of a node is easier.
Disadvantage
* More Memory Space is required since it has two pointers.
2. Explain with example the insertion & deletion in singly linked list
Singly Linked List Implementation
Linked list consists of series of nodes. Each node contains the element and a pointer to its successor node. The pointer of the last node points to NULL.
Insertion and deletion operations are easily performed using linked list.
A singly linked list is a linked list in which each node contains only one link field pointing to the next node in the list.
DECLARATION FOR LINKED LIST
Struct node ;
typedef struct Node *List ;
typedef struct Node *Position ;
int IsLast (List L) ;
int IsEmpty (List L) ;
position Find(int X, List L) ;