Perform a literature survey on a problem related to data structures. You may sta
Perform a literature survey on a problem related to data structures. You may start with a recent paper and fully understand the results and approaches of this paper, and the previous results on which it builds. You can then find a few related papers to see what has been done on this topic. If you need advice on the topic you have found, especially if you are uncertain whether your topic is suitable, consult the instructor during his office hours or by email as early as possible.
Submit a two-page proposal of your project by March 9 via Brightspace. In this proposal, give a description of the problem you have chosen, summarize the results in at least two papers you have read on this problem, give a list of papers that you plan to further read for this problem (this does not have to be a complete list), and what you may possibly include in your survey. Typeset your proposal and submit a PDF file. The report should be 2-page long, single-spaced in 12-point font, with one inch margins all around. Do not exceed this page limit.
Write a final report summarizing the papers read and presenting your findings, and submit it by April 13 via Brightspace. Only submit a single PDF file that is your report. The report should be 5-10 pages, single-spaced in 12-point font, with one inch margins all around. The report should at least contain the following parts:
a. A clear statement of the problem and a short survey of known results.
b. A description, in your own words, of the main results you have found. Research publications do not always give the clearest explanation and proofs, and different papers might not be consistent in notation. You need make the papers easier to understand, for example, by finding a different way to present the theorems and proofs, simplifying notation, adding examples, and summarizing proof ideas.
c. Give your critique of the new ideas and results from the papers you read, e.g., how they compare with each other, which results are most useful, and what applications they have. Also state open problems, including any of your own, for future work in the area.
Make sure that the scope of the topic you choose is reasonable. If you need only read one paper for a problem you choose, then you have not done enough. On the other hand, if you have to read over 10 papers addressing the topic, you will probably need to narrow the field somehow, either by restricting the scope of the topic, or by only surveying the most recent or most relevant papers.
To find a topic on your own, there are some conferences that might provide good starting points. Conferences are typically two or three years ahead of journals in terms of the publication of most recent results, so try the following conferences. Note that only a fraction of the papers in most of the conferences listed below are related to this course. Conferences also vary in average quality; STOC, FOCS, SODA and SoCG are very high in quality. SODA may be the best source as it is not only strong but also focused on algorithms, while STOC and FOCS are very broad. SoCG is very good if you are looking for a topic on data structures in computational geometry. You are expected to be able to download papers in proceedings of these conferences if you connect to Internet from Dal campus.
ACM Symposium on Theory of Computing (STOC)
IEEE Symposium on Foundations of Computer Science (FOCS)
SIAM/ACM Annual Symposium on Discrete Algorithms (SODA)
Symposium on Computational Geometry (SoCG)
International Colloquium on Automata, Languages and Programming (ICALP), Proceedings in LNCS series
European Symposium on Algorithms (ESA), Proceedings in LNCS series
Symposium on Algorithms and Data Structures (WADS), Proceedings in LNCS series
Scandinavian Workshop on Algorithms and Complexity (SWAT), Proceedings in LNCS series
International Symposium on Algorithms and Computation (ISAAC), Proceedings in LNCS series
Some conference papers are more difficult to understand than other conference papers. Sometimes this is because not all details are given in the conference paper due to page limit of conference proceedings. In this case, you can try to locate the full version of the paper. The author’s website is a good place to start, as the author might have put the full version online. You can also check the author’s DBLP entry (Google author’s name and DBLP). Many of these papers have or will eventually have a journal version, perhaps with the same title. If the journal version is already published, try to retrieve it.
Proofread your report thoroughly and use a spell checker. The writing does affect your score.