jelanmathewjames / ktu_s3_ds_cst201 Goto Github PK

Basic Concepts of Data Structures System Life Cycle, Algorithms, Performance Analysis, Space Complexity, Time Complexity, Asymptotic Notation, Complexity Calculation of Simple Algorithms

Arrays and Searching Polynomial representation using Arrays, Sparse matrix, Stacks, Queues-Circular Queues, Priority Queues, Double Ended Queues, Evaluation of Expressions Linear Search and Binary Search

Linked List and Memory Management Self Referential Structures, Dynamic Memory Allocation, Singly Linked List-Operations on Linked List. Doubly Linked List, Circular Linked List, Stacks and Queues using Linked List, Polynomial representation using Linked List Memory allocation and de-allocation-First-fit, Best-fit and Worst-fit allocation schemes

Trees and Graphs Trees, Binary Trees-Tree Operations, Binary Tree Representation, Tree Traversals, Binary Search Trees- Binary Search Tree Operations Graphs, Representation of Graphs, Depth First Search and Breadth First Search on Graphs, Applications of Graphs

Sorting and Hashing Sorting Techniques – Selection Sort, Insertion Sort, Quick Sort, Merge Sort and Heap Sort Hashing- Hashing Techniques, Collision Resolution, Overflow handling, Hashing functions – Mid square, Division, Folding, Digit Analysis

QUESTIONS

1. Write a program to read two polynomials and store them in an array. Calculate the sum of the two polynomials and display the first polynomial, second polynomial and the resultant polynomial. Answer

2. Write a program to enter two matrices in normal form . Write a function to convert two matrices to tuple form and display it. Also find the transpose of the two matrices represented in tuple form and display it. Answer

3. Write a program to Write a program to enter two matrices in normal form . Write a function to convert two matrices to tuple form and display it. Also find the sum of the two matrices in tuple form and display the sum in tuple form. Answer

4. Implement a circular queue using arrays with the operations:

• Insert an element to the queue.
• Delete an elements from the queue.
• Display the contents of the queue after each operation. Answer

5. Implement a Queue using arrays with the operations:

• Insert elements to the Queue.
• Delete elements from the Queue.
• Display the contents of the Queue after each operation. Answer

6. Implement a Stack using arrays with the operations:

• Pushing elements to the Stack.
• Popping elements from the Stack
• Display the contents of the Stack after each operation. Answer

7. Implement a Priority Queue using arrays with the operations:

• Insert elements to the Priority Queue.
• Delete elements from the Priority Queue.
• Display the contents of the Priority Queue after each operation. Answer

8. Implement a Double-Ended Queue (DEQUEUE) with the operations:

• Insert elements to the Front of the queue.
• Insert elements to the Rear of the queue
• Delete elements from the Front of the queue.
• Delete elements from the Rear of the queue.
• Display the queue after each operation. Answer

9. Using stack convert an infix expression to a postfix expression and evaluate the postfix expression. Answer

10. Write a menu driven program for performing the following operations on a Linked List:

• Display
• Insert at Beginning
• Insert at End
• Insert at a specified Position
• Delete from Beginning
• Delete from End
• Delete from a specified Position Answer

11. Implement a stack using linked list with the operations:

• Push elements to the queue.
• Pop elements from the queue.
• Display the queue after each operation. Answer

12. Implement a Queue using linked list with the operations:

• Insert an elements to the queue.
• Delete an elements from the queue.
• Display the queue after each operation. Answer

13. Write a program to reverse the content of queue using stack Answer

14. Implementation of searching algorithms linear search, binary search

• Answer 1. Linear Search
• Answer 2. Binary Search

15. Write a program to read two polynomials and store them using linked list. Calculate the sum of the two polynomials and display the first polynomial, second polynomial and the resultant polynomial. Answer
16. Write a program to read two polynomials and store them using linked list. Find the product of two polynomials and store the result using linked list. Display the resultant polynomial. Answer
17. Create a Doubly Linked List from a string taking each character from the string. Check if the given string is palindrome in an efficient method. Answer
18. Create a binary search tree with the following operations:

• Insert a new node .
• Inorder traversal.
• Preorder traversal.
• Postorder traversal.
• Delete a node. Answer

19. Represent any given graph and

• Perform a depth first search .
• Perform a breadth first search. Answer

20. Implementation of sorting algorithms – bubble, insertion, selection, quick, merge sort

• Answer 1. Bubble sort
• Answer 2. Insertion sort
• Answer 3. Selection sort
• Answer 4. Quick sort
• Answer 5. Merge sort