CS 413: Analysis of Algorithms
Homework 3: Programming assignment
As it appears in the course syllabus, for the homework assignments, students are encouraged to
discuss the problems with others, but you are expected to turn in the results of your own effort
(not the results of another group or person). Even when not explicitly asked, you should justify
your answers concisely.
Consider the following problems and implement their corresponding algorithms in C++ or
Java:
1) Counting inversions as seen in the class (the divide and conquer approach) (30
points)
2) Merge sort algorithm to sort a list of n number in decreasing order (30 points)
Submission rules:
To submit the solution to the above assignment, you need to prepare the following files:
1- The source code of your program that includes all .cpp or .java files.
2- A standalone executable file of your program for each given problem.
3- A brief report about the code you have written + analysis of the worst-case time
complexity of your algorithm.
You will get a zero if any of the above cases are missing, or the grader is not able to run
your code.
You need to put all the above files into a folder, compress it, and upload the
compressed file on BB to the related repository.
