Using Huffman code, we can compress the bits used for saving the characters in a file: Total bits used for saving the character in table 1 is 264 bits using standard ASCII 8 bits for 1 character. Using Huffman code encoding in Table 2, the total bits used is 126 bits. The problem: ➢ Input: list of characters such as table 1 ➢ Output: total bits using Huffman code encoding (table 2) ➢ Task: Design an algorithm in pseudocode/code to print the total bits using Huffman code encoding and write down the Algorithm analysis. The complexity of the algorithm must be in O(n) and proof it! ➢ PS: you don’t need to sort the input since the input is already sorted!
1. Using Huffman code, we can compress the bits used for saving the characters in a file:
Total bits used for saving the character in table 1 is 264 bits using standard ASCII 8 bits for 1 character.
Using Huffman code encoding in Table 2, the total bits used is 126 bits.
The problem:
➢ Input: list of characters such as table 1
➢ Output: total bits using Huffman code encoding (table 2)
➢ Task: Design an
encoding and write down the Algorithm analysis. The complexity of the algorithm must be in
O(n) and proof it!
➢ PS: you don’t need to sort the input since the input is already sorted!
2. In a square maze, we can have multiple steps from ‘s’ to reach ‘e’ with one place that can only
be visited once. Example:
Input
3
s..
..#
.e#
Output
4
These are the unique steps:
*..
*..
**.
*..
**.
.*.
**.
.*.
.*.
**.
**.
**.
input
4
.s..
.#.#
#e.#
....
output
2
These are the unique steps:
.**.
..*.
.**.
.**.
.**.
..*.
.**.
....
The problem:
➢ Input: an integer followed by the maze.
➢ Output: total number of unique steps. (no need to print the unique steps)
➢ Task: Design an algorithm in pseudocode/code to print the total number of unique steps using
a backtracking algorithm.
Step by step
Solved in 2 steps with 1 images
