Project selection deadline: 03-November-2019, Sunday, 11:59pm.

Presentation submission deadline: 07 09-December-2019, Saturday Monday, 11:59pm

Project report submission deadline: 14-December-2019, Saturday, 11:59pm

General guideline:

• There are two types of projects: Theoretical and Programming. For either type, you shall have to write a report (10 marks) and prepare a presentation (10 marks: slides 5 marks + voice audio 5 marks ) .
• For a theoretical project, you shall choose a research paper from the list that I suggested below. You shall read the paper and understand the paper clearly. Then you shall write a report on the paper by your own language. Your report will contain the main idea in the paper, explanation of key techniques in the paper, additional examples, your idea on possible future work, etc. A typical structure of a report for a theoretical project should contain: Title, your ID and Name, Abstract, Introduction, Key techniques, Examples, Results, Possible future works, Conclusion, References.

Or, you can choose a survey topic, you shall have to survey important and/or recent results on that topic. The survey can be done from books, research papers, and similar materials. You then write your findings in a report and then present your findings by a presentation. You need to discuss different techniques used in the papers or texts from the books, comparison of their results, different ideas, etc in your report. You can also add your own idea on how to improve the existing results and any possible future development in that topic.

• 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". Or you can upload the file in the cloud and share me the link.

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". Or you can upload the files in the cloud and share me the link.

• 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.

Possible Topics:

• You shall have to choose only one topic, either a theoretical one or a programming one, from the list below. In one section, two students can not choose a same project. If you cannot decide which one to choose, contact me and I shall help you choosing a topic.
• You can choose a topic that is aligned to your interest in other Masters course and to your own research interest. For example, you may choose the topic of Huffamn coding if you find that this topic would be close to what you want to do in some other Masters course or in your future research.
• When you choose a topic, send me an email by mentioning your name, ID, and the Project ID from the lists below. If there are many students selecting a particular project, then I may distribute randomly among the students.
• Each topic below contains a tentative description of the project. Actual content of the project may little change once you do the project.
• Theoretical topics:
  • T01: Paper [pdf]
  • T02: Paper [pdf]
  • T03: Paper [pdf]
  • T04: Paper [pdf]
  • T05: Finding the closest pair of points: This algorithm is available in the textbook CLRS, Chapter 33.4. You have to write by your own language the description of the algorithm, divide-and-conquer technique, complexity analysis, pseudo code, etc. You shall have to also add some recent development or important variations of closest pair problem (search for them in the internet.)
  • T06: Survey Huffman coding: What is Huffman coding, importance, the greedy idea, algorithms and running time, variations, etc. Huffman coding is available in the textbook CLRS, Chapter 16.3. However, you shall have to look into other materials for recent development or important variations of Huffman coding as well (search for them in the internet.)
  • T07: Survey convex hull algorithms: Convex hull algorithms are available in the textbook, Chapter 33.3. It has two algorithms: Graham's scan and Jarvis march. But you shall have to add one more algorithms, that is Chan's algorithm.
  • T08: Survey of different search trees: Survey different search trees, such as binary search trees, AVL trees, red-black trees, and others. Compare their advantages and disadvantages, running times, etc. They are mostly available in the textbook CLRS.
  • T09: Survey of linear time sorting algorithms: There are special cases of sorting that runs in O(n) time. Survey those algorithms from the textbook CLRS Chapter 8.2, 8.3, 8.4. Compare their techniques, advantages, disadvantages, running time, etc. Add their major recent developments (search for them in the internet.)
  • T10: Selection in linear time: Selecting i-th smallest element from a set of n elements in O(n) time is an important problem in computer science. There are two algorithms for this problem in the text CLSR Chapter 9.2, 9.3. One of them is very similar to the randomized quicksort. You shall study these two algorithms and write a report on them, including their techniques, running time analysis, examples, comparison, etc. You shall also look into other materials for recent development or important variations of this problem (search for them in the internet.)
  • T11: Strassen’s algorithm for matrix multiplication: This is a very famous algorithm that follows divide-and-conquer strategy. A brute-force algorithm takes O(n^3) time, but the Strassen's one takes O(n^2.81) time. You shall study these two algorithms and write a report on them, including their techniques, running time analysis, examples, comparison, etc. These two algorithms are available in the text CLSR Chapter 4.2. You shall also look into other materials for recent development or important variations of this problem (search for them in the internet.)
• 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.
  • P01: 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).
  • P02: Merge sort vs 3-way merge sort: In 3-way merge sort, the elements will be divided into three equal parts and the merging will be done among the three parts. You shall have to program this 3-way merge sort and the merge sort that we saw in the lecture. Then you shall have to compare their actual running time (ms, sec, min, etc.). Run your program for small input (say, n=100) to very large input (say, n=100,000) gradually, take random values as your input array, plot/make table for your actual running time , and compare them against each other. There are codes available in the internet for 3-way merge sort. You can look into them, but finally you shall have to write code by yourself.
  • P03: Single pivot vs dual-pivot quicksort: Recently Yaroslavskiy has improved the quicksort algorithm further by using two pivots and by using good partition technique. It runs faster than the randomized quicksort that we have seen in the lecture. You shall implement randomized quicksort algorithm that we saw in our lecture and Yaroslavskiy's dual-pivot quicksort algorithm. Then compare their actual running time in (ms, sec, min, etc.). Run the two algorithms for small input (say, n=100) to very large input (say, n=100,000) gradually, take random values as your input array, plot/make table for your actual running time , and compare them against each other. Yaroslavskiy's algorithm can be found in many places in the internet, for example here, but finally you shall have to understand the code and write it by yourself.
  • P04: Binary search vs Skip list: Both binary search and skip list has O(nlog n) running time for searching. You shall implement both of these algorithms. Take a sorted array (you can take a random array and then use programming language's built-in sorting function, such as Java's Array.Sort() function, to sort the array.) Then create a skip list. For insert functions in the skip list, randomly take random (0,1) values for the new element. Do some random searching again and again by binary search and by skip list. Plot/write tables for comparing their actual running time in (ms, sec, min, etc.) and compare them each other. Increase your array size from small size (such as n=100) to bigger size (such as n=100,000).
  • P05: Merge sort vs heap sort: Implement merge sort and heap sort. You shall have to implement a heap by an array. You shall have to implement the necessary functions, such as heapify(), buildheap() and heapsort(). Then run your program for both algorithms for small input (say n=100) to large input (say n=100,000). Your output will be the sorted list. Plot/write tables for comparing the actual running time in (ms, sec, min, etc.) for merge sort and heap sort and compare them.
  • P06: Implement LCS by dynamic programming algorithm: Show the table, run your program for different X and Y of different lengths (small, say 3, 4, 5 to big, say 20, 30, 40), and find the LCS length, and find all LCSs by the program. Implement LCS by brute-force algorithm. Plot/write tables for comparing the actual running time in (ms, sec, min, etc.) of brute-force method and dynamic programming method.
  • P07: Merge sort vs Timsort: Timsort is a variation of merge sort, but runs faster than merge sort. Implement both merge sort and Timsort. Compare their actual running time (ms, sec, min, etc.). Run your program for small input (say, n=100) to very large input (say, n=100,000) gradually, take random values as your input array, plot/make table for your actual running time , and compare them against each other. There are codes available in the internet for Timsort. You can look into them, but finally you shall have to understand the code and write it by yourself.
  • P08: Linear time sorting algorithms: There are special cases of sorting that runs in O(n) time. Three of them are Counting sort, Radix sort and Bucket sort. They are available in the textbook CLRS Chapter 8.2, 8.3, 8.4. Implement these three sorting algorithms. Compare their actual running time (ms, sec, min, etc.). Run your program for small input (say, n=100) to very large input (say, n=100,000) gradually, take random values as your input array, plot/make table for your actual running time , and compare them against each other. You can discuss with the student taking the project T09.
  • P09: Implement brute-force and Strassen's algorithms for matrix multiplication: There are two simple algorithms for matrix multiplication: one is the brute-force algorithm and the other one is the Strassen's algorithms. They are available in the textbook CLRS Chapter 4.2. Implement these two algorithms. Compare their actual running time (ms, sec, min, etc.). Run your program for small input (say, n=10) to very large input (say, n=100) gradually, take random values as your input matrix, plot/make table for your actual running time , and compare them against each other. You can discuss with the student taking the project T11.
  • P10: Implement linear time selection: Selecting i-th smallest element from a set of n elements in O(n) time is an important problem in computer science. There are two algorithms for this problem in the text CLSR Chapter 9.2, 9.3. One of them is very similar to the randomized quicksort. You shall implement these two algorithms and compare them. Compare their actual running time (ms, sec, min, etc.). Run your program for small input (say, n=100) to very large input (say, n=100,000) gradually, take random values as your input array, plot/make table for your actual running time , and compare them against each other. You can discuss with the student taking the project T10.