COT5405-Analysis-of-Algorithms-Project

This simple project aims to compare the time complexity of different algorithms.
Programming language: C++
Project time：2020 Dec
Check 'AlgoTowers.cpp' and 'Report.pdf' files for details

Problem Definition

Consider a city in Florida named Gridville that has a grid layout of m × n cells. Associated with each cell (i, j) where i = 1, . . . , m and j = 1, . . . , n, Gridville architectural board assigns a non-negative number p[i, j] indicating the largest possible number of floors allowed to build on that block. A developer company named AlgoTowers is interested to find the largest possible area (shaped square or rectangle) of blocks within city limits that allows a building of height at least h

Algorithm Design Tasks

• Alg1 Design a Θ(mn) time Dynamic Programming algorithm for computing a largest area square block with all cells have the height permit value at least h. (Task1&2)
• Alg2 Design a Θ(m3n3) time Brute Force algorithm for computing a largest area rectangle block with all cells have the height permit value at least h. (Task3)
• Alg3 Design a Θ(mn) time Dynamic Programming algorithm for computing a largest area rectangle block with all cells have the height permit value at least h. [Hint: For gradual progress and also partial credit you might consider working on a O(mn2)-time algorithm design first.] (Task4&5)