#acl Claudius Korzen:read,write Patrick Brosi:read,write Axel Lehmann:read,write Natalie Prange:read,write All:read

This page describes how Bachelor's and Master's Projects and Theses work at the Chair for Algorithms and Data Structures.

A list of available, ongoing and completed projects and theses can be found [[ListOfProjectAndThesisTopics|here]].
{{{#!html
<!-- # ''Note: This is a new page, created on 07-02-2017. The old page, which was outdated and in a terrible format, can still be found [[BachelorAndMasterProjectsAndThesesOld|here]].'' -->
}}}

<<TableOfContents(2)>>

= Application for a project or thesis =
If you are interested in doing a project or theses with us, please '''carefully read this page first''' and then '''send an e-mail to the prospective supervisor with the following information:'''

 1. An acknowledgement that you have carefully read this whole page and the pages linked from it.
 2. A list of the courses you have already taken with us.
 3. A transcript of the grades of the courses you have taken so far.
 4. A very short description of your interests and your strengths (concerning work on a project/thesis).
 5. If you have an own project in mind (not necessary): a very short description of the goal and the scientific merit.

'''If you want to do your thesis with a company or another department''', please provide the following *additional* information in a concise format. Concise means that you should not write more than a paragraph for each of the items below and that your text should be concrete and understandable for a non-expert. The purpose of this information is so that we can check whether the planned work has sufficient scientific merit with respect to the field of computer science.

 a. What is the expected / aimed at outcome?
 a. How does your approach and the expected result differ from the state of the art? See the section on "Related Work" in our [[WritingGuidelines|guidelines]].
 a. How do you plan to evaluate your work. See the sections on "Theoretical Analysis" and "Empirical Analysis" in our [[WritingGuidelines|guidelines]].
 a. Supervision must be provided by the company or the other department and the supervisor should provide an evaluation report at the end of the thesis, in a format to be discussed with us.


= Deliverables of a Bachelor's or Master's PROJECT =

1. Fulfill the reproducibility requirements described in the next section

2. Create a project website:<<BR>>
2.1 The pages should be in a subfolder ''www'' in your folder in our SVN<<BR>>
2.2 There should be a single MD file in blog post format in ''www/content/post''<<BR>>
2.3 Any images or other files included in the MD file should be in ''www/static''<<BR>>
2.4 Note that this does not exclude interactive elements (e.g. via !JavaScript)<<BR>>
2.5 You can test the final appearance of the website as [[https://github.com/ad-freiburg/ad-blog|described here]]<<BR>>
2.6 You can look at [[http://ad-blog.informatik.uni-freiburg.de/|websites of previous projects]] in this format<<BR>> 
2.7 Here is a long list of [[https://ad.informatik.uni-freiburg.de/publikationen/bachelor_master_projekte|previous projects]] in a format predating the MD format<<BR>>

3. There is usually no presentation needed for a project

= Deliverables of a Bachelor's or Master's THESIS =


1. Fulfill the reproducibility requirements described in the next section

2. A written thesis<<BR>>
2.1 Upload a PDF of the thesis to our SVN, in a separate subfolder ''thesis''<<BR>>
2.2 In that same subfolder, also provide all the sources (tex files, bib files, figures, etc.)<<BR>>
2.3 Check our [[http://ad-wiki.informatik.uni-freiburg.de/teaching/WritingGuidelines|Guidelines for how to write a proper thesis]]<<BR>>
2.4 Here is a long list of [[https://ad.informatik.uni-freiburg.de/publikationen/bachelor_master_arbeiten|example theses]] which have already been completed at our chair

3. An oral presentation<<BR>>
3.1 The oral presentation takes place after you have officially submitted your thesis<<BR>>
3.2 Upload a PDF of the slides to our SVN, in a separate subfolder ''presentation''<<BR>>
3.3 In that same subfolder, also provide all the sources (if you use tex: like for the thesis, or the PPTX file)<<BR>>
3.4 The maximal duration of the presentation is 20 minutes (if you show a demo during your presentation, this time will also be counted towards the 20 minutes)<<BR>>
3.5 There is ample time for questions afterwards<<BR>>
3.6 By default, the presentation will be held online via Zoom. On request, the presentation can take place in Building 51, 2nd Floor, Room 024 (our "Küche")<<BR>>
3.7 You should be there 15 minutes earlier for setup and testing<<BR>>
3.8 Check our [[PresentationGuidelines|Guidelines for how to give a great presentation]]

4. There is no need for a website for a thesis


= Reproducibility =

For both projects and theses, '''your results must be easily reproducible'''. We have very specific requirements for this. They are explained in detail on our [[Reproducibility]] page, together with a simple working example.

Note the word "easily" in the previous paragraph. It is important that we can reproduce your results not just in principle, but easily. That is, there should be no need for lengthy explanations or expert knowledge, but once the software runs, everything should be "self-explanatory". From our perspective this should look like this:

1. We build the docker image (the comments at the end of the Dockerfile should say how)<<BR>>
2. We start a docker container (the comments at the end of the Dockerfile should say how)<<BR>>
3. There is information on the console on how to proceed further<<BR>>
4. Whatever components you provide from here on, they should be self-explanatory

Concerning Item 3, this will look different depending on your type of work. If your docker container starts a web service, there should at least be output on the console which provides the URL of the service. Further explanations on the service can then be provided on the web page. If your docker container starts an interactive shell, there should at least be instructions on how to proceed further. In the simplest case, this can be a message ''Type make all to get help on the available options of how to proceed further''.

Always keep in mind what is the point of all this. The point is that someone else, who is maybe not familiar with all or any of the details of your work, can see and reproduce what you have done easily, without assistance from you. And not just now, but also in six months or in a year or in five years. Also note that that "someone else" might be you in the future. It is amazing how quickly one forgets about ones own work, and you will be pleasantly surprised if you find that you can still run and understand everything months or years later.


= The first meeting =

In the first meeting with the supervisor, create a Google Doc where you copy and fill out the following template. The Google Doc must be named ''Firstname Lastname (<type of work>)'', where type of work is one of: Bachelorprojekt, Masterprojekt, Bachelorarbeit, Masterarbeit, Bachelorprojekt + Bachelorarbeit, Masterprojekt + Masterarbeit. The Google Doc should be shared with at least the following people: Student, Supervisor(s), Hannah Bast bast@informatik.uni-freiburg.de, Frank Dal-Ri dal-ri@informatik.uni-freiburg.de (our system administrator), Heike Hägle haegle@informatik.uni-freiburg.de (our secretary).

The document should contain a section for each meeting. As a minimum, each section header should contain the number of the meeting and the date and the time. The sections should be ordered in reverse chronologial order, that is, with the most recent meeting at the TOP.

The section of the first meeting should contain at least the following information:

{{{
Short working title: [this may change later]
Uni-Account: [initials + number]
Informatik-Account: [usually first seven letters of last name + the initial of first name]
Primary e-mail address:
SVN: [subdirectory in student-projects or student-theses, named firstname-lastname]
Special RAM requirements:
Special Disk space requirements:
Actual beginning of work:
Planned end of work:

Goal of the thesis: [succinct description in one paragraph]
First step: [see text below]
Deadline for the first step:
}}}

The first step should be something, where the whole problem is solved from beginning to end, but with a relatively simple approach (how simple is up to you). The more aspects are touched (even if just in a simplistic way) in this first step, the better. The resulting code should follow our [[Reproducibility|reproducibility guidelines]], just like for the final submission.

This first step is usually considerable work, but not very hard technically. It will give you a very good feeling for the challenges involved. Having completed this first steps, it usually becomes very clear (from the shortcomings of the simple approach) what the next steps should be.

We urge you to start your work right after the first meeting and we will be very unhappy if you don't. If you are not quite finished by the deadline, just drop us a line and ask for an extension. But never come to a follow-up meeting unprepared or with half-finished code, see the next section.

= Follow-up meetings =

It is very important that you come well-prepared to all follow-up meetings. In particular:

'''You must have working code and data ready''' that follows our [[Reproducibility|reproducibility guidelines]], just like for the final submission. In particular, all the relevant data should be there, either under ''/local'' or under ''/nfs/students''. We should have the opportunity to try out your code before the meeting, so please send it early enough.

'''Time-consuming precomputation should be done before the meeting'''. Many projects or theses involve some sort of preprocessing of (often large amounts of) data. For the intermediate meetings, we usually don't want to reproduce your precomputation, but we want to be able to reproduce whatever it is that can be done with the results of your precomputation. Store the results of your precomputation in your folder under ''/nfs/students'' or (if network latency is an issue) under ''/local/data''. The docker container should then mount this data via the ''-v'' option.

'''Don't expect us to lead the meeting''', it is your project / thesis and you should be the driving force. If you have specific problems or questions, you should prepare something (ideally in the form of code or a demo or an example), so that we can quickly understand what the problem is. It's usually not efficient if you start by telling us about all the details of the current status quo.

'''Always bring your laptop''', in case there is uncommitted code or data. It will also allow you to make small fixes right in the meeting.

= Forum for asking questions =

We have a dedicated forum for asking questions related to the technical aspects of our project or thesis: https://daphne.informatik.uni-freiburg.de/forum/viewforum.php?f=1082

It's similar to the forums we have for our courses. The forum is organized into several subforums, including: Programming, Docker, Datasets, Writing and Presenting, Miscellaneous.

All members from the Algorithms and Data Structures group are subscribed and will be happy to help whenever they can. Please write us an email if you have asked a question on the forum and haven't received an answer for several days. Other students (including you) can also subscribe to the forum and they are very welcome to answer questions, too. Like in our courses, many questions are relevant and interesting for other students, too.

In principle, feel free to ask any question on the forum. But for questions strongly related to your project and which probably only your supervisor can answer, better ask your supervisor directly.

= Grading scheme for the theses =

Your final grade for the thesis will be an average of four grades, one for each of the following four aspects:

 1. Quality of the conceptual/theoretical work. This includes aspects such as:
  a. How well were the ideas thought out / the details worked out
  a. How independent was the work
  a. How meaningful and interesting/useful were the results.
 1. Quality of the implementation work. This includes aspects such as:
  a. Does the Docker setup work (this is actually a hard requirement)
  a. How easily can we reproduce your work and your results
  a. Is the code well documented, did you adhere to a proper coding style, are there unit tests (these are all basic requirements in every course offered by our chair).
 1. Quality of the evaluation. This includes aspects such as:
  a. Is the experimental setup well described
  a. Is the selection of datasets reasonable (there should be at least two, with different characteristics)
  a. Is there a comparison with a reasonable baseline or competitor method
  a. Are the results correct
  a. Are the results properly discussed
 1. Quality of the write-up. This includes the aspects described in our [[WritingGuidelines|guidelines for writing a thesis]]



= List of available and ongoing projects and theses =
A list of available, ongoing and completed projects and theses can be found [[ListOfProjectAndThesisTopics|here]].

{{{#!html
<!-- # 
{{attachment:available.png|Available|align="top"}} = Available; {{attachment:ongoing.png|Ongoing|align="top"}} = Ongoing

Click on the titles for a more detailed description of the project, including background info, goals, and first steps. Note that for some topics, it can make sense if several people work on them concurrently. So ''ongoing'' does not necessarily mean, that the topic is no longer available.

{{attachment:ongoing.png|Ongoing|align="top"}} [[BachelorAndMasterProjectsAndTheses/GtfsMerger|Merging Overlapping GTFS Feeds (Bachelor project or thesis)]]: Many transportation companies publish their timetable data either directly as GTFS feeds or in formats that can be converted to GTFS. As soon as you have two GTFS feeds (two sets of timetable data) that cover either the same or adjacent areas, the problem of duplicate trips arises. You should develop a tool that merges two or more GTFS feeds and solves duplication / fragmentation issues. As a bachelor project or thesis. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/brosi|Patrick Brosi]].

{{attachment:ongoing.png|Ongoing|align="top"}} [[BachelorAndMasterProjectsAndTheses/HomepageAnalyzer|Extract and Analyze Scientist's Homepages (project and/or thesis)]]: Extract a large number of scientist's homepages from the [[http://commoncrawl.org|CommonCrawl]] web crawl. Extract the central information from these pages, including: name, profession, gender, affiliation. It will be relativel straightforward to get results of medium quality. The challenge is to achieve results of high quality. Machine learning will be crucial to achieve that. Exploring suitable methods is part of the challenge. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:ongoing.png|Ongoing|align="top"}} [[BachelorAndMasterProjectsAndTheses/TokenizationRepair|Tokenization Repair (project and/or thesis)]]: Interesting and well-defined problem, the solution of which is relevant in a variety of information retrieval scenarios. Simple rule-based solutions come to mind easily, but machine learning is key to get very good results. A background in machine learning, or a strong willingness to aquire one as part of the project/thesis, is therefore mandatory for this project. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:ongoing.png|Available|align="top"}} [[BachelorAndMasterProjectsAndTheses/SparqlTextUI|Combined SPARQL+Text search (project or thesis)]]: This is well-suited as a project (B.Sc. or M.Sc.) but also provides ample opportunity for continuation with a theses (B.Sc. or M.Sc). You should be fond of good user interfaces and have a good taste concerning layout and colors and such things. You should also like knowledge bases and big datasets and searching in them. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:available.png|Available|align="top"}} [[BachelorAndMasterProjectsAndTheses/SynonymFinder|Synonym Finder (project and/or theses)]]:
Find synonyms for all entities from Freebase or !WikiData or Wikipedia. Evaluate the quality and compare it to existing synonym databases like !CrossWikis.
Motivation: Most entities are known under several names. For example, a person like "Ellen !DeGeneres" is also known as just "Ellen". A profession like "Astronaut" is also known as "Spaceman", "Spacewoman" or "Cosmsonaut". Knowing these synonyms is key for many NLP (Natural Lanuage Processing) problems. Including complex problems like semantic search and question answering. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:ongoing.png|Ongoing|align="top"}} [[BachelorAndMasterProjectsAndTheses/OsmSearch|A Search Engine for OpenStreetMap Data (project and/or thesis)]]:
Implement the backend for a search engine for [[http://www.openstreetmap.org|OpenStreetMap]] data. Your server should load an arbitrary .osm file and answer (fuzzy) string searches over the entire dataset. This is a nice project to familiarize yourself with different index structures. Continuation as a thesis is possible. Preferably you have visited our lecture [[InformationRetrievalWS1617|Information Retrieval]], but this is not required. Code should be written in C++.
Supervised by [[https://ad.informatik.uni-freiburg.de/staff/brosi|Patrick Brosi]].

{{attachment:ongoing.png|Ongoing|align="top"}} [[BachelorAndMasterProjectsAndTheses/TabularInformationExtraction|Tabular Information Extraction (project and/or thesis)]]: Extract data from a knowledge base in a tabular format. This could for example be a list of cities with columns for the country they are in, population count and coordinates but really anything fitting in a table should be possible. Think of the typically hand crafted summary tables on Wikipedia.
This is well-suited as a project (B.Sc. or M.Sc.) with possible continuation as a thesis. You should be interested in knowledge bases, big datasets and searching in them. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/schnelle|Niklas Schnelle]].

{{attachment:ongoing.png|Available|align="top"}} [[BachelorAndMasterProjectsAndTheses/ConversationalAqqu|Conversational Aqqu (project and/or thesis)]]: In this project you will be working on an extension to our Question Answering system Aqqu. This extension will enable follow-up questions and thus a more natural interface. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/schnelle|Niklas Schnelle]].

{{attachment:available.png|Available|align="top"}} [[http://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/QAonWikiData|Question Anwering on WikiData]]: make our question answering work on [[https://www.wikidata.org|WikiData]]. !WikiData is currently growing fast and will become the new Freebase. It's an exciting dataset. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:available.png|Available|align="top"}} [[http://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/Chatbot|A Simple chat bot]]: Build a simple chat bot using deep learning. For a recent example of such a chatbot, see [[https://www.washingtonpost.com/news/to-your-health/wp/2017/12/03/the-woebot-will-see-you-now-the-rise-of-chatbot-therapy|Woebot]]. This topic gives you a lot of freedom concerning the outcome, but it is also free in the sense that you have to research yourself what is out there already and what can realistically be achieved in six months yourself. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:available.png|Available|align="top"}} [[http://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/QAErrorCorrection|Error Correction for Question Answering]]: Design and build a system that accepts a (relatively simple) question in natural language and automatically corrects typos etc. This should be realized with a character-based language model learned using deep learning (e.g., with an RNN). Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:ongoing.png|Available|align="top"}} [[http://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/ScientistFinder|Crawling and Analysis of Scientist Homepages]]: Design and build a system that crawls as many university pages and finds as many person mentions as possible and creates a neat knowledge base from this information (Name of Scientist, Affiliation, Gender, Title). In previous work, we tried extracting this information from the CommonCrawl archive, but that turned out to be much too incomplete and unreliable. This is a challenging problem with large practical value. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/schnelle|Niklas Schnelle]].

{{attachment:available.png|Available|align="top"}} [[http://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/BitcoinTradingApp|Bitcoin trading app]] Design and implement a reasonably clever (not to reckless and not to conservative) algorithm for trading bitcoins. Evaluate on historical data and implement an API and a web app to monitor on live data. Take into account all the actual costs incurred (like taxes and fees). Analyse the return of investment that can be reasonably expected. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:available.png|Available|align="top"}} [[http://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/ClueWebEntityRecognition|Entity Recognition on a Web Corpus]] Design and implement a named-entity recognizer for a web-size corpus. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:available.png|Available|align="top"}} [[http://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/ClueWebContextDecomposition|Context Decomposition of a Web Corpus]] Decompose the sentences of a given web-size corpus into their semantic components, using fancy technology developed in our group. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:ongoing.png|Ongoing|align="top"}}  [[http://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/RiverMap|River Maps]] The goal of this project is to use our tool [[http://loom.cs.uni-freiburg.de|LOOM]] to render maps of rivers from OSM data. Each river segment should consist of all rivers that contributed to this river so far (for example, beginning at Mannheim, the Neckar should be part of the segment that makes up the Rhine). Think of a single river as a single subway line starting at the source of that river, and the Rhine, for example, as dozens of small subway lines next to each other. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/brosi|Patrick Brosi]].

{{attachment:available.png|Available|align="top"}} [[http://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/MailSearch|Mail Search]] The goal of this project is a fast and efficient search in very large mail archives. The subtasks are: (1) Write an efficient parser that reads one or files in MBOX format and produces a CSV file with one line per mail and columns for the various structured and unstructured parts of an email (from, to, subject, date, body, ...); (2) take proper care of encoding issues, which are a major issue when dealing with a large number of emails; (3) setup an instance of !CompleteSearch for the data from the CSV file; (4) provide a simple and effective search unterface using the instance from 3 as a backend. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/bast|Hannah Bast]].

{{attachment:ongoing.png|Ongoing|align="top"}}[[https://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/WordExtraction|Extracting Words from Text Documents with Complex Layouts (bachelor thesis)]] Design and implement a (learning-based) system for extracting words from layout-based text documents (e.g., PDF documents), which is a surprisingly difficult (but not super-hard) task. The reason is that the text is typically only provided character-wise (and not word-wise) so that word boundaries must be derived from e.g., analyzing the spacings between the characters. Another challenge is that the layout of a text document can be arbitrarily complex, with text arranged in multiple columns and different alignments so that special care is required to not mix up text from different columns. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/korzen|Claudius Korzen]].

{{attachment:ongoing.png|Ongoing|align="top"}}[[https://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/SpecialCharactersExtraction|Extracting Special Characters from Layout-Based Text Documents (bachelor thesis)]] Design and implement a (learning-based) system for extracting ''ligatures'' (like fi or ffi) and ''characters with diacritics'' (like á and è) from layout-based text documents (e.g., PDF documents). The challenge here is that such characters can be ''drawn'' into the text, in which case they need to be recognized by analyzing their shapes. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/korzen|Claudius Korzen]].

{{attachment:ongoing.png|Ongoing|align="top"}}[[https://ad-wiki.informatik.uni-freiburg.de/teaching/BachelorAndMasterProjectsAndTheses/MergingHyphenatedWords|Merging Hyphenated Words in Layout-Based Text Documents (project)]] Design and implement a (learning-based) system for merging hyphenated words in layout-based text documents (e.g., PDF documents). The challenge here is to decide, whether or not the hyphen between the two parts of a hyphenated word needs to be retained (because of a compound word) after merging the parts. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/korzen|Claudius Korzen]].

{{attachment:available.png|Available|align="top"}}  [[BachelorAndMasterProjectsAndTheses/GtfsBrowser|GTFS Browser Web App (Bachelor project or thesis)]]: Develop a web-application that can be used to analyze huge GTFS datasets. There are already some tools available (for example, [[https://github.com/google/transitfeed/wiki/ScheduleViewer|ScheduleViewer]]) but they all feel and look quite clumsy, are incredible slow and cannot handle large datasets. Supervised by [[https://ad.informatik.uni-freiburg.de/staff/brosi|Patrick Brosi]].
-->
}}}
{{{#!html
<!--
= Completed projects and theses =
[[http://ad.informatik.uni-freiburg.de/publications/bachelor_master_theses|List of completed B.Sc. and M.Sc. theses]] (each with the written thesis and presentation)

[[http://ad.informatik.uni-freiburg.de/publications/bachelor_master_projects|List of completed B.Sc. and M.Sc. projects]] (each with a project website)
-->
}}}