Week 5 Tutorial
Uploaded by
hemaj903Week 5 Tutorial
Uploaded by
hemaj903Common questions
Powered by AIHuffman coding is solved using a greedy algorithm that constructs an optimal prefix-free binary tree. The time complexity is O(n log n), where n is the number of unique characters or symbols to encode, due to the priority queue operations required to repeatedly select and merge the two least frequent nodes .
Merging the two nodes with the least frequency ensures that less common characters appear deeper in the tree, and more common characters have shorter codes. This minimizes the total weighted path of the tree, used to encode the message with the shortest possible bit string length, adhering to the greedy algorithm's principle .
To construct a Huffman tree, determine the frequency of each character in the message. For "BANANAAPPLE", the frequencies are: B=1, A=3, N=2, P=2, L=1, E=1. Create nodes for each character and construct the tree by merging the two least frequent nodes iteratively until one node remains. Then assign binary codes starting from root to leaves. The encoded message requires at least 29 bits .
The greedy approach in TSP often does not yield the optimal solution compared to dynamic programming or backtracking. It simply chooses the local optimal solution at each step (nearest neighbor), which can lead to longer total paths overall. Dynamic programming considers multiple possible paths at each stage, providing a better approximation to the optimal tour, though it incurs higher computational costs .
To solve the fractional knapsack problem, first calculate the value per kg for each item, then sort items in descending order of this value. Start picking items with the highest value per kg until the weight limit is reached. If the limit is exceeded, take the item fractionally. For the given weights and values (A: 40, B: 42, C: 25, D: 24, E: 30), the optimal solution is to take items in the order of B, A, and then C fractionally to fill the knapsack to 15 Kg, yielding a maximum value of 92.2 .
Allowing fractional selection of items in the knapsack problem leads to better utilization of available weight capacity compared to 0/1 knapsack problem, as it optimizes the value-to-weight ratio. It provides flexibility to achieve higher overall value, especially when the total weight limit is strictly enforced and cannot accommodate all items fully .
To construct an optimal Huffman code, list character frequencies: A=2, B=3, C=4, D=4. Build a binary tree by iteratively selecting and merging the nodes with the lowest frequencies. Assign binary values to each character by traversing the tree from root to leaf. This results in a minimum encoding of 24 bits .
To determine the minimum number of classrooms needed, first sort classes by their finishing times and then iterate through them, assigning each class to a room that becomes free the earliest. For the given set of start and finish times, 3 classrooms are required. This scheduling ensures each classroom is utilized optimally without overlaps .
Sorting activities by finish time facilitates the selection of the maximum number of non-overlapping activities. This ensures at every step, the earliest possible finishing activity is selected, optimizing the number of activities accommodated since choosing the earliest finishing activity leaves the maximum remaining time for subsequent selections .
Using the greedy approach, which involves selecting the nearest unvisited city, starting from City A results in the sequence A -> B -> D -> C -> A. The total minimum travel distance is 67 units, calculated as follows: start at A, travel to the nearest city B (12 units), then to D (15 units), then to C (20 units), and finally return to A (18 units).