Project selection deadline:

• 14-11-2017 (Tuesday) during the lecture. The list is now complete. I suggest you to choose a project from the list below.

Project report submission deadline:

• 21-12-2017: Thursday, 12:00 midnight. Submit pdf by email.

Presentation Schedule:

• Boys:
  • 10-12-2017 (week 13): Sunday
    • 6:15-6:35: P4(1)
    • 6:35-6:55: T2(2)
    • 6:55-7:15: P1(3)
  • 12-12-2017 (week 13): Tuesday
    • 6:15-6:35: P2(4)
    • 6:35-6:55: T5(5)
    • 6:55-7:15: T3(6)
  • 17-12-2017 (week 14): Sunday
    • 6:15-6:35: T7(7)
• Girls: Submit your presentation slides in pdf by email 24 hours before your presentation time.
  • 10-12-2017 (week 13): Sunday
    • 4:30-4:50: T2(1)
    • 4:50-5:10: T5(2)
    • 5:10-5:30: P2(3)
  • 12-12-2017 (week 13): Tuesday
    • 4:30-4:50: P3(4)
    • 4:50-5:10: T6(5)
    • 5:10-5:30: T1(6)
  • 17-12-2017 (week 14): Sunday
    • 4:30-4:50: T3(7)
    • 4:50-5:10: P5(8)
    • 5:10-5:30: P4(9)
  • 19-12-2017 (week 14): Tuesday
    • 4:30-4:50: P1(10)
    • 4:50-5:10: P6(11)

General guideline:

• There are two types of projects: (1) Theoretical and (2) Programming. For both types, you shall have to write a report and give a presentation.
• For a theoretical project, 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, comparison of their results, different ideas, etc in your report. You can also add your own idea on how to improve the existing results or any possible future development in that topic.
• For a programming project, you shall have to implement the programming problem. Then you shall have to write your pseudo code, data structures used in your program, your findings, result comparison, and the program code itself in a report and then present it in a presentation. You can use any programming language you feel comfortable. However, it is preferable that you use C/C++/Java/C# or similar high level language. You can also add your idea on how to improve the existing results or any future development in that topic. You should write the programming code yourself. Copying from other sources will incur penalties.

Report writing (10 marks):

• A report should be about 5-6 full pages, in English, and in 10 size fonts. For a programming project, the programming code can go to an appendix in extra pages.
• Theoretical Project: A typical structure of a report for a theoretical project should contain: Title, your ID and Name, Abstract, Introduction, Findings, Comparisons, Possible future work, Conclusion, References.
• Programming Project: 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 the running time and other data, Possible future work, Conclusion, References, Program code.

Presentation (10 marks):

• A presentation should be of 10-15 minutes and in English. Then about 5 minutes for questions and answers.
• For a theoretical project, I may ask you to show the papers or materials you have used in your survey.
• For a programming project, I may ask you to change the code to modify your program.

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. If you cannot decide which one to choose, contact me and I shall help you choosing a topic. When you choose a topic, send me an email by mentioning your name, ID, and the topic number from the lists below. If there are many students selecting a particular project, then I may distribute randomly among the students. I shall declare a project selection deadline by which you shall send your choice.
• Each topic below contains a tentative description of the project. Actual content of the project may little change once you go through the project.
• Theoretical topics:
  • T1: Energy efficient algorithms. This is a very new concept. Start with this paper [pdf] and add more papers, if necessary. Some slides are available in the internet. You can look into those slides, but finally you shall have to make your own presentation.
  • T2: Survey of different search trees, such as binary search trees, AVL trees, red-black trees, and others.
  • T3: Online algorithms. What are online algorithms, importance, performance measure, examples, etc. Online algorithms are similar to approximation algorithms in Lecture 13.
  • T4: Quantum algorithms. This is a new concept. What are quantum algorithms, importance, how the running time/performance are measured, example of quantum algorithms, etc. Your project should focus on algorithms and theoretical topics.
  • T5: Huffman coding. What is Huffman coding, importance, the greedy idea, algorithms and running time, variations, etc. Huffman coding is available in the textbook CLSR, Chapter 16. However, you shall have to look into other materials as well.
  • T6: 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.
  • T7: Genome sorting algorithms: These are one of many bioinformatics algorithms. Sorting algorithms here are different than what we saw in merge sort or quick sort. There are several variations of genome sorting algorithms, but you will cover only sorting by reversals. If you are interested in the recent and emerging topic of bioinformatics, then this project is suitable for you.
  • T8: 3-way merge sort. This project is the theoretical version of the programming project P3 below. Two students taking these two projects can work/discuss together. In merge sort, we divide the elements into two equal parts and merge the two sorted parts together. In 3-way merge sort, the elements will be divided into three equal parts and the merging will be done among the three parts. In this project you shall have to write pseudo code, write and solve recurrence relation of 3-way merge sort, and compare it with merge sort. You should also explain why this strategy is not better than the merge sort.
• Programming topics:
  • P1: Implement two versions of quick sort: pivot as the first element and randomized. Run both of your algorithms and compare their time. Run your program for small input (say, n=10) to very high (say, n=100,000,000), take random values as your input array, plot your running time (real time, not the number of steps), and compare them against each other and also against the curve of n log n.
  • P2: 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), find the LCS length, and find all LCSs by the program. Implement LCS by brute-force algorithm and compare the result, both LCS and running time (real time, not the number of steps), with the results of dynamic programming.
  • P3: Implement 3-way merge sort. This project is the programming version of the theoretical project T8 above. Two students taking these two projects can work/discuss together. In merge sort, we divide the elements into two equal parts and merge the two sorted parts together. 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 running time. Run your program for small input (say, n=10) to very large input (say, n=100,000,000), take random values as your input array, plot your running time (real time, not the number of steps), and compare them against each other. There are codes available in the internet. You can look into them, but finally you shall have to write code yourself.
  • P4: Implement heap sort. You shall have to implement heap by an array. You shall have to implement the necessary functions, such as heapify(), buildheap() and heapsort(). Then run your program for small input to large input. Your output will be the sorted list. You can show your output by writing the array again and again with delays. You can get some bonus if you can show the output by drawing the heap tree (for smaller inputs).
  • P5: Implement Skip list. Implement search, insert, and delete. Run these functions again and again and measure their running time. Display your skip list as shown in the slide. For insert functions, randomly take random (0,1) values for the new element. Plot your running time and compare against the log n curve.
  • P6: Implement disjoint set data structures. Implement makeset(x), findset(x) and union (x, y). Implement union() by worst case technique (that means, join the set of y after the set of x) and by improved technique (join smaller set to the end of larger set). Run makeset() function for random inputs many times to make the data structures big. Then perform union() many times by the two techniques, measure the time and plot them. Compare the time against the curse of n^2 and n log n.
• After you select a topic:
  • After you select a topic, you are welcome to contact me for any guidance. I can help you finding materials, which topics to be covered and which not, etc.