Design and Analysis of Algorithms

Semester 2, Academic Year 2021-2022

Project Phase I

Due: Jan 28, 2023 Points: 40 _________________________________________________

In the DAA course project, you will solve your favorite algorithmic problem by designing and implementing an algorithm for that. There are many problems that can be solved using specific algorithms and many of them resemble real-life problems.

The following list shows the important problem types. The problem that you are going to choose for your project should fall into one of these categories:

Sorting

Searching

String processing

Graph problems

Combinatorial problems

Geometric problems

Numerical problems

To search for suitable topics, the following online sources are suggested.

Codeforces

URI Online Judge

UVa Online Judge - Home

Pick a topic that matches your interest and the course outline from the above-mentioned links or any other relevant sources. Note that the problem topic must be challenging enough to consider as a course project.

In the first phase you have to submit a hard copy including the following components:

A mathematical model for the solution (10 points)

Algorithm that you have designed (15 points)

Analysis of the algorithm (10 points)

Determine the time and space complexity (establishing the order of growth) of the algorithm (5 points)

The project can be done in group of maximum three students after taking approval from the instructor. For late submission 10% will be deducted for each day including weekends. You are required to use the template for writing the report.

Design and Analysis of Algorithms

Semester 2, Academic Year 2021-2022

Project Phase II

Due: Feb21, 2023 Points: 60 ____________________________________________________

In this phase you have to do the following:

Redesign the algorithm of phase I if required

You need to implement the algorithm that you have designed (30 points)

Detailed analysis of algorithms runtime over different sizes of inputs using plots and graphs (10 points)

Proof that your algorithm is correct. (10 points)

You need to submit a report along with the code of the implementation. (10 points)

Phase II of the project should be done within the same group. The report should include a contribution table describing the role of each group member during the conceptualization and implementation of the project. are not allowed to copy the code from anyone else. Any copying will result zero in the project. For late submission, 25% will be deducted for each day including weekends.

can you help me to select topic for this project !!!!!!!!!!!!!!!!!!!!!