Chapter 5-7: Trees, Graphs, Algorithms, and Sorting (PDF)

CHAPTER 5: TREES AND GRAPHS 1. What is the space complexity of an Adjacency List representation of a graph? - O(V + E) 2. What type of graph has edges with weights or costs associated with them? - Weighted Graph 3. Which statement describes a binary tree? - A hierarchical data...

CHAPTER 5: TREES AND GRAPHS 1. What is the space complexity of an Adjacency List representation of a graph? - O(V + E) 2. What type of graph has edges with weights or costs associated with them? - Weighted Graph 3. Which statement describes a binary tree? - A hierarchical data structure in which each node has at most two children. 4. What is the space complexity of an adjacency matrix representation of a graph? - O(V\^2) 5. What is an AVL tree? - A type of binary search tree (BST) that maintains balance by ensuring the height difference between the left and right subtrees of any node is at most 1. 6. What is the purpose of breadth-first search (BFS) in graph traversal? - To explore all vertices at the present depth level before moving on to vertices at the next depth level. 7. Which property defines a balanced binary tree? - The height of the left and right subtrees of any node differ by at most 1. 8. What is a binary tree? - A hierarchical data structure in which each node has at most two children. 9. How is rebalancing done in AVL trees? - Using rotations. 10. What is the worst-case time complexity for operations in an unbalanced binary search tree (BST)? - O(n) 11. What are graphs used for? - To model relationships between objects by consisting of vertices and edges. 12. What time complexity does a balanced binary search tree (BST) guarantee for search, insertion, and deletion? - O(log n) CHAPTER 6: ALGORITHMS (SORTING AND SEARCHING) 1. Which sorting algorithm is considered stable? - Merge Sort 2. Which sorting algorithm uses the concept of \"partitioning\"? - Quick Sort 3. Which searching algorithm is efficient for a sorted list? - Binary Search 4. What is the time complexity of the Binary Search algorithm in the worst case? - O(log n) 5. In Binary Search, if the target element is greater than the middle element, what is the next step? - Search the right half 6. What is the best-case time complexity of the Bubble Sort algorithm? - O(n) 7. Which algorithm is not suitable for large datasets due to its high time complexity? - Bubble Sort 8. What is the worst-case time complexity of the Quick Sort algorithm? - O(n\^2) 9. Which algorithm repeatedly finds the smallest element and places it at the beginning? - Selection Sort 10. Which sorting algorithm has the best average-case time complexity? - Merge Sort 11. Which sorting algorithm is suitable for small datasets or nearly sorted arrays? - Insertion Sort 12. Which sorting algorithm has the best time complexity in the average case? - Merge Sort 13. Which searching algorithm has a time complexity of O(n) in the worst case? - Linear Search 14. Which sorting algorithm has the best space complexity? - Insertion Sort 15. Which sorting algorithm divides the input into a sorted and unsorted region? - Selection Sort 16. Which searching algorithm is optimal for sorted data? - Binary Search 17. Which sorting algorithm has the worst time complexity in the worst-case scenario? - Bubble Sort 18. Which searching algorithm requires the dataset to be sorted? - Binary Search 19. Which searching algorithm has a time complexity of O(1) on average? - Hashing 20. Which sorting algorithm is considered stable? - Merge Sort CHAPTER 7: DIVIDE AND CONQUER AND GREEDY ALGORITHM 1. What is the recurrence relation for the time complexity of merge sort? - T(n) = 2T(n/2) + O(n) 2. What is the main disadvantage of the divide and conquer approach? - It may require more memory for recursion 3. In a divide and conquer algorithm, how is the problem size reduced in each step? - It is split into two halves 4. Which of the following problems is typically solved using divide and conquer? - Multiplying large integers (e.g., Karatsuba algorithm) 5. What are the three main steps in a divide and conquer algorithm? - Divide, Conquer, Combine 6. Which of the following algorithms does \*not\* use the divide and conquer approach? - Bubble Sort 7. What is the base case in divide and conquer algorithms? - The point where the input is reduced to a trivial problem size 8. What is the time complexity of merge sort in the worst case? - O(n log n) 9. What is a characteristic of Greedy Algorithms? - Making locally optimal choices at each step 10. What is the Greedy Choice Property? - A global optimum can be achieved by selecting a local optimum 11. Which sorting algorithm uses the Divide and Conquer approach? - Merge Sort 12. Which algorithm makes use of the Greedy approach for finding the shortest path? - Dijkstra\'s Algorithm 13. What is a characteristic of Divide and Conquer? - Dividing the problem into smaller independent subproblems 14. What is the key characteristic of Dynamic Programming? - Overlapping subproblems 15. What is the time complexity of Merge Sort? - O(n log n) 16. What are the steps involved in the Divide and Conquer strategy? - Divide, Conquer, Combine 17. Which problem can be solved using Dynamic Programming? - Longest Common Subsequence 18. What is Divide and Conquer? - A problem-solving strategy that breaks a problem into smaller subproblems, solves each subproblem recursively, and then combines the solutions to get the final solution. CHAPTER 8: BRUTE FORCE DESIGN ALGORITHM 1. What is a limitation of the brute force approach in terms of optimization? - It does not leverage problem-specific knowledge, heuristics, or patterns 2. When is the brute force approach used? - When the problem is small in scale or when no better algorithm is immediately available 3. What are some applications of the brute force approach? - Search problems, optimization problems, cryptography, brute force algorithms 4. What is a limitation of the brute force approach in terms of time complexity? - Exponential time complexity, leading to impractical computation time for large problem sizes 5. When is it appropriate to use the brute force approach? - For problems with a small number of possibilities, when no optimized algorithm is readily available, and when no discernible pattern or optimization exists 6. What is the knapsack problem? - Determining the maximum value that can be obtained by selecting a subset of items without exceeding the weight capacity of a knapsack 7. What is the brute force approach? - Trying all possible solutions to a problem until the correct or optimal one is found 8. What is the solution approach for the knapsack problem using brute force? - Consider all possible combinations of items, check if they fit within the weight limit, calculate their total value, and keep track of the maximum value 9. What is a limitation of the brute force approach in terms of memory usage? - It may require storing a large number of intermediate results, leading to high memory usage