Activity Selection Problem: Greedy Algorithms

Two leaves in the tree that share the same parent node and are at the lowest level.

A process where two bottom-most leaves are swapped with their parent. This creates a new node representing the combination of the two leaves.

A set of leaves and their associated frequencies, created by merging leaves and adjusting frequencies.

An optimal prefix code tree for the set S' created by merging leaves.

An algorithm that makes a locally optimal choice at each step, hoping this will lead to a globally optimal solution.

A tree that is obtained from T' by replacing the merged leaf node X with an internal node with the original two leaves c and c'.

A problem where finding the optimal solution involves choosing the largest coin denomination at each step, regardless of available denominations.

The situation where an optimal solution for the overall problem includes the greedy choice made at each step. This helps ensure that the greedy solution is also optimal.

A lemma that states that if T' is an optimal prefix code tree for S', then T is an optimal prefix code tree for S.

A coding scheme that generates the most efficient prefix code by repeatedly merging the two lowest frequency nodes in a tree.

A problem where the optimal solution involves selecting a set of activities, without overlaps, to maximize the number of activities attended.

The time complexity of Huffman's coding scheme, which is O(n log n).

The key factor in the Activity Selection Problem, where the activity with the earliest finish time is prioritized.

The situation where the greedy algorithm may not always find the optimal solution for the Coin Changing Problem.

The optimal solution for the Coin Changing Problem with denominations $1, $4, $5, $10 and a target of $8. The greedy algorithm wouldn't find this optimal solution.

The solution provided by the Greedy Algorithm for the Coin Changing problem with denominations $1, $4, $5, $10 and a target of $8.

A sequence of characters, often used to represent text.

The length of a string, measured by the number of characters it contains.

A property of an algorithm where the optimal solution to a problem can be obtained by making a series of locally optimal choices.

A property of an algorithm where the optimal solution to a problem contains within it the optimal solutions to its subproblems.

A classic optimization problem where you must select items with maximum total value from a set, considering a weight constraint.

A variation of the Knapsack problem where you are allowed to take fractional amounts (parts) of the items.

A method where characters are represented using a fixed number of bits, regardless of their frequency in the text.

A method where characters are represented using a variable number of bits, typically assigning fewer bits to frequently occurring characters and more bits to less frequent ones.

The process of converting information into a format suitable for storage or transmission.

A code where no codeword is a prefix of another codeword. This ensures that decoding is unambiguous, as you can identify each codeword in the encoded message without confusion.

A tree representation of a prefix code where each character is a leaf node and the path from the root to a leaf represents the codeword for that character. The further a leaf is from the root, the longer its codeword.

The problem arises when one codeword is a prefix of another. You cannot tell which string is the original, causing ambiguity in decoding.

A code that allows us to decode an encoded text into its original form without ambiguity. Each codeword is unique, and no codeword is a prefix of another.

The goal of encoding is to minimize the total length of the encoded text. The optimal code achieves this goal by assigning shorter codewords to more frequent characters.

In an optimal prefix code tree, the two characters with the lowest frequencies should share the same parent and be placed farthest from the root. This minimizes the overall code length.

A proof technique used in computer science where we assume a solution exists and then prove that it can be improved by modifying certain parts of the solution. This is often used to prove optimality in algorithms like Huffman coding.

Selecting activities with the shortest duration first might not lead to the optimal solution. For example, if the optimal solution has more activities than the shortest duration solution, the shortest duration solution might not include all the possible activities.

Choosing activities based on the earliest start time can result in a suboptimal solution, especially if the optimal solution involves selecting activities with later start times but longer durations.

The 'Cut-and-Paste' argument proves a greedy choice property by demonstrating that an optimal solution can always be constructed by incorporating the greedy choice without compromising optimality.

The proof by contradiction demonstrates that if the subproblem solution (excluding the earliest finish time activity) were not optimal, there would exist a solution with more activities, contradicting the optimality of the original solution including the earliest finish time activity.

The Greedy-Activity-Selector algorithm efficiently selects activities with the earliest finish times, ensuring that the selected activities do not conflict. Its time complexity is O(n), where n is the number of activities, assuming that finish times are sorted.