Greedy Algorithms and Applications

A greedy algorithm that finds the shortest path between two nodes in a weighted graph.

A set of nodes whose shortest paths from the source node have already been determined.

The current estimated distance of a node from the source node.

The node that precedes a given node in the shortest path from the source node.

Initialize: Set IN to the source node, set d-values for all nodes (0 for the source, infinity for others).

Repeat until all nodes are in IN: Select the node with the smallest d-value not in IN, add it to IN. Recompute d-values for all neighbors of the new node.

Once a node is added to IN, its d-value (shortest distance) is finalized. Adding another node to IN later cannot create a shorter path to a node already in IN.

It makes locally optimal decisions, choosing the node with the smallest d-value at each step, to find the overall shortest path.

A mathematical technique used to prove a statement true for all natural numbers. It involves two steps: base case (proving the statement true for the smallest number) and inductive step (assuming the statement is true for a specific number and proving it true for the next number).

Big Theta notation representing an algorithm's time complexity. It indicates that the algorithm's runtime grows proportionally to the square of the input size.

The process of converting characters (letters, numbers, symbols) into a unique binary representation that computers can understand and store.

A character encoding scheme where each character is assigned a fixed number of bits, regardless of its frequency of occurrence.

A character encoding scheme where frequently occurring characters are assigned shorter bit sequences, while less frequent characters are assigned longer sequences.

American Standard Code for Information Interchange. A widely used character encoding standard that assigns 8 bits to each character, allowing for 256 unique characters.

A character encoding standard that uses 16 or 32 bits per character, supporting a wider range of characters from different languages.

A code where no code sequence is a prefix of another code sequence. This ensures that the code can be uniquely decoded without ambiguity.

Variable-length encoding optimizes storage by assigning shorter codes to frequently occurring characters, reducing the overall number of bits required.

In the example, using fixed-length encoding with 3 bits per character, the total storage requirement is 150,000 bits (50,000 characters * 3 bits/character).

In the example, using variable-length encoding, the total storage requirement is 108,500 bits. This is significantly less than the fixed-length scheme.

Each bit in the code is sequentially considered, narrowing down the possible character until it is uniquely identified. This is possible because the code is a prefix code.

Prefix codes enable unique decoding without false starts or backtracking, making the decoding process efficient and error-free.

A Huffman tree is optimal because it minimizes the weighted path length (E(T)) by strategically grouping nodes with the lowest frequencies. This ensures efficient data encoding and transmission.

In a Huffman tree, siblings at the lowest level (nodes with the smallest frequencies) can be interchanged without impacting the overall optimality (E(T)).

Combining two nodes with the lowest frequencies into a parent node with their combined frequency preserves optimality. The parent node becomes a new internal node in the tree.

An optimal tree for a set of frequencies is one that minimizes the weighted path length (E(T)) across all possible tree configurations.

E(T) represents the weighted path length of a Huffman tree. It is the sum of the frequencies of each node multiplied by its depth (distance from the root).

Nodes with the lowest frequencies are typically placed at the bottom level of a Huffman tree, forming sibling pairs.

Huffman trees are built by repeatedly merging the two lowest frequency nodes until all nodes are incorporated into a single tree structure.

JPEG is an image compression standard that utilizes Huffman coding to efficiently encode and compress photographic images.

An algorithm exhibits the greedy-choice property if at each step, the best immediate choice is made, leading to an optimal solution for the entire problem.

A shortest-path algorithm finds the shortest path between two nodes in a graph, where the path length might be represented by the distance, cost, or time taken.

A proof technique where you prove the base case (smallest size of IN) and then assume the property holds for a specific size of IN (k). Then you prove the property also holds for the next size (k+1).

It represents the length of the shortest path from node x to node p, passing through node v.

The algorithm chose node p as the next node because it was closer to the starting point x (in terms of distance or cost) than the other options, such as z. Thus, the path going through v is shorter than the path going through z.

Determining the next node p to add to IN takes (n) operations, which means the time required grows linearly with the number of nodes in the graph (n).

The for loop takes (n) operations, where n is the number of nodes in the graph. It operates by checking each node z to see if it’s in IN and updating its distance and parent node if necessary.

The overall complexity of the shortest-path algorithm described in the text is (n2), which means the time it takes to run grows quadratically with the number of nodes in the graph.

A standard for compressing images, developed by the Joint Photographic Experts Group.

A type of data compression that discards some information to reduce file size, resulting in a smaller but less accurate representation.

A type of data compression that preserves all information, allowing the original data to be perfectly reconstructed.

A lossless compression technique that assigns shorter codes to frequently occurring data and longer codes to infrequent data.

The perceived brightness or darkness of an image. It is a key factor in how humans perceive images.

In image processing, the process of rounding and simplifying image data to reduce file size.

JPEG compression involves multiple stages that take advantage of human perception to reduce file size, including luminance/color separation, quantization, and Huffman encoding.

JPEG compression achieves smaller file sizes by reducing quality. The amount of detail lost depends on the compression level.