Description

QUESTION 1

You are required to do a comparative study to compare theoretical performance with practical

demonstration of the following algorithms:

1- At least two sorting algorithms, only one of which can be among the algorithms that have

already been discussed in the class.

2- At least two search algorithms with at least one of them having Big O efficiency of O(log n

) or better, for example, Hash tables. You may use algorithms discussed in the course,

however, you are encouraged to include other algorithms as well.

3- The report should be of about 1,000-1500 words and of not more than about ten pages

including screenshots and references etc.

4- Don’t discuss the general implementation (C code) of the algorithms, however, use inline

comments to reflect your understanding of the code. Similarly avoid very detailed

description of algorithms, instead give appropriate references.

You must demonstrate performance with respect to at least the following parameters:

a. Number of records: small (less than 100,000), medium (~ 500,000) and large (one

million or higher).

b. Randomness of the data, for example partially ordered data vs. pseudo-random data.

c. Any algorithm specific parameter, for example pivot in case of quicksort algorithm.

You should analyze/comment on the performance of the algorithm with respect to

any variation of such a critical parameter.

The interface of the application must be console-based, menu-driven, very similar to the screenshot

given below:

You must submit the following:

1- Source code of tester, implementation and header files as a single zipped file of CLion

project. Your tester file must demonstrate testing of algorithms under different conditions.

Code should be error-free C code with detailed inline and header comments to convince me

that you have understood working of the code.

2- The report which must be the commentary on algorithms describing their relative

strengths and weaknesses and EXPLAINING any performance variations. Arguments

given should be supported by intuitive, meaningful and reproducible screenshots of

execution of C programs demonstrating performance of various algorithms.

3- Please note that interface of the application should be very similar to Figure 1.

The largest part of the evaluation will be based on the comparative performance

demonstration and discussion. You must make sure that all submitted code is fully functional and

results shown are reproducible. Specifically you must ensure the following:

1- Error-free working c code;

2- Inline and header comments in the source code reflecting understanding of the code;

3- Screenshots of code execution demonstrating relative performance of various algorithms

under various conditions of size and type of data and other constraints as discussed above.

This includes commentary on the relative performance and analysis of algorithms

describing any reasons for inferior or superior performance of an algorithm especially under

certain constraints, for example, partially sorted listed, or any critical parameter like pivot

position.

Criteria Marks Comments

Header and inline comments: Appropriate header and inline comments for all the

header and source files.

5

Project organization: Code should be divided into header, implementation and tester

files.

5

Setup of experimental work: General description of the work undertaken and approach

of investigation, algorithms compared and contrasted and any limitations of the work is

clearly described.

15