ADS2 Tutorial 2024/25

See the Table of Contents on the right. I highly recommend reading through the whole page.

You can find below the tasks done at the tutorial. To communicate regarding the homework, we will be using OWL. If you haven't received an enrollment token from me, please send me an email.

When sending an email, please always add [ADS2] in the subject line.

What we have done at the tutorial

(To compile the tex, you also need the following preamble.)

Useful Resources

[A] Algorithms by Dasgupta, Papadimitriou, and Vazirani
[JE] Algorithms by Jeff Erickson (the page contains various PDFs suitable for screen, printing etc.)
[CLRS] Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. Find it on libgen

Credit requirements

I will grant credits for gaining a total of 100 points. You can see your current number of points in OWL.

You can gain points in the following ways:

Solving homework: I will assign tasks for at least 150 points. Each task has a deadline, typically in two weeks; for solutions submitted after the deadline you only get 2/3 of total points. The tasks will be divided into thematic groups distinguished by some code and I require that you hand in at least one task from each group. It's OK if your solution is not perfect, but I want you to put some effort into each group of tasks. More details on homework.
Student grading: if you are confident when handing in homework, you can get up extra points by becoming a student grader for this task. The formula for points obtained is $r \cdot b/5$, where $b$ is the number of points the task is worth and $r$ is the number of solutions you graded, that is, if a task is worth $6$ points and you grade $10$ solutions, you will get $10 \cdot 6/5 = 12$ points. You can only become a grader $3\times$ a semester. More about student grading…
Project: you can get extra points for a small project, which can be practical (implementing some algorithm) or theoretical (description and analysis of some nontrivial algorithm). You can propose a project or ask me for ideas. The project has to be novel in some way; I will not allow a simple implementation of a textbook algorithm, not least because those are widely publicly available.

More Information

Homework

Only hand in homework electronically via OWL either as plaintext, markdown with math (best option), or a PDF file. The PDF can be created from MS Word, LibreOffice Writer, typeset with (La)Tex, or it can be a readable (!!!) scan or camera picture (I recommend Office Lens (iOS, Android) or a similar app, especially if you want to accompany your solution with a picture.)
Unless stated otherwise, by „solving“ a task I mean that you prove the given statement.
A proof must be correct, clear, and easy to understand.
If the proof involves an algorithm, you must give a proof of correctness and a complexity analysis.
In your proof you can use statements from the lecture without proving them.
If you start getting lost in your formulations, introduce notation. Assign precise names to objects or quantities and use these names or variables in your text, instead of using pronouns. (It is a common mistake that you talk about this or that set and I'm quickly lost. Why not say a set $A$ and a set $B$?) In plaintext denote a subscript as follows: $a_1$ is a_1, and superscript as follows: $a^2$ is a^2$.
For a good (correct, clear, easy to understand) solution you will gain the full amount of points. If something is missing, but the proof contains the right idea, or if the proof is correct but not quite clear or intelligible, you will get about half the points. If you don't solve the task at all or the proof is completely incorrect, you will get 0 points.
Grading Process:
- About a week after publishing homework, I will give first feedback.
- If your solution looks like it might be correct but important details are missing, I will ask you for explanations. If your solution is incorrect, you will have a chance to resubmit.
- Shortly after the deadline, I will do the same, giving an additional week to those who have tried to do the homework within the deadline. This process can repeat at most once more, so you get 2 resubmission / correcting attempts.
- Late submissions are graded in the same way but the obtained points are reduced by 2/3.
- Submissions 2 months after the deadline are not accepted.
I strongly recommend to learn the basics of mathematics typesetting using LaTeX. I have good experience with the LaTeX wikibook. The easiest way to get into it is probably hackmd.io (small syntax demo; click „edit“ to see the code.) You can also use a web LaTeX editor (Overleaf) because getting LaTeX to work locally can be nontrivial.
I always recommend collaboration when solving tasks and homework, BUT:
- Try solving the task yourself first, you will learn more.
- Try to avoid using ChatGPT and similar tools; I think you don't learn much that way, but I don't strictly forbid it. I will treat ChatGPT usage the same way as talking to a friend, most crucially:
- Even if you solved the task with someone, you must write up your own solution, without the help of any AI/LLM/… If anything makes me suspicious that you don't really understand the task and are just copying what someone (or something) else wrote, and if my suspicion is confirmed, I will report you to PlagUE. I will be much more skeptical next time and I will keep asking many questions about your solution until I'm convinced you really understand the solution.
- Don't ever cheat.

Student Grading

If you are confident in your homework solution, send me an email with the subject line [grading] name-of-task. I will grade your task first and if it is OK, I will give you extra points for grading the solutions of your classmates. The formula for how many more points you get is $r \cdot b/5$, where $b$ is how many points the task is worth and $r$ is the number of solutions you will grade, so if a task is worth $6$ points and you will grade $10$ students, you will gain $10 \cdot 6/5 = 12$ points. You can become a student grader at most $3\times$ a semester.

Logistically: the way it works is that I give access to the grader in OWL, he grades and assigns points, and I see all of it and can make corrections if needed. The grader should carefully read and evaluate a solution. Is the solution correct? If not, where did the author make a mistake? What are they not understanding and how could I help them understand? What question will push them in the right direction? Next, is the solution clear and easy to understand? Would it be helpful to split the solution into more paragraphs? Introduce some notation? Etc. Based on this the grader will suggest a number of points, for example:

The solution is essentially correct, but I would suggest instead of using the notation A, B, C to use an indexed notation A_1, A_2, A_3. Otherwise, the proof was structured relatively clearly.

… and then give 2 points for the task.

If I feel a need to add anything to the feedback provided by the grader or to change the amount of points awareded, I will do that (but it only happens rarely).

The grader's responsibility is to correct all the assigned tasks within a week that they become accessible to them in OWL.