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
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
Criteria Marks Comments
Header and inline comments: Appropriate header and inline comments for all the
header and source files.
Project organization: Code should be divided into header, implementation and tester
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