Data Structures and Algorithms - II Homeworks

Homework Assignments:

• Homework 1 : The program solves a maze by finding all possible paths from a starting point 'E' to a destination, while collecting treasures represented by lowercase letters. The program implements a recursive algorithm that explores the maze and uses backtracking to find all valid paths.
• Homework 2 : It includes two classes: GraphSOS and Trie.
  • The GraphSOS class solves a matrix transformation problem by identifying 'O' elements connected to the boundary and converting the remaining inner 'O' elements to 'X' while preserving the boundary-connected 'O' elements.
  • The Trie class implements a Trie data structure to find the minimum XOR value between an input mask and a set of binary numbers. The code takes user inputs, constructs a Trie using the binary numbers, and computes the minimum XOR values between the mask and each number, displaying the results as output.
• Homework 3 : It provides implementations of Dijkstra and Prim algorithms for optimizing transportation networks.
  • The Delivery class utilizes Dijkstra algorithm to calculate the shortest path between two vertices in a graph, making it ideal for determining efficient delivery routes.
  • The Traffic class applies Prim algorithm to find the minimum spanning tree (MST) of a graph representing a traffic network. By identifying the MST, it enables the optimization of traffic flow and the discovery of the most efficient routes within the road network.
• Homework 4 : It implements the "Longest Common Prefix" algorithm using a Trie data structure. It prompts the user to enter a list of strings and then finds the longest common prefix among them.