14012402-4 Algorithms PROGRAMMING PROJECT TOPICS You are expected to select one of programming topics that described below or other programming proposals that you may have on your own, provided they have a very strong relation to the contents of this course. Once the project is completed, include the following in your presentation and project: A demonstration of your project in which you show the various features of your system, such as its correctness, efficiency, etc. You should be prepared to answer detailed questions on the system design and implementation during this demo. We will also examine your code to check for code quality, code documentation, etc. You should also hand in a completed project report, which is essentially a polished version of the project design document, but should also include some experimental results, e.g. charts of running time versus input size, etc. You should also turn in your code and associated documentation (e.g. README files) so that everything can be backed up for future reference. submit your code and all associated files to blackboard Project Topics: Shortest Paths and Minimum Spanning Trees: In this project you will implement the Dijkstras shortest path algorithm as well as Prims minimum spanning tree algorithm, Kruskal's Algorithm and Boruvka's Algorithm. Assume adjacency list representations of the input graphs. Implement the fringe data structure using a binary heap and alternatively, as a linked list, and compare the two methods. Some animation which shows each major iteration of the algorithms will be very desirable. Have a user interface in which you can incrementally add edges to the graph and update the trees accordingly. Median finding, Order Statistics and Quick Sort: In this project you will implement the median-finding algorithms. The user should be able to select the k, i.e., the rank of the number desired as output (k = n/2 is the median). You should also be able to select groups of 3, 5, 7 etc. in the linear-time median finding algorithm and be able to compare the performance of each. Also implement the randomized median finding algorithm and compare against the linear-time one. Implement quick sort using both algorithms and compare the performances of these different versions. Convex Hull: Implement several versions of the convex hull algorithm: (a) the divide and conquer version, (b) the Graham Scan version, (c) the version in which a preprocessing step removes all points in the extremal quadrilateral, and (d) a convex hull algorithm when the input is not a set of points, but is a nonconvex polygon. Have a GUI where one can insert new points (for (d), the user can add a new vertex to the input polygon) and the application recalculates the hull. Compare the performances of all algorithms. Network Flow: Implement the Ford-Fulkerson algorithm for computing network flow in bipartite graphs. While your algorithm should be able to handle large graphs, for demo purposes design a GUI in which any bipartite graph of up to 20 nodes can be specified. Some animation which shows each major iteration of the algorithm will be very desirable. Run experiments that measure the performance of the algorithm over large inputs. String Matching algorithms: Implement both the KMP pattern matching algorithm as well as the Longest Common Subsequence (or Edit Distance) algorithm. Your algorithm should be tested out on real datasets, e.g., text files, biological sequence data, times series databases, etc. Compare the performances of each algorithm against naive algorithms for the same problems. Matrix Multiplication: Read up about how large matrices are multiplied. Implement the Soloway-Strassen matrix multiplication algorithm, as well as the nave algorithm. Compare the running time of the two algorithms experimentally using synthetically generated large matrices Sudoku Solver: Implement a brute force sudoku solver along with an optimized solver (Eg. The Backtracking Solver) for a matrix. Compare performance over varied datasets. Note: user interface, animation, clear code with comments and clear analysis of your algorithms will be considered in the final grades

14012402-4 Algorithms PROGRAMMING PROJECT TOPICS You are expected to select one of programming topics that described below or other programming proposals that you may have on your own, provided they have a very strong relation to the contents of this course. Once the project is completed, include the following in your presentation and project: A demonstration of your project in which you show the various features of your system, such as its correctness, efficiency, etc. You should be prepared to answer detailed questions on the system design and implementation during this demo, We will also examine your code to check for code quality, code documentation, etc. You should also hand in a completed project report, which is essentially a polished version of the project design document, but should also include some experimental results, e.g. charts of running time versus input size, etc. You should also turn in your code and associated documentation (e.g. README files) so that everything can be backed up for future reference. sub your code and all associated files to blackboard Project Topics: . Shortest Paths and Minimum Spanning Trees: In this project you will implement the Dijkstra's shortest path algorithm as well as Prim's minimum spanning tree algorithm, Kruskal's Algorithm and Boruvka's Algorithm. Assume adjacency list representations of the input graphs. Implement the fringe data structure using a binary heap and alternatively, as a linked list, and compare the two methods. Some animation which shows each major iteration of the algorithms will be very desirable. Have a user interface in which you can incrementally add edges to the graph and update the trees accordingly. Median finding, Order Statistics and Quick Sort: In this project you will implement the median-finding algorithms. The user should be able to select the "K", i.e., the rank of the number desired as output (k = n/2 is the median). You should also be able to select groups of 3, 5, 7 etc. in the linear-time median finding algorithm and be able to compare the performance of each. Also implement the randomized median finding algorithm and compare against the linear-time one. Implement quick sort using both algorithms and compare the performances of these different versions. Convex Hull: Implement several versions of the convex hull algorithm: (a) the divide and conquer version, (b) the Graham Scan version, (c) the version in which a preprocessing step removes all points in the extremal quadrilateral, and (d) a convex hull algorithm when the input is not a set of points, but is a nonconvex polygon. Have a GUI where one can insert new points (for (d), the user can add a new vertex to the input polygon) and the application recalculates the hull. Compare the performances of all algorithms. Network Flow: Implement the Ford-Fulkerson algorithm for computing network flow in bipartite graphs. While your algorithm should be able to handle large graphs, for demo purposes design a GUI in which any bipartite graph of up to 20 nodes can be specified. Some animation which shows each major iteration of the algorithm will be very desirable. Run experiments that measure the performance of the algorithm over large inputs. String Matching algorithms: Implement both the KMP pattern matching algorithm as well as the Longest Common Subsequence (or Edit Distance) algorithm. Your algorithm should be tested out on real datasets, e.g., text files, biological sequence data, times series databases, etc. Compare the performances of each algorithm against naive algorithms for the same problems. Matrix Multiplication: Read up about how large matrices are multiplied. Implement the Soloway-Strassen matrix multiplication algorithm, as well as the nave algorithm. Compare the running time of the two algorithms experimentally using synthetically generated large matrices Sudoku Solver: Implement a brute force sudoku solver along with an optimized solver (Eg. The Backtracking Solver) for a nxn matrix. Compare performance over varied datasets. . . Note: user interface, animation, clear code with comments and clear analysis of your algorithms will be considered in the final grades