Greedy Algorithms

Question 1

Greedy Algorithms

Answer 1

Greedy algorithms make locally optimal choices at each step in the hope of finding a globally optimal solution. Examples include Interval Scheduling, Huffman Coding, and Kruskal’s Algorithm for Minimum Spanning Trees.

Question 2

Interval Scheduling

Answer 2

Interval Scheduling is a class of problems where you have a set of tasks, each with a start time and an end time, and you want to find a maximum-size subset of non-overlapping tasks that can be scheduled. The goal is to select the most tasks without any of them overlapping in time.

Question 3

Huffman Coding

Answer 3

Huffman Coding is a data compression algorithm used to compress data efficiently. It works by constructing a binary tree called the Huffman Tree, where characters (or symbols) are represented as leaves. The most frequent characters have shorter binary codes, while less frequent characters have longer codes. Huffman Coding is used in various file compression formats like ZIP and JPEG.

Question 4

Kruskal’s Algorithm for MST (Minimum Spanning Tree)

Answer 4

Kruskal’s Algorithm is used to find the Minimum Spanning Tree (MST) in a weighted, connected graph. The MST is a subset of edges that connects all nodes with the minimum possible total edge weight, and it contains no cycles. Kruskal’s Algorithm works by sorting all the edges by their weight and then adding edges one by one to the MST, avoiding cycles. It is a greedy algorithm because it always selects the shortest edge that does not form a cycle in the current MST.