Merge sort vs randomized quicksort: Implement merge sort and randomized quick sort. Run your program gradually from small input (say, n=100) to very high input (say, n=100,000). Take random values as your input array. Compare the two algorithms for the following three things.

1. Count and compare number of “comparisons” among the input elements in both algorithms. Put your data in a table for comparison.
2. Count and compare the number of “copy/assignment” of the input elements in both algorithms. Put your data in a table for comparison.
3. Run both programs and plot/write table and compare their actual running time in (ms, sec, min).

Programming topics: For all programming topics, you shall have to use programming language’s clock function (or similar functions) to get the actual running time in (ms, sec, min) before and after the execution of the function that you write in your program. Then take the difference of these two times to get the actual execution time of your function. For example, if you implement merge sort algorithm, then use necessary get time function before and after the merge sort function to get the actual running time in ms, sec, or minutes of your merge sort.

• For a programming project, you shall have to implement a programming problem given in the list below. Then you shall have to write in a report your pseudo code, data structures used in your program, your findings, result comparison, and the program code itself. You can use any high level programming language to implement your program, such as C, C++, Java, C#, Python, etc. You can also add your idea on how to improve the existing results or any future development in that problem. You should write the programming code by yourself. Directly copying from other sources will incur penalties. A typical structure of a report for a programming project should contain: Title, your ID and Name, Abstract, Introduction, Pseudo code, Data structures, Comparisons by plotting/making tables for the running time and other data, Possible future works, Conclusion, References, Program code.
• A report should be maximum 10 pages, in English, and in 10-12 size fonts. For a programming project, your programming code can go to an appendix in extra pages.
• You shall also prepare a presentation. It will consists two things: slides and your presentation audio (no video). Slides will be in English. A presentation audio should be of 10 minutes maximum and in English. Presentation of more than 10 minutes may incur penalty. Your audio should follow your slides. So, the number of slides and audio length will depend upon each other.
• After I receive the project report and the presentation, I may ask you some questions on them. For example, I may ask you to explain some code on a programming project or some theoretical question on a theoretical project.
• Make your project report as a pdf and give the file name as “Report-YourProjectID-YourID”. Send me the file by email with email subject as “Report-YourProjectID-YourID”.
• Make your presentation slides as a pdf and give the file name as “Presentation-ProjectID-YourID”. Make your presentation audio as an mp3 file and give the file name as “Audio-ProjectID-YourID”. Send me the pdf and the mp3 file by email with email subject as “Presentation-ProjectID-YourID”.
• If time permits, then we shall arrange presentation sessions where you will give the presentation in front of your classmates.

Bonus marks:

• I shall give up to 2 marks bonus if you prepare your report in LaTeX and another 2 marks bonus if you prepare your presentation in LaTeX-Beamer.