ADS1 Tutorial 2022/23

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

You can find below both the tasks done at the tutorial as well as the homework assignments. However, 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

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 weaks, then you only get 2/3 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.

Další informace

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.
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 is iterative: if you eventually converge to a perfect solution I didn't need to give it away, just give hints, you can still obtain the full amount of points. My goal is for you to discover the solution, and that's what gets rewarded, not the amount of work you put in. (E.g. if someone gets it right on their first try, they will get the same point as someone who required two rounds of feedback.)
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.
- Even if you solved the task with someone, you must write up your own solution. If anything makes me suspicious that you don't really understand the task and are just copying what someone else wrote, and if my suspicion is confirmed, I will be much more skeptical next times and I will keep asking many questions about your solution until I'm convinced you really understand the solution.

Student Grading

If you are confident in your homework solution, send me an email with the subject line [ADS1][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.