Quantum @ LIACS

Personal webpage of Vedran Dunjko

Teaching: Foundations of Computer Science 1

On this webpage you will be able to see all the organizational announcements regarding the course Foundations of Computer Science 1 (LIACS), and also you will be able to download relevant teaching materials.

Student confidential data should be accessed via blackboard, accessible from the course web-site.

Course grading. Course grading, and student obligations are detailed on the university course web-site, and were explained in the introductory lecture slides (Intro). Only the mid-term and the final exam contribute to the final grade. All the exercises done during the tutorials, and listed in the exercise sheet are only here to help you prepare for the exams.

For any questions regarding the course, send me an email to v.dunjko [at] liacs.leidenuniv.nl with the subject line starting with “FCS1:”. Otherwise I cannot guarantee a prompt answer.

For consultations, please contact me via email first.

Updates and materials

22-01-2020: The exams have been corrected. Your grades have been uploaded on Blackboard. Recall, in the case you scored y = 5.0 or higher on the midterm, your final grade is the grade of the final exam + y/10, and just the exam grade otherwise. 5.5 in total is a passing grade. The exam, both English and Dutch with the concise hand-written solutions is available here (exam and solutions). Please email me if you see a problem with your grade asap, as your grades will be forwarded to uSIS by the end of the week.

27-12-2019: Additional materials uploaded. Here (concepts-listing) you can download a working version of the list of main concepts we covered in the course. Warning: this is a working version and it is likely to contain typos, please let me know if you find any. It is not meant to be a substitute for the book of Schaum, or the full slides, but rather to be used as a quick check-list for you to make sure you have solid knowledge of the basic concepts. Note, not all concepts that we have covered in the course, nor that you are expected to know are listed -- only the most important, basic ones are.

10-12-2019: Today's lectures can be found here (quick review and exercises) . I may be providing more information on this web page before the exam, if extra clarifications are needed. If I don't see you sooner, I wish you excellent Holidays, and see you in the New Year!

5-12-2019: The last tutorials will cover the exercises 88, 92,104, 108 a) b) for 13.1-13.4, 109 (as many sub-problems as possible).

3-12-2019: Today's lectures can be found here (Languages and automata) . In the pre-lecture I have provided a number of solved problems involving trees, which you can find here here (exercises binary trees & modulo computation) .

29-11-2019: The next tutorials will cover the exercises 83, 86, 87, 102, 106 (a) and c)) and 107 b).

26-11-2019: UPDATE: For the last two lectures, I will make myself available for consultations in the standard lecture room GORL/HAVZ from 13:20 onward. If you are having problems with any of the materials, or would simply like to hear some of the concepts explained again, please send me an email, and I will prepare a short refresher of those topics for that hour. Otherwise, I will be providing brief presentations of some interesting topics we did not have time to cover (and which will not be in the exam but are very interesting).

26-11-2019: Today's lectures can be found here here (Binary trees and modulo computation) .

22-11-2019: The next tutorials will cover the exercises 60, 66 - 68, 79, 82. INFORMATION: in the next lectures we will be continuing with binary trees; it may be beneficial if you have a quick look of Ch. 10 of Schaum, remind yourselves of the basic properties of binary trees, and take a look at section 10.5 (binary tree traversal). We will also be discussing equivalence relations, so remind yourself of that concept.

19-11-2019: Today's lectures can be found here (Induction over structures) (warning: large file) and here (Trees 1) .

14-11-2019: The exercises for the next tutorials are: 50, 51, 52, 53, 59, 62a and 64.

14-11-2019: Last Tuesday's lectures can be found here (Graphs 3, combinatorics) and here (Induction-recursion-1) .

7-11-2019: The exercises for the next tutorials are: 43, 48,49, 50 and 45 (cases with 4 and 5 vertices only).

7-11-2019: Update; Here (exercises-batch-1) you can download the second batch of scans of solutions to some of the exercises you did not manage to cover in the tutorials. Many thanks to your TAs, Daniëlle and Diederick, for providing these. In the case you are having trouble with some of the older exercises, please let me know in the break during the lectures or via email, and I may post detailed solutions online.

6-11-2019: Yesterday's lectures can be found here (Graphs 3) .

1-11-2019: The exercises for the next tutorials are: 41 (note, Th 8.1. of Schaum is the sum-degree formula),42, 44, 46,47, and Schaum problem 8.1 (not the same as Theorem 8.1!).

29-10-2019: Today's lectures can be found here (Graphs 2) ; we covered slides up to 46. Solutions to the mid-term can be found here (solutions mid-term) .

The midterm can be found here (English), and here (Dutch) . The solutions will be made available online after the tutorials.

15-10-2019: The slides from today's lecture can be found here (Graph theory 1) . We stopped at slide 44.

15-10-2019: Minor updates: the university has a number of rules and regulations specifying how exams are administered. The relevant information can be found on this page. Specifically, details about the exam day and process itself (when you can enter, what you can bring in etc.) can be found here.

11-10-2019: The exercises for the next tutorials are: 33, 34, 39 a) and b), and the following two additional exercises. Any remaining time can be used to solve the exercises you did not have time for in the last tutorials.

11-10-2019: Updates regarding preparation for the mid-term: as mentioned early in the course, on the web page of Prof. de Graaf for the course Fundamentele Informatica 1 2018/2019 you can find a lot of additional materials including examples of previous midterms (tussentoets), some with solutions. This year's midterm will be similar; note in some years the midterm covered more materials than we have done this year, and related questions will not appear. This year, the midterm will cover all the materials up to (and including) functions, sequences and series. If you have questions regarding certain exercises, please contact me via email or (better) in person during the lessons. Please ask your questions by and including next Tuesday; I cannot guarantee I will be able to answer all the questions you ask later next week.

11-10-2019: Updates regarding the mid-term. 1) students with permission for extra exam time should report to the rooms 412 and 413 on the day of the exam. 2) The exam will by default be in English, and the answers to questions should be in English. However, in the case you are having language problems, we will have a version in Dutch prepared as well, and we will also evaluate any solutions you give in Dutch as well. In short: language should not be an issue.

9-10-2019: Information regarding the mid-term: the mid-term will take place on Oct 21 (Monday), 11:00-13:00, in Snelius, rooms 312,313,412,413. The exam starts 11:00 sharp. Please show up a bit early so you can be allocated to the appropriate room.

9-10-2019: Information regarding the mid-term content: the mid-term will cover all the topics we have done thus far up to (and including) yesterday's lectures. A good way to prepare is to go through the corresponding chapters of Schaum: Ch. 1: 1.1 - 1.6; Ch. 2; Ch 3: 3.1-3.5. The problems will be exactly the type you have been solving in the tutorials. I may be providing more information on this next Tuesday.

9-10-2019: The slides from yesterday's lecture can be found here (Refresher, Relations 3 finalized, sequences, series) .

7-10-2019: Additional materials uploaded. Here (exercises-batch-1) you can download the first batch of scans of solutions to some of the exercises you did not manage to cover in the tutorials. Many thanks to your TAs, Daniëlle and Diederick, for providing these. In the case you are having trouble with some of the older exercises, please let me know in the break during the lectures or via email, and I may post detailed solutions online.

4-10-2019: Additional materials uploaded. Here (concepts-listing) you can download a working version of a list of main concepts we have been studying so far. Checking if you understand and know all the concepts listed will help you estimate your current knowledge of the matter. Warning: this is a working version and it is likely to contain mistakes, please let me know if you find any. It is not meant to be a substitute for the book of Schaum, or the full slides. In the case you are struggling with certain concepts of the course, I will be happy to introduce additional basic examples and clarifications in this document; please let me know what is problematic by email.

3-10-2019: For the next week, the planned exercises are as follows; 2a and 3a, 21,27,28,30,31,32. Regarding 2a and 3a, prove those using the laws of set algebra, and name the laws. If one of the groups already finished one of the listed exercises in the previous week, you can skip it.

2-10-2019: The slides from yesterday's lecture can be found here (Refresher, Relations 3 finalized) and here (Functions 1) .

27-09-2019: By the request of some of the students, I will be posting (some) of the exercises which will be covered in the upcoming tutorials a few days in advance. For the next week, the planned exercises are as follows; 14d, 14c, 12, 3b, 23d, 23e, 26 (for reflexivity and transitivity), 27 and 28. If one of the groups already finished one of the listed exercises in the previous week, you can skip it.
Additional instructions for the exercises. For 3b, provide a full proof (using basic definitions only, i.e., do not use de Morgan’s law). Hints for 14d, 14c, 3b can be found here . The hints suggest how to solve these problems easier, but any solution is equally valid. For 28, Note a | b denotes that a divides b, i.e. that b/a is a whole number. For 12: you can use proof-by-contradiction.

26-09-2019: The exercises planned for this weeks tutorial were: 8, 11(c,e,f), 17, 18 and 25.

24-09-2019: The slides from today’s lecture can be found here (Relations 3) . Next lecture will finish this set of slides, and move on to the next topic: functions. Additional materials: notes regarding basics of proofs (on the example of Noblemen and Outlaws puzzle) with a few (very) detailed examples are found here (story about proofs) . (Very) detailed proof of associativity of relation composition + a proof-in-picture can be found here (associativity of relation composition).

18-09-2019: Information about the next lecture: based on your feedback, in the next lecture we will spend a bit of extra time discussing proofs, and we will provide a number of detailed examples.

17-09-2019: Today's planned tutorial exercises were 11,13,15,16,22. Not all were completed and we will be providing some of the solutions next time. A typo in the exercise sheets (exercise 11), spotted by a careful student has been fixed. Thank you.

17-09-2019: The slides from today’s lecture can be found here (Relations 1) and here (Relations 2). The contents of this lecture coincide with Schaum 2.1 - 2.6

10-09-2019: Today's planned tutorial exercises were 2,6,7,10,14,19,20. Not all were completed and we will be providing some of the solutions later in the course. For examples of formal proofs of set expression equivalences, see e.g. Schaum exercise 1.8. Exercise 20 is solved in the lecture slides Sets 2 .

10-09-2019: The slides from today’s lecture can be found here: Sets 2 , Sets 3, and Sets 4. The materials of the last two lectures are covered in Schaum 1.1 - 1.7 .

03-09-2019: Answers to admin questions: Issues regarding uSIS registration have been reported and will be fixed soon.
Guidelines regarding which courses to enrol will also be provided shortly.

03-09-2019: The slides from today’s lecture can be found here: Intro, Sets 1.
The tentative exercise sheet can be found here. The exercise sheet may be updated as the course progresses.

03-09-2019: First lecture will take place in at 14:15 in GORL/HAVZ (Havingazaal)
This first lecture will last from 14:15 to 16:45.
There will be no tutorials after the lecture in this first week.

A lot of related materials in dutch can be found on the web page of Prof. de Graaf for the course Fundamentele Informatica 1 2018/2019.