Data Structures & Algorithms
NPTEL MOOC on DSA by IIT Delhi Teacher Dr. Naveen Garg
https://nptel.ac.in/courses/106/102/106102064/
Suggested Courses
*Learning Data Structures and Algorithms*
https://www.udemy.com/course/learning-data-structuresand-algorithms/
*Data Structures and Algorithms Tutorials and Courses
https://hackr.io/tutorials/learn-data-structures-algorithms
*Data Structures and Algorithms Specialization*
https://www.coursera.org/specializations/data-structuresalgorithms
*C++ with Data Structures and Algorithms by Coding Ninjas*
https://www.codingninjas.com/courses/onlline-c-plus-pluscourse
*Algorithms and Data Structures*
Top 100 DSA Questions from Exam Point of View:
Q1. Define Data Structures.
Q2. Classify Data structures from different point of views.
Q3. What do you mean by ADT?
Q4. Write two ways of searching an element in a given array.
Q5. Write the algorithm for bubble sort.
Q6. What do you mean by analysis of an algorithm?
Q7. Define Asymptotic Notations.
Q8. Define Space and Time Complexity.
Q9. List different operations on a data structure and define each one.
Q10. What do you mean by Time Space Trade-off?
Q11. How can you say time complexity of an algorithm depends upon input size? Justify.
Q12. What do you mean by growth of a function?
Q13. What is the basic criterion every algorithm must satisfy?
Q14. List some desired features in an effective algorithm.
Q15. What do you mean by Linear Search? What is its time complexity?
Q16. Write recursive algorithm for binary search?
Q17. State an essential condition for binary search.
Q18. Differentiate between Linear Search and Binary Search.
Q19. How can we traverse a given array of n elements?
Q20. Write the code for insertion of an element in an array.
Q21. Differentiate between static and dynamic implementation of an array.
Q22. What are Best, Average and Worst cases in context of Algorithm Analysis?
Q23. Write Time complexities for Binary Search in Best, Avg. and Worst cases.
Q24. Derive the time complexity for binary search.
Q25. What do you mean by Stack and Queue ADTs?
Q26. Sort the following array using Quick Sort. Give steps for the same. 87, 34, 69, 22, 50, 2, 18, 61, 7, 82
Q27. Write Overflow and Underflow conditions for Stack and Queue.
Q28. Sort the following array using Merge Sort. Give steps for the same. 96, 54, 42, 11, 69, 70, 77, 5, 10, 21
Q29. Implement Stack using arrays.
Q30. Write algorithm for PUSH and POP using Linked List.
Q31. Write algorithm for Enqueue and Dequeue using array.
Q32. Write algorithm for Enqueue and Dequeue using Linked List.
Q33. Write the algorithm for Insertion Sort.
Q34. What do you mean by Linked List and describe various forms of linked list.
Q35. What do you mean by Infix, Prefix and Postfix expressions?
Q36. Write the code for converting an infix expression to postfix expression using stack.
Q37. Write an algorithm for postfix evaluation using stack.
Q38. What do you mean by Tower of Hanoi? Provide its solution.
Q39. What do you mean by a circular queue? Give overflow and underflow conditions in a circular queue.
Q40. Differentiate between linear queue and circular queue.
Q41. Define Priority Queue. Give rules for insertion, deletion or traversal in a priority queue.
Q42. Explain any two applications of stack.
Q43. How circular queue are better than Simple queue?
Q45. Write the code for Merge Sort. On what mechanism it is based upon?
Q46. What do you mean by pivot element in Quick Sort? Explain its role.
Q47. Write the algorithm for selection sort.
Q48. Write the time complexity for Worst case of Bubble Sort, Insertion Sort and Merge Sort. Which one is better and why?
Q49. What do you mean by AVAIL? Why we use AVAIL in context of a linked list?
Q50. What do you understand by a doubly linked list? State its advantage over singly linked list.
Q51. Write the code for insertion in the beginning in a singly linked list.
Q52. How do we traverse a singly linked list? In what ways it can be converted into a circular linked list?
Q53. Define Header Node in a Header linked list. What is its significance?
Q54. Write the algorithm for traversal of a doubly linked list. What is the other name of doubly linked list?
Q55. Differentiate between different sorting algorithms in context of time complexities in Best, Avg and Worst Cases.
Q56. Write the code for Heap Sort.
Q57. Define Max Heap. What is Max Heap Property? How can we access parent, left child and right child of nth node in a Heap?
Q58. Which kind of Heap is used to create a priority queue?
Q59. State Applications of a Heap and explain any two of them.
Q60. What do you mean by a Binary Search Tree? Write the property of a Binary Search Tree.
Q61. What do you mean by balance factor in an AVL Tree?
Q62. Differentiate between AVL Tree and BST.
Q63. What are different Tree traversals? Write algorithm for Preorder traversal using stack.
Q64. Differentiate between Binary Tree and Binary Search Tree.
Q65. Write a short note on Hashing.
Q66. What do you mean by collision? What are collision resolution techniques?
Q67. Write a short note on Threaded Binary Tree.
Q68. List and explain any two applications of Binary Trees.
Q69. Write a short note on B+ Tree. What is the key difference between B- Tree and B+ Tree?
Q70. Analyze complexity of all operations available on linked lists.
Q71. What do you mean by a stable sort? Prove with the help of an example that Bubble sort is stable.
Q72. What do you mean by an in-place sort? How can you say Merge Sort is not an in-place sort?
Q73. Write the algorithm for Quick Sort. Discuss its advantages over Merge sort.
Q74. Discuss the relevance of Divide and Conquer strategy in context of Binary Search.
Q75. Differentiate between BFS and DFS.
Q76. What do you mean by a tree? How it is different from a graph?
Q77. Define Graph. What are its types? How can we represent a graph in memory?
Q78. What do you mean by in-degree and out-degree in a graph?
Q79. How do we search in a linked list? Write algorithm for the same.
Q80. Write Overflow and underflow conditions in a linked list.
Q81. Depict pictorially the insertion of an element named ITEM in a NEW node at the end of a linked list.
Q82. Describe steps for deletion of an element with given ITEM from a linked list.
Q83. Define Recursion. Explain one example problem that solves with the help of recursion.
Q84. Evaluate the given postfix expression - P: 5, 6, 2, +, *, 12, 4, /, -
Q85. Covert the given infix expression I: A+(B*C-(D/E^F)*G)*H into its equivalent postfix expression P.
Q86. Derive Time complexity of Insertion sort in worst, best and average cases.
Q87. What are two essential properties of a recursive procedure?
Q88. Implement Circular Queue using Linked List.
Q89. Convert Q:((A+B)*D)^(E-F) into postfix expression.
Q90. Write an algorithm to check whether parenthesis in a given expression are balanced or not.
Q91. Write an algorithm to merge two given sorted arrays into one sorted array.
Q92. How do we represent following data structures in memory: Array, Linked List, Tree, Graph, Stack and Queue.
Q93. What do you mean by following?
a) Labeled graph
b) Weighted graph
c) Simple Path
d) Cycle
e) Loop
f) Degree of a graph
g) Connected Graph
h) Transpose of a Graph
i) Transitive closure of a graph
j) Height of a tree
Q94. Define following:
a) Min-Heap
b) Directed Graph
c) Forest
d) Root
e) Sparse Matrix
f) Deque
g) Complete Binary Tree
h) 2-Tree
i) Inorder successor of a node
j) Multigraph
Q95. Write the algorithm for deletion from a Binary Search Tree discussing all three cases.
Q96. Give a formal presentation for post-order traversal of a binary tree.
Q97. Describe rotation in an AVL tree when balance gets disturbed due to insertion of a new node in
i) Left subtree of a right subtree of a node.
ii) Left subtree of a Left subtree of a node.
iii) Right subtree of a left subtree of a node.
iv) Right subtree of a right subtree of a node.
Q98. Describe HEAPSORT and sort the given array using HEAPSORT. 66 55 34 21 8 50 43 80
Q99. Write algorithm for BFS describing it in detail with the help of an example.
Q100. Write algorithm for DFS describing it in detail with the help of an example.