Design and Analysis of Algorithms · Unit 4 · 6 hrs
Greedy Algorithms
Exam-focused notes for Greedy Algorithms (Design and Analysis of Algorithms, CSC325): what the TU syllabus asks and how it has actually been tested, with 10 solved past questions from this unit.
What this unit covers
- Optimization Problems and Optimal Solution, Introduction of Greedy Algorithms, Elements of Greedy Strategy
- Greedy Algorithms: Fractional Knapsack, Job sequencing with Deadlines, Kruskal's Algorithm, Prims Algorithm, Dijkstra's Algorithm and their Analysis
- Huffman Coding: Purpose of Huffman Coding, Prefix Codes, Huffman Coding Algorithm and its Analysis
Huffman Coding
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.[10]
An optimal solution is the best possible feasible solution to a problem: the one that maximizes or minimizes the objective function (maximum profit, minimum cost, shortest path, etc.) while satisfying all constraints. Among all feasible solutions, the optim...
Full solved answer →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 |
[5]
Symbol Frequency ------------------- a 30 b 20 c 25 d 15 e 35 Total frequency $= 30 + 20 + 25 + 15 + 35 = 125$ --- Sort ascending: d(15), b(20), c(25), a(30), e(35) Node db(35) Remaining: c(25), a(30), e(35), db(35) Node ca(55) Remaining: e(35), db(35), ca(...
Full solved answer →Generate the prefix code for the string "CYBER CRIME" using Huffman algorithm and find the total number of bits required. [5]
String: CYBER CRIME (11 characters including one space) Character frequencies: Character Frequency ---------------------- C 2 Y 1 B 1 E 2 R 2 Space 1 I 1 M 1 Total = $2+1+1+2+2+1+1+1 = 11$ characters, 8 distinct symbols. --- Order the nodes by frequency. Th...
Full solved answer →Greedy Algorithms
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 |
[10]
Item 1 2 3 4 5 6 7 --------------------------- Value 12 10 20 15 2 3 50 Weight (kg) 2 1 3 2 12 10 1 Missing data: The knapsack capacity $W$ is not given in the problem. This is essential to solve the fractional knapsack. This solution assumes $W = 15$ kg, w...
Full solved answer →When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity. [5]
A greedy strategy provides an optimal solution when the problem satisfies the following conditions: 1. Greedy Choice Property: A globally optimal solution can be reached by making a locally optimal (greedy) choice at each step. That is, the choice that look...
Full solved answer →Find the MST from following graph using Kruskal's algorithm. [5]
The question asks to find the MST from a given graph using Kruskal's algorithm. Missing data: No graph image, adjacency matrix, edge list, or vertex/weight information was provided with the question. The actual graph is unreadable/absent. Because no numeric...
Full solved answer →Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy. [5]
Given n jobs, each with a deadline and a profit (earned only if the job is completed by its deadline), find a feasible sequence of jobs that maximizes total profit. Each job takes unit time to complete and only one machine (processor) is available. --- The ...
Full solved answer →Explain the greedy algorithm for the fractional knapsack problem with its time complexity. [5]
A thief has a knapsack that can carry a maximum weight W. There are n items, where the i-th item has: - Weight: w[i] - Value: v[i] Any fraction of an item can be taken (unlike 0/1 knapsack). The objective is to maximize total profit by selecting items or fr...
Full solved answer →Explain Prim’s algorithm for MST problem and analyze its time complexity. [5]
A Minimum Spanning Tree (MST) of a weighted, connected, undirected graph is a spanning tree whose total edge weight is minimum among all possible spanning trees. Prim's Algorithm is a greedy algorithm that builds the MST by starting from an arbitrary vertex...
Full solved answer →Optimization Problems and Optimal Solution, Introduction of Greedy Algorithms, Elements of Greedy Strategy
What do you mean by optimization problem? Explain the greedy strategy for algorithm design to solve optimization problems. [5]
An optimization problem is the problem of finding the best solution from all feasible solutions. The goal is either to maximize or minimize some objective function subject to given constraints. Optimization problems can be divided into two categories: - Dis...
Full solved answer →Make Unit 4 stick
Practice CSC325 with flashcards & quizzes