Foundations_of_Algorithms

JHU Foundations of Algorithms, 605.621 Summer 2021

PA_1: Closest pair of points

• Implemented the algorithm that returns the closest pair of points in a Euclidean two-dimensional plane.
• Implemented Simple algorithm using Brute-force algorithm.
• Implemented Improved algorithm using divide-and-conquer method.
• Compare/Contrast the two algorithm performances (time complexity) by analyzing the number of function calls of the algorithm.

PA_2 : The Maryland Lighthouse Challenge

• Implemented the traveling salesman problem (TSP) that finds the fastest tour covering all the lighthouses.
• Implemented Simple algorithm using Brute-force algorithm.
• Implemented the improved algorithm using the Nearest Neighbor method and Multi-Fragment Heuristic method.
• Analyzed the algorithm performance (time complexity) by measuring the number of function calls of the algorithm.

PA_3: Interleaving Strings

• Analyzed the dynamic programming algorithm that finds if a string is interleaved of two other strings.
• Improved the interleaving algorithm that handles leading noise and matching repetitions.