Karel Král

kralka (AT) iuuk.mff.cuni.cz

Veronika Slívová

slivova (AT) iuuk.mff.cuni.cz

What happened during face to face. Useful links.

Mentoring for Students of English Curriculum

Time Friday 15:40, room S4

What happened:

May 24

Complexity and computability once again.

May 17

Bloom filters.

May 10

Data structures.

May 3

Data structures and what we would expect on the exam.

Apr 26

Hash functions.

Apr 19

State holiday.

Apr 18

Moved mentoring. Data structures.

Apr 12

No mentoring today. Ask your questions using email.

Apr 5

Morning session in our office.

Mar 29

Data structures questions.

Mar 22

Data structures questions.

Mar 15

Splay trees measurements.

Mar 8

Plotting data.

Mar 1

Splay trees (beware there are some nice pictures but also some terrible mistakes on Wikipedia).

Rotations on Splay trees -- why single rotations are not enough.

Splay trees can be linearly deep!

Software project try announcing your software project at some facebook group or in the classroom.


Email questions and advertisement during classes.

Jan 11

Approximation algorithms. Scheduling and metric travelling salesman.

Jan 4

Complexity, big O notation. Working with memory in C++.

Dec 21

Reductions again but for a different audience.

Dec 14


Dec 7

Hierarchy theorems with construction of universal turing machine. Four diagonalization proofs (size of the set of real numbers and natural numbers, set theory, computability, complexity -- hierarchy theorems).

We are making an unofficial preparatory course for Data Structures. You should get an email about this, if you have not send me and email and I will add you to the mail list. If you want to participate implement a linked list and sorting using linked list.

Nov 30

Savitch theorem.

We are starting the Data Structures 101 minicourse (I will send an email about it).

Nov 23

Time and space complexity, big O notation, deterministic vs nondeterministic Turing machines, P vs NP (without proof).

Nov 16

We need to leave early, please meet us in our office at 13:00. We need to leave by 15:00 (preferably earlier). We are happy to answer your emails during the weekend or meet you during next week.

Space and time complexity, intuition, relations with each other, complexity classes.

If you are interested we are able to do a Programming and Data Structures 101 course. Ideally during this semester, the sooner the better. (We are tutors for czech students for Datastructures I course.)

Nov 9

Post Correspondence Theorem and reducibility of problems.

Nov 2

Reducibility, completeness, hardness. Mainly for complexity theory (with introduction of non-deterministic machines and the class NP).

Oct 26

Computability theory, Gödel enumeration of Turing machines, diagonalization, halting problem and intuition behind all this.

Oct 19

There were just four students. You can meet us this Friday 14:00 in our office, fifth floor, ring the bell "Doktorandi KAM". We will also be in the room S4 at 15:40 for limited time, if someone comes.

Book on computability: pretty much slide 4 from the lecture., Arora Barak is available for free in pdf. Two other books (I have not read those, but both seem nice, the books might be written from another point of view, so I cannot tell how useful those are for the classes) http://computingbook.org/ http://hjemmesider.diku.dk/~neil/comp2book2007/book-whole.pdf

Bookshops list.

Libraries: MFF UK library catalog. National Library of Technology (you might need to pay a reasonable membership fee). Municipal Library of Prague (general purpose, again you need to pay some fee).

Student licence for software: you may try to use computers in the computer lab. List of available software (mainly in czech, but do not hesitate to use an online translator or to ask us for a translation).

Oct 2, 15:30 room S510.

Introduction of each other.

Signing up for classes.

Software project and Thesis.


Q: Address of study department, how to get certificate that you are a student?

A: Ke Karlovu 3, go there, be nice, they will help you.

Q: Credits for Bc classes?

A: Yes, these will be counted as optional credits (not compulsory and also not elective).

Q: Where to find teacher list for Software project. And list of available Software projects.

A: Adam Dingle will give an overview Friday 12.10 from 15:40 - 16:40 in room S11.

Q: Where to find Erasmus info.

A: See this site. We will happily add more info in case anyone is interested.

Q: Algorithms and Data Structures 101?

A: We can make this happen or give you enough material.

Q: What is 3blue1brown?

A: An awesome visual math tutorials 3blue1brown. Check this out!

Q: Does the 15 credits rule apply to me as well?

A: No! You only need to get 45 credits by the end of semester. Take a look at this study guide page.

Q: What is the 45 credit rule?

A: You should get at least 45 credits each year. This is the bare minimum (you should optimally get at least 60 credits).

Q: Are there videos of some lectures?

A: Yes! Sometimes even in english! See for instance the very popular course of Deep learning by Milan Straka!