Programming Assignment

B$-$Trees

Implement the search method for a B$-$Tree.

The method should return the node containing the key if it exists, otherwise,

it should return null.

Implement the insert and delete methods for a B$-$Tree.

Ensure that the tree remains balanced after each operation.

Write unit tests to verify the correctness of both operations.

Dynamic Programming

Implement the rod cutting problem using dynamic programming.

Write a function that receives a rod length and a list of prices and returns

the maximum revenue achievable.

Implement the Longest Common Subsequence $($LCS$)$ problem using dy$-$

namic programming.

Write a function that receives two strings and returns their LCS$.$

Greedy Algorithms

Implement a greedy algorithm for a suitable problem of your choice $($e$.$g$.,$

coin change, scheduling$).$

Justify the choice of the greedy strategy for this problem.

Write unit tests to verify the correctness of your algorithm.

Huffman Codes

Implement Huffman coding for text compression.

Write a function that takes a string as input and outputs the encoded string

along with the Huffman tree.

Write a decoding function that takes the encoded string and the Huffman

tree and returns the original string.

Write unit tests to ensure your Huffman coding and decoding work correctly.

Graphs $-$ BFS and DFS

Implement both Breadth$-$First Search $($BFS$)$ and Depth$-$First Search $($DFS$)$

for graphs represented using adjacency lists.

Write functions that perform BFS and DFS starting from a given node and

explore all connected components.

Write unit tests to verify the correctness of both BFS and DFS implementa$-$

tions.

Submission Requirements

Your code should be well$-$documented with comments explaining the func$-$

tionality of each component.

Ensure that all unit tests pass and provide coverage for edge cases in your

implementations.

Submit a report detailing your approach, challenges faced, and the com$-$

plexity analysis of each algorithm implemented$($just code running times with

some comments are enough$).$