Course Information

About this course

The purpose of this course is to let you delve deep into some topic you are interested in within the field of theoretical computer science.  This is done by doing a small research project under the guidance of a faculty member.

Since the course is done individually, it has no scheduled activities.  As such, the course can be started and taken at any time during the year.

Scope and Topics

• The project can in principle be within any sub-field of theoretical computer science Links to an external site. (e.g. algorithms, complexity theory, cryptography, or formal methods) as long as there is some available faculty member with expertise in the subject.
• The project should be grounded in the state of the art of current research in its area.  In general, the 7.5 credit scope of the course is not sufficiently large to solve any open research problems, and this is not expected of you.  Rather, depending on the difficulty of the research area, suitable objectives may be:
  • To produce a survey of a specific research problem or subarea (in particular in areas where the state of the art is scattered across many papers and there is a lack of overview).
  • To understand and produce an alternative exposition of some breakthrough result (in particular if the original paper is difficult to read).
  • Empirical evaluation of different state-of-the-art algorithms for a problem.
  • Suggest a new formal model / problem / algorithm and prove some properties about it.
• Since the course is the culmination of the Theoretical Computer Science track of the Master Program in Computer Science, it is expected that the project builds upon and dives deeper into material that you learned in the courses of the track:
  
  • DD2372 Automata and Languages
  • DD2440 Advanced Algorithms
  • DD2442 Seminars on Theoretical Computer Science
  • DD2443 Parallel and Distributed Computing
  • DD2445 Complexity Theory
  • DD2448 Foundations of Cryptography
  • DD2452 Formal Methods
  • DD2457 Program Semantics and Analysis
  • DD2459 Software Reliability
  • DD2460 Software Safety and Security

Getting started

1. The first step is to find a supervisor and a project.
   1. Think about what topics in theoretical computer science you are most interested in and would like to immerse yourself in.  Maybe you only have a broad idea (e.g. "I would like to go more in-depth in formal methods"), or maybe you have a more specific idea (e.g. "I would like to study algorithms for matrix multiplication"), or something in between.
   2. Identify which faculty member/members work on those topics and could be a suitable supervisor. Perhaps you already know who they are based on having taken courses with them, but if you are unsure and would like guidance, contact Per Austrin who can help put you in contact with a supervisor.
   3. Discuss possible projects with the supervisor and/or Per Austrin.  If you already have something very specific in mind this is more of a discussion about whether your idea is feasible, and if you more have a broad idea about what types of topics you would like to work on, the supervisor and/or Per will try to help you narrow it down to a specific project.
2. Once you have a supervisor and concrete project, write a short project plan.
   1. The project plan should briefly outline what you plan to do in the project, have a few references to the primary earlier work that you are basing the project off, indicate what the deliverables of the project will be (see FAQ below), and have a tentative timeline.  It does not have to be more than a page long.
   2. Send the project plan to Per Austrin for approval.

Written Report

• The report should be written in the style of a research paper in the field.
• The intended audience of the written report are your fellow students on the theoretical computer science track.
• Example reports:
  Here are some examples of reports from good projects from earlier years.
  • Simple Parallel Minimum Cuts in Near-Linear Work and Low Depth Download Simple Parallel Minimum Cuts in Near-Linear Work and Low Depth by Andrés López Martı́nez
  • The Ring Learning with Errors Problem Download The Ring Learning with Errors Problem by David Balbás Gutiérrez
  • Unified Collections Download Unified Collections by Anders Ågren Thuné

FAQ

• Q: What should the deliverables of the project be?
  A: the default is that you produce a written report documenting your project (written in the style of a scientific paper) and give a short presentation.
• Q: What determines my grade in the course?
  A: The grade is decided by your written report and oral presentation, with the written report being the main deciding factor.  Within the written report, the technical contents and overall writing quality weigh equally heavy.
• Q: Is there any deadline for when my project needs to be finished?
  A: From the point of view of the course there is no strict deadline. However you may of course be subject to external deadlines such as not being allowed to start your Master's Thesis until you have finished this course.