Explain the greedy algorithm for the fractional knapsack problem with its time complexity.
Marks: 5Chapter: Unit 4. Greedy Algorithms
Chapter Study
Bsc CSIT Semester 5 – Design and Analysis of Algorithms – Unit 4. Greedy Algorithms
Comprehensive questions and detailed answers for Unit 4. Greedy Algorithms. Perfect for exam preparation and concept clarity.
13
Questions
75
Marks
Explain the greedy algorithm for the fractional knapsack problem with its time complexity.
MediumTHEORY5 marks2076(TU Final)
Explain the approximation for solving vertex cover with a suitable example.
MediumTHEORY5 marks2076(TU Final)
Explain Prism’s algorithm for MST problem and analyze its time complexity.
MediumTHEORY5 marks2076(TU Final)
What do you mean by optimization problem? Explain the greedy strategy for algorithm design to solve optimization problems.
MediumTHEORY5 marks2078(TU Final)
Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy.
MediumTHEORY5 marks2078(TU Final)
Generate the prefix code for the string ” CYBER CRIME” using Huffman algorithm and find the total number of bits required.
MediumTHEORY5 marks2079(TU Final)
Find the MST from following graph using Kruskal’s algorithm.
MediumTHEORY5 marks2079(TU Final)
When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity.
MediumTHEORY5 marks2080(TU Final)
Suppose that a message contains alphabet frequencies as given below and find Huffman codes for each alphabet
| Symbol | Frequency |
|---|---|
| a | 30 |
| b | 20 |
| c | 25 |
| d | 15 |
| e | 35 |
MediumTHEORY5 marks2080(TU Final)
Does greedy algorithm guarantee optimal solution? Solve the Fractional knapsack problem to find maximum loot from given information.
| Item | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Value | 12 | 10 | 20 | 15 | 2 | 3 | 50 |
| Weight (kgs) | 2 | 1 | 3 | 2 | 12 | 10 | 1 |
MediumTHEORY10 marks2081(TU Final)
Explain the approximation algorithm for vertex cover of a connected graph with an examples.
MediumTHEORY5 marks2081(TU Final)
How do you define optimal solution? Does greedy algorithm always guarantee optimal solution? Given the string "SUPER DUPER CSIT", use a Greedy algorithm to build a Huffman tree.
MediumTHEORY10 marks2082(TU Final)
How does 0/1 Knapsack problem differ from fractional one? Find the minimum vertex cover in the following graph.
MediumTHEORY5 marks2082(TU Final)
Showing 13 questions
Sample Questions
Explain the approximation for solving vertex cover with a suitable example.
Marks: 5Chapter: Unit 4. Greedy Algorithms
Explain Prism’s algorithm for MST problem and analyze its time complexity.
Marks: 5Chapter: Unit 4. Greedy Algorithms
What do you mean by optimization problem? Explain the greedy strategy for algorithm design to solve optimization problems.
Marks: 5Chapter: Unit 4. Greedy Algorithms
Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy.
Marks: 5Chapter: Unit 4. Greedy Algorithms
And more questions available on this page.