florian-rabe/teaching

My lecture notes and other course materials

teaching's Issues

New room

Our room was changed to West Hall 2 (starting Thursday).

Scala example implementation of formal systems

I've split the example into two git branches.

• master: A very simple implementation that covers only type theory and is good to acquire basic understanding. It is sufficient for Homework Problem 3.1

• formal_systems_full: an advanced implementation that includes

  • programing language as discussed in the lecture
  • type inference, i.e., we can omit types in places where they can be inferred from the context
  • control flow operators, whose rules are not given in the lecture

  You can use this to deepen understanding and to run example programs (which may be helpful for Homework Problem 3.2).

Talk on JavaScript — The Birth & Death of JavaScript

A bit on the history, the current state of affairs, and a view on the future.

https://www.destroyallsoftware.com/talks/the-birth-and-death-of-javascript

Auditing AaDS

Auditors must submit homeworks as everybody else and reach a passing percentage on the homeworks.

They do not have to do quizzes or final.

Course content

The course description on campus net was automatically copied-over from last year, when the course was given by a different instructor, and is therefore outdated.

This year's course will cover much of the same material but with different emphasis and in a different order.

You can get an idea of the course content by peeking at the table of contents of my lecture notes.
However, note that list is not final yet. (In particular, it almost certainly contains more material than we will be able to cover.)

Tutorial

There will be a tutorial tomorrow at 16:30 in NM Conference Room.

Homework 2

I've posted it.

Tutorial

There will be a tutorial today at 20:00 in NM Conference Room.

Homework 3 posted

Small mistake in the notes

There seems to be a word missing between "mentioned" and "and programs" (see screenshot).
I hope this helpfull and not nitpicking.

Square-and-multiply algorithm on lecture notes (AaDS)

It seems that square-and-multiply algorithm on page 33 will not terminate. (Please go over it; I might have failed to notice that it could work.) I found the following implementation on Wikipedia (Click here to view it) and it appears to be a good example of it.

Function exp_by_squaring(x, n)
    if n < 0  then return exp_by_squaring(1 / x, -n);
    else if n = 0  then return  1;
    else if n = 1  then return  x ;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

Homework 7 published

This is officially published only next week.

But some of you may prefer to do both at once.
So I'm making it available already.

Homework Submission

• Some of you are submitting source files and PDFs to jgrader. Please submit only zip files.

• Make sure to submit all the files before the deadline. Grading late assignments sent by email is not possible.

Homework 4 posted

This is not due for a while.

But the first problem is about correctness. So you may want to look at that one now already.

Course registration rejected

I checked with the student records office: First-year students who were rejected from the course can register for it if they submit a prerequisite waiver form.

The form has to be signed by (at least) me and be submitted to the student records office.
You should do that right away.

Relevant current events

I'm going to use this issue to post interesting current practical examples that I come across.

Feel free to post yourself if you find something.

Course content

SaDS is a completely new course, and it is not entirely obvious what material it should and how much material it can cover.

The table of contents give you a rough idea what we will do, but I may still have to adjust that list significantly as we go along.

Homework 3 posted

Homework 2 posted

I'll answer questions in the lecture tomorrow.

I will discuss some techniques relevant for this homework in upcoming lectures.
But it's possible to start working on it already.

Tutorial Time Slot

Based on the discussion during today's tutorial, I put the possible time slots for the tutorial in a doodle vote.
Please choose the sime slots that best fit your schedule
http://doodle.com/poll/ez5cgzqtpptipww9#table

Small mistake in the notes #2

It should be n==0 not x==0

Homework policy

Homeworks will usually be

• posted on Tuesday (in the github repository)
• due on Thursday morning (11:00) of the following week

Homeworks will be submitted via grader by uploading one zip file for each problem.

For each student, the weakest two homeworks are not counted for grading.
In exchange, there will be no deadline extensions whatsoever.
If you are officially excused for the majority of the week, the homework will not count for you.

AaDS: No slot for the third homework (HW #3)

Hello,

I cannot upload my solutions for the third homework because no slot is created.

Homework 6 published

I'm officially giving it out tomorrow. But it's already online.

Excuses for Quiz

I received some official excuses for people who did not notify me ahead of time that they would miss the quiz.

As per official policy, I will not accept those excuses.

Homework submission

Homeworks will be submitted via github.

Be prepared to tell me a github user and repository name on Thursday next week.

AaDS: Not registered on Jgrader

Dear Dr. Rabe,

I am registered on Campusnet for AaDS but could not select AaDS as active course and submit homework on Jgrader.

Best,

Rui Cao

Bonus homework on static analysis

As announced in the lecture, I'm offering a bonus homework for up to 5% credit.

You have to

• choose a major open source project
• run a state-of-the-art static analysis tool over it (e.g., findbugs for Java as demonstrated in the lecture)
• identity faults, patch them, and submit the patch back to the project

For example, for a github project, you might

• fork it and clone the fork
• set up an IDE with a plugin for your static analysis tool
• use the IDE to build the project and run the analysis tool
• inspect and evaluate the (potential) faults detected by the tool
• remove faults, push the change, and submit a pull request to the project maintainers.

Homework 1

Homework 1 is published.

Retakers

I'll announce the procedure for retakers in this issue.

I created this issue so that affected people can subscribe to it already.

Homework Submission

After the discussion, we made an agreement on how to submit the homework.

Please create a private repository by next Tuesday, and add @florian-rabe @aulon and me as collaborators. Also, please inform Florian the match of your real name and GitHub username.

Ps: as a student, you can create private repositories for free. You can get the student developer pack here: https://education.github.com/pack

Homework 5 published

Tutorials

Tutorials will start next week.

AaDS: Quiz 3 this week

Does anyone know for sure whether we are having a quiz this week?

Update: It is announced that It is on Thursday (16.03)

Additional section on loop invariants and termination orderings

In the lecture, some people had difficulties with these concepts.

So I added Sect. 3.1.4.
It introduces no new material. Instead, it explains the same material in a different way.

This new way is particularly helpful for self-study: It shows how you can implement potential loop invariants and termination orderings in such a way that you can test them by running the program.

AaDS: No slot for the first question (HW #1)

Hello,

I cannot upload my solutions for the first question of the first homework.
The deadline is false. It is indicated as follows: "No submission, deadline was 0000-00-00 00:00:00."

Final Tutorial Time Slot

Given that in the poll there was no agreement, I am setting the tutorial for Sunday 3 pm.

Hope to see you all there!

Feedback on using GitHub

This is the first time I'm using GitHub, and this a bit of an experiment.
Please let me know if this is working well for managing a lecture.

I've created this issue so that we can discuss the pros and cons of using GitHub.
Respond to this issue with any feedback or suggestions specific to the use of GitHub.

Typo in AaDS lecture notes

In Example 3.10 (https://github.com/florian-rabe/Teaching/blob/master/AaDS_17/goals.tex#L215) it should be it is sufficient to prove $\gcd(x,y)=\gcd(x, y-x) not it is sufficient to prove $\gcd(x,y)=\gcd(y-x). gcd on one argument makes no sense here.

Tutorial today 4pm NM conference room

Cost of polynomial multiplication

In today's lecture, I ran out of time and couldn't finish the cost of the example algorithm.

We computed the number of multiplications for multiplying polynomials of degree $n$ to be $3^{\log_2 (n+1)}$.

That simplifies to $(n+1)^{\log_2 3}$, which is roughly $(n+1)^{1.58}$ and thus much better than $(n+1)^2$.

Problem 3.1

One student asks by email:

I had a question regarding the first problem of the 3rd homework in Algorithms
and Data Structures.
One part of the problem is to argue informally why there can be no better
algorithm. I am confused as to how does one do that.
I can only say that this is the algorithm that I came up with and that it takes
the least amount of steps/operations possible. Could you give an example of
correct solution to the problem?

Using GitHub for the course

I'm using GitHub to manage my courses.

Announcements and Questions

All announcements and questions will be posted as issues on this repository.
Labels will be used to sort these conveniently.
If you create a new issue, make sure to attach appropriate labels.

Note that I use this repository for multiple courses - always include the label for the course:

• AaDS Algorithms and Data Structures
• SaDS Secure and Dependable Systems

Lecture notes

The lecture notes are part of the repository.
You can read them online or create a local copy using the 'git pull' command.

The lecture are written using LaTeX (which you should learn anyway and which you may want to use to write your homeworks).
If you use LaTeX, you can edit and compile the lecture notes yourself.

You can even use 'git push' requests to propose changes to me. - I may award bonus credit for substantial improvements.

Homework 1 posted

It's in this repo.
I'll answer questions in the lecture tomorrow.

Homeworks

I've uploaded a partial solution to Subproblems 1-3 of question 2.1.

As discussed in the lecture, deadline HW 2+3 are pushed to the respective Tuesday.

I've also adapted the problem statement to make it a little simpler and fit the partial solution better.

As before, you can alternative implement it in a different language.

Grading

The course will be graded as follows:

• 7 quizzes at 5 % each
• homeworks at 15 %
• 50 % final exam

bonus credit as announced

Lecture rescheduling

I'll be off-campus on Thursday March 23.

As agreed in the lecture today, we will make up for that by extending some of the Thursday lectures.

We will start next week (March 16) with a lecture 19:00-21:00.

Reassessment

Some people asked me about the reassessment option.

My understanding is that I can simply let you take my final exam.
I will find out and get back to you by responding to this issue.

Note that a reassessment can make your results worse, especially when (as in this year) the instructor has changed.
My final exam may or may not have a different emphasis than last year's, and that may work for or against anybody who takes a reassessment.

Grading SaDS

The grading scheme will be as follows:

• 10%: attendance (starting next week)
• 15%: homeworks
• 30% midterm exam
• 45% final exam

Up to 10% bonus points are obtainable through major contributions to the lecture notes.
To submit such a contribution, generate a pull request.
(If you plan to make a major contribution, you may want to check with me first).

Lecture rescheduling

I'm off campus on Thursday next week.

Therefore,

• there will be a double-lecture on Tuesday, Mar 21, 8:15 - 11:00
• there will be no lecture on Thursday, Mar 23