|
Size: 8496
Comment:
|
Size: 10575
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 4: | Line 4: |
| = Guidelines for M.Sc. and B.Sc. theses at the Chair of Algorithms and Data Structures = | = Guidelines for writing a M.Sc. or B.Sc. theses at the Chair of Algorithms and Data Structures = |
| Line 10: | Line 10: |
| All M.Sc. or B.Sc. theses primarily supervised so far by our chair can be found under http://ad.informatik.uni-freiburg.de/publikationen/bachelor_master_arbeiten . The list is currently (01Apr14) still quite incomplete, but that will hopefully change within a week from now. | All M.Sc. or B.Sc. theses primarily supervised so far by our chair can be found under http://ad.informatik.uni-freiburg.de/publikationen/bachelor_master_arbeiten . |
| Line 22: | Line 22: |
| An abstract should be self-contained and understandable also to a non-expert. ''Think of it as the shortest way to say what you did in one paragraph.'' As a minimum, it should clarify the problem dealt with in the thesis, and the main results that were obtained. Optionally, you can add a sentence or two about the underlying techniques and how the thesis advances the state of the art. | An abstract should be self-contained and understandable to a non-expert. ''Think of it as the shortest way to say what you did in one paragraph.'' As a minimum, it should clarify the problem dealt with in the thesis, and the main results that were obtained. If space permits, add a sentence or two about the underlying techniques and how the thesis advances the state of the art. |
| Line 30: | Line 30: |
| Most probably, other researchers have worked on the problem of your thesis, or highly related problem, before. ''Your thesis should include a section which summarizes the most relevant of these works.'' Typically this is Section 2, right after the introduction. For each of these works, it should be explained in a nutshell what they do, what they achieve, and how this differs from what you do in your thesis. This should be understandable without the need to actually read the paper. Think of each description as the shortest way to say this in one paragraph. When there is a lot of work about a particular topic / problem, it is ok to focus on the most recent / most advanced approaches. | Most probably, other researchers have worked on the problem of your thesis, or a strongly related problem, before. ''Your thesis should include a section which summarizes the most relevant of these works.'' Typically this is Section 2, right after the introduction. For each of these works, it should be explained in a nutshell what they do, what they achieve, and how this differs from what you do in your thesis. This should be understandable without the need to actually read the papers referred to. For each related work, think of the description as the shortest way to say this in one paragraph. When there is a lot of work about a particular topic / problem, it is ok to focus on the most recent / most advanced approaches. |
| Line 34: | Line 34: |
| Most probably, your work will make use of some algorithms and data structures. Either your own, or such from previous work, or a combination of the two. ''In any case, provide information about the basic complexity of your algorithms, in particular their running time.'' Do this also if the the statement appears straightforward to you. For example, your algorithm may obviously be linear in the size of the input data. Anyway, say it! | Most probably, your work will make use of some algorithms and data structures. Either your own, or such from previous work, or a combination of the two. ''In any case, provide information about the basic complexity of your algorithms, in particular their running time.'' Do this also if the the statement appears straightforward to you. For example, the running time of one of your algorithms may obviously be linear in the size of the input data. In any case, say it and provide an argument / proof for it! |
| Line 38: | Line 38: |
| Most probably, your work involves the implementation of an algorithm or data structure, or of a whole system. ''Whatever it is, your implementation should be thoroughly evaluated.'' The kind of evaluation depends on the nature of your problem. What is almost always of interest is running time = how long does it take to do whatever your code does. If there is a pre-processing phase, this should also be evaluated. If a lot of disk space and/or memory is consumed, that should also be evaluated. If there are existing approaches which can be used to solve your problem, compare to the best one of these approaches. If there is no solution yet for your problem, think of a simple baseline algorithm (= the straightforward solution) and compare to that. Do your evaluation on at least three different data sets of different kinds and sizes. | Most probably, your work involves the implementation of an algorithm or data structure, or of a whole system. ''Whatever it is, your implementation should be thoroughly evaluated.'' The kind of evaluation depends on the nature of your problem. If the focus is on results of a particular ''quality'', that should be evaluated. If the focus is on ''efficiency'', running time and (if relevant) space consumption should be evaluated. Even if the focus is on quality, efficiency should be evaluated, too. One always wants to know the running time of a procedure and (if relevant) its space consumption. If there is a pre-processing phase, this should be evaluated separately. If the pre-processing consumes a lot of intermediate disk space or memory, that should also be evaluated. Think about the evaluation from the perspective of someone who wants to use your software in practice. What is it that you would want to know then? Typically, there are other approaches which can be used (either directly or with small modifications / adjustments) to solve your problem. As a minimum, compare to the best one of these approaches. If there is a variety of principally different approaches, pick the best one for each principle. If there is no solution yet for your problem, think of a simple baseline algorithm (= the straightforward solution) and compare to that. Sometimes there are two or even three simple baseline algorithms. Do your evaluation on at least three different data sets of different kinds and sizes. If the amount of work needed per data set is very large, it is OK to use only two data sets. |
| Line 42: | Line 44: |
| Most probably, your work will leave various open ends. Make a list of what could be done next to improve on what you did. For each item, give a short description of the possible improvement + an idea for how, in principle, it could be achieved. Also give an estimate for the necessary time to realize that improvement (hours, days, weeks, months). Order your list by importance / significance = the thing that should be improved next / gives the biggest improvement should come first. | Most probably, your work will leave various open ends. Make a list of what could be done next to improve on what you did. For each item, give a short description of the possible improvement + an idea for how, in principle, it could be achieved. Also give an estimate for the necessary time to realize that improvement (hours, days, weeks, months). Order your list by importance / significance. That is, the thing that should be improved next / gives the biggest improvement should come first. |
| Line 52: | Line 54: |
| A typical question is: how much should I write? My typical answer is: write as much as is necessary to understand what you did, how you were doing it, ... all the aspects listed in Section "Content" above. No more, no less. The thesis should be self-contained. That is, for someone with general basic knowledge in computer science, it should not be necessary to read anything else than your thesis in order to understand your descriptions / explanations on the named aspects. | A typical question is: how much should I write? My typical answer is: write as much as is necessary to understand what you did, how you were doing it, and all the aspects listed in Section "Content" above. No more, no less. The thesis should be self-contained. That is, for someone with general basic knowledge in computer science, it should not be necessary to read anything else than your thesis in order to understand all the main aspects of your thesis. |
| Line 58: | Line 60: |
| Structure is also very important. A good way to start your write-up is to write down all the section and subsection headers. The names should be carefully chosen, and they should be consistent in their style. | Structure is also very important. A good way to start your write-up is to write down all the section and subsection headers. The names of the headers should be carefully chosen, and they should be consistent in their style. |
| Line 60: | Line 62: |
| Every section and every subsection should start with a small introduction that tells the reader what comes next. The following four sentences are an example. In this section, we will give a high-level description of the algorithm. The algorithm has two phases. In the first phase, ... (Section 3.1). In the second phase, ... (3.2). Note again, how simple the sentences are. | Every section and every subsection should start with a small introduction that tells the reader what comes next. The following four sentences are an example: "In this section, we will give a high-level description of the algorithm. The algorithm has two phases. In the first phase, ... (Section 3.1). In the second phase, ... (3.2)." Again, note how simple the sentences are. |
| Line 62: | Line 64: |
| Consistency is also very important. If you use a particular word to describe something, stick to that word. Variation is maybe nice in a novel. But in scientific work, every single inconsistency makes it harder for the reader. It is also fine to repeat the same word again in the next sentences. In scientific work, it is even good style. | Consistency is also very important. If you use a particular word to describe something, stick to that word. Variation is maybe nice in a novel. But in scientific work, every single inconsistency makes it harder for the reader. It is also fine to repeat the same word again in the next sentences. In scientific work, it is even good style. For example, in the previous paragraph, it it better to write "The algorithm has two phases" than just "It has two phases". Visual consistency is also important. If you use different fonts, use them with a consistent meaning. If you have a variety of tables, make sure they have a consistent look. |
| Line 68: | Line 70: |
| === Typical errors === Please avoid at least the following errors. ''Hyphens in noun phrases'': multi-word noun phrases have a hyphen, ''only'' if you use them as an adjective. Here is an example. (1) This problem has a large scale. (2) This is a large-scale problem. Putting a hyphen in (1) would be a mistake. Not putting the hyphen in (2) would be a mistake. Understand the purpose of the hyphen. It say what belongs together. In sentence (2), without the hyphen, it would not be clear whether it is a "scale problem" that is large, or whether the problem has a "large scale". ''Commas after introductory clauses'': there is always a comma after clauses like "However", "In this section", "Therefore", ... TODO: what else. === Spelling === As a final step, ALWAYS run a spell checker over your write-up. It's very embarrassing indeed if your write-up contains mistakes that any spell checker would have found. TODO: spell-check this web page. |
|
| Line 70: | Line 89: |
| It's certainly possible to do a master's thesis with a topic of your own choice. | It is possible to do a master's thesis with a topic of your own choice. |
| Line 72: | Line 91: |
| In both of these cases, it is particular important that the work adheres to the scientific standards sketched above. | In both of these cases, it is particularly important that the work adheres to the scientific standards sketched above. |
| Line 74: | Line 93: |
| If you plan such a thesis and want Prof. Bast to be your reviewer, please send her an email with succinct answers to the following quesions: | If you plan such a thesis and want Prof. Bast to be your reviewer, please send her an email with succinct answers to the following questions: |
| Line 78: | Line 97: |
| 2. How does your approach and the expected result differ from the state of the art? See Section Contents -> Related Work above. | 2. How does your approach and the expected result differ from the state of the art? See the section on "Related Work" above. |
| Line 80: | Line 99: |
| 3. How do you plan to evaluate your work. See Section Contents -> Theoretical Analyis / Empirical Analysis above. | 3. How do you plan to evaluate your work. See the sections on "Theoretical Analysis" and "Empirical Analysis" above. |
| Line 82: | Line 101: |
| Please don't send pages of text. Please be specific though. The answers should make it possible to assess what your thesis is about and whether it fulfills our standards. No more, no less. | Please don't send pages full of text. Be brief and specific. Your answers to the three questions above should make it possible to quickly assess what your thesis is about and whether it fulfills our standards. No more, no less. |
Guidelines for writing a M.Sc. or B.Sc. theses at the Chair of Algorithms and Data Structures
Contents
Examples
All M.Sc. or B.Sc. theses primarily supervised so far by our chair can be found under http://ad.informatik.uni-freiburg.de/publikationen/bachelor_master_arbeiten .
Content
M.Sc. and B.Sc. theses are supposed to be pieces of scientific works. Here are some guidelines to some minimal standards required of any scientific work so that it deserves that name.
Title
As a minimum, a title should be informative. Think of it as the shortest way to say what you did in one short sentence. A secondary criterion is that it is catchy. This is not necessary, however, and sometimes hard to achieve. Also a catchy title should be informative. If you build a system, a typical title is the name of the system, followed by a colon, followed by a short description of what the system does.
Abstract
An abstract should be self-contained and understandable to a non-expert. Think of it as the shortest way to say what you did in one paragraph. As a minimum, it should clarify the problem dealt with in the thesis, and the main results that were obtained. If space permits, add a sentence or two about the underlying techniques and how the thesis advances the state of the art.
Introduction
An introduction should be self-contained and understandable to a non-expert. Think of it as the shortest way to say what you did in a couple of pages. As a minimum, it should clarify the problem dealt with, the motivation for dealing with that problem, the main results, the main challenge and the line of attack used to overcome it, and how it advances the state of the art. In the abstract, you have only one or two sentences (if any) for each of these aspects. In the introduction, you have more space. For the problem statement, it is almost always a good idea to provide a figure or screenshot with a (carefully chosen) example.
Related Work
Most probably, other researchers have worked on the problem of your thesis, or a strongly related problem, before. Your thesis should include a section which summarizes the most relevant of these works. Typically this is Section 2, right after the introduction. For each of these works, it should be explained in a nutshell what they do, what they achieve, and how this differs from what you do in your thesis. This should be understandable without the need to actually read the papers referred to. For each related work, think of the description as the shortest way to say this in one paragraph. When there is a lot of work about a particular topic / problem, it is ok to focus on the most recent / most advanced approaches.
Theoretical analysis
Most probably, your work will make use of some algorithms and data structures. Either your own, or such from previous work, or a combination of the two. In any case, provide information about the basic complexity of your algorithms, in particular their running time. Do this also if the the statement appears straightforward to you. For example, the running time of one of your algorithms may obviously be linear in the size of the input data. In any case, say it and provide an argument / proof for it!
Empirical analysis
Most probably, your work involves the implementation of an algorithm or data structure, or of a whole system. Whatever it is, your implementation should be thoroughly evaluated. The kind of evaluation depends on the nature of your problem. If the focus is on results of a particular quality, that should be evaluated. If the focus is on efficiency, running time and (if relevant) space consumption should be evaluated. Even if the focus is on quality, efficiency should be evaluated, too. One always wants to know the running time of a procedure and (if relevant) its space consumption. If there is a pre-processing phase, this should be evaluated separately. If the pre-processing consumes a lot of intermediate disk space or memory, that should also be evaluated. Think about the evaluation from the perspective of someone who wants to use your software in practice. What is it that you would want to know then?
Typically, there are other approaches which can be used (either directly or with small modifications / adjustments) to solve your problem. As a minimum, compare to the best one of these approaches. If there is a variety of principally different approaches, pick the best one for each principle. If there is no solution yet for your problem, think of a simple baseline algorithm (= the straightforward solution) and compare to that. Sometimes there are two or even three simple baseline algorithms. Do your evaluation on at least three different data sets of different kinds and sizes. If the amount of work needed per data set is very large, it is OK to use only two data sets.
Future work
Most probably, your work will leave various open ends. Make a list of what could be done next to improve on what you did. For each item, give a short description of the possible improvement + an idea for how, in principle, it could be achieved. Also give an estimate for the necessary time to realize that improvement (hours, days, weeks, months). Order your list by importance / significance. That is, the thing that should be improved next / gives the biggest improvement should come first.
Writeup
English or German
You can write your thesis in German or in English. If you write it in English, more people will read it. Plus, it's a great opportunity to practice writing in English. You will almost certainly need that ability in your later job, so why not start now. If you don't want anyone to read your thesis, write it in French.
Scope
A typical question is: how much should I write? My typical answer is: write as much as is necessary to understand what you did, how you were doing it, and all the aspects listed in Section "Content" above. No more, no less. The thesis should be self-contained. That is, for someone with general basic knowledge in computer science, it should not be necessary to read anything else than your thesis in order to understand all the main aspects of your thesis.
Style
The most important general rule is: write simple sentences. A simple sentence has the form: subject, predicate, object. If your sentences has two or more verbs, consider splitting it into two simpler sentences. It is rarely necessary to have sentences with more than two verbs. The sentences in this paragraph are a good example for this writing style. Note that this writing style may not be the best when writing a novel. But it is perfect for scientific text, because it is easy to read and follow.
Structure is also very important. A good way to start your write-up is to write down all the section and subsection headers. The names of the headers should be carefully chosen, and they should be consistent in their style.
Every section and every subsection should start with a small introduction that tells the reader what comes next. The following four sentences are an example: "In this section, we will give a high-level description of the algorithm. The algorithm has two phases. In the first phase, ... (Section 3.1). In the second phase, ... (3.2)." Again, note how simple the sentences are.
Consistency is also very important. If you use a particular word to describe something, stick to that word. Variation is maybe nice in a novel. But in scientific work, every single inconsistency makes it harder for the reader. It is also fine to repeat the same word again in the next sentences. In scientific work, it is even good style. For example, in the previous paragraph, it it better to write "The algorithm has two phases" than just "It has two phases". Visual consistency is also important. If you use different fonts, use them with a consistent meaning. If you have a variety of tables, make sure they have a consistent look.
Bibliography
Make sure that the entries in your bibliography have a consistent style. That is, abbreviate all conferences in the same way or use the full names for all, but do not mix the two styles. Same for author names. Same for capitalization of titles. Same for page numbers. It makes a very careless and untidy impression, if the bibliography entries are inconsistent in their style.
Typical errors
Please avoid at least the following errors.
Hyphens in noun phrases: multi-word noun phrases have a hyphen, only if you use them as an adjective. Here is an example. (1) This problem has a large scale. (2) This is a large-scale problem. Putting a hyphen in (1) would be a mistake. Not putting the hyphen in (2) would be a mistake. Understand the purpose of the hyphen. It say what belongs together. In sentence (2), without the hyphen, it would not be clear whether it is a "scale problem" that is large, or whether the problem has a "large scale".
Commas after introductory clauses: there is always a comma after clauses like "However", "In this section", "Therefore", ...
TODO: what else.
Spelling
As a final step, ALWAYS run a spell checker over your write-up. It's very embarrassing indeed if your write-up contains mistakes that any spell checker would have found.
TODO: spell-check this web page.
Topic of your own choice or with a company
It is possible to do a master's thesis with a topic of your own choice. Some students also want to write their thesis at a company and want Prof. Bast to be their reviewer. In both of these cases, it is particularly important that the work adheres to the scientific standards sketched above.
If you plan such a thesis and want Prof. Bast to be your reviewer, please send her an email with succinct answers to the following questions:
1. What is the expected / aimed at outcome?
2. How does your approach and the expected result differ from the state of the art? See the section on "Related Work" above.
3. How do you plan to evaluate your work. See the sections on "Theoretical Analysis" and "Empirical Analysis" above.
Please don't send pages full of text. Be brief and specific. Your answers to the three questions above should make it possible to quickly assess what your thesis is about and whether it fulfills our standards. No more, no less.