Assignment Paper

Write a final report summarizing the papers read and presenting your findings, and submit it by April 14 via
Brightspace. Only submit a single PDF file that is your report. The report should be 5-10 pages, singlespaced 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.
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.
Tips:
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