Design and Analysis of Algorithms
Unit 3: Divide & Conquer, and Greedy Algorithm
- Q1). What do you mean by Graph Theory? Explain.
- Q2). Write a note on Graph and Digraph.
- Q3). Explain various data structure for Graphs.
- Q4). Write a note on Breadth First Search(BFS).What type of problem i can solve using BFS.
- Q5). Write a note on Depth First Search(DFS).What type of problem i can solve using DFS.
- Q6). Write a note on Bipartite Graph.
- Q7). Explain Topological Sort.
- Q8). Discuss Strongly Connected Components with its algorithm.
- Q9). What do you mean by Minimum Spanning Tree? Explain.
- Q10). Discuss Kruskal's Algorithm to find MST with example and also find its analysis.
- Q11). Discuss Prim's Algorithm to find MST with example and also find its analysis.
- Q12). Explain Bellman-Ford Algorithm and give its analysis.
- Q13). Suppose that undirected graph G=(V,E) has non-negative edge weights and these are raised by 1. Can the minimum spanning tree changes? Can shortest paths changes? Justify with proper example.
- Q14). Expalin the greedy approach of algorithm.
- Q15). Write the characteristics and structure of Greedy Algorithm.
- Q16). Explain the Activity Selection Problem and give its solution by using Greedy approach with its analysis and correctness.
- Q17). What do you mean by "Greey Algorithm"? Write its pseudo code and prove that the fractional knapsack problem has a greedy-choice property.
- Q18). What is 0/1 knapsack problem? Does greedy method effctive to solve the 0/1 knapsack problem?
- Q19). Explain the Huffman Codes with examples.
- Q20). Explain the travelling salesman problem.
- Q21). What do you mean by Flow? Write Ford Fulkerson algorithm to find maximum flow in a network.
- Q22). Write an algorithm to find the minimum and maximum elements simulteneously from a given list of elements. you are also required to discuss its running time.
