Algorithm Design & Analysis Questions

1. Using Huffman code, we can compress the bits used for saving the characters in a file:

Total bits used for saving the characters in table 1 is 264 bits using standard ASCII 8 bits for a 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 C/C++ 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 dont 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	Output
3 s.. ..# .e#	4 These are the unique steps: *.. *.. **. *.. **. .*. **. .*. .*. **. **. **.
4 .s.. .#.# #e.# ....	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 C/C++ code to print the total number of unique steps using a backtracking algorithm.

3. From the following list of bus rapid transit system (one way):

Name	Route
Vacation	A->B->C->D
Work 1	E->B->F->G->H
Work 2	B->N->E
Work 3	H->D->N

The problem:

• Task: Design an algorithm in C/C++ code to read the bus rapid transit system routes list and print the number of tickets we need to purchase if we want to visit all places minimal twice. The complexity of the algorithm must be O(V+E). V is the number of places. E-> is the number of transits.
• PS: Use Tarjans or Kosarajus strongly connected component algorithm.

4. In a string, we can have repeated pattern. Example:

Input	Output
abc	none
abaa	none
aaaa	(a) 4
abab	(ab) 2
abcabc	(abc) 2
ababacababac	(ab) 2
ababacababacababac	(ababac) 3

The problem:

• Input: a string in a line.
• Output: Print the pattern and the repeated count if there is a repeated pattern, Print "none" otherwise.
• Task: Design an algorithm in code C/C++ to for the problem and write down the Algorithm analysis. The complexity of the algorithm must be in O(n).
• PS: Use the KMP algorithm for string matching. The repeated pattern is valid only from the first character.

P.S:

- Please answer in a proper format - Please answer in a typed or softcopy format - Please don't do it with pen or pencil, do it with software or tools - If you want to ask any question, ask it in the comment section, I will try to answer it

Thanks!

Table. 1. Characters count. Character Frequency E 1 F 1 H 1 M 1 R 1 T 1 Y 1 2 12 D G 2 2 Table 2. Character bit using Huffman code Character Bits Frequency Total Bits Space 3 4 12 A 3 4 12 S 3 4 12 D 4 2 8 G 4 2 8 1 4 3 L 4 2 8 N 4 3 12 O 4 2 8 Y 4 1 4 E 5 1 5 F 5 1 5 H 5 1 5 . 5 1 5 R 5 1 5 T 5 1 5 Total: 126 3 L 0 1 N Space 2 2. 3 3 4 S 4 4 Table. 1. Characters count. Character Frequency E 1 F 1 H 1 M 1 R 1 T 1 Y 1 2 12 D G 2 2 Table 2. Character bit using Huffman code Character Bits Frequency Total Bits Space 3 4 12 A 3 4 12 S 3 4 12 D 4 2 8 G 4 2 8 1 4 3 L 4 2 8 N 4 3 12 O 4 2 8 Y 4 1 4 E 5 1 5 F 5 1 5 H 5 1 5 . 5 1 5 R 5 1 5 T 5 1 5 Total: 126 3 L 0 1 N Space 2 2. 3 3 4 S 4 4