2IS80 - Fundamentals of Informatics

Announcements

[17-02-2016
Grade details for the exam of 28 Jan 2016 have been uploaded to Oase.
Time slots for inspection of work and preparation for the re-sit are included in the schedule below.
[13-01-2016]
A summary of the Information theme is available on Oase.
Errata
[13-01-2016]
An old exam is available on Oase.
[06-01-2016]
Due to the Open Days on Fri/Sat 08/09 Jan 2016, AUD is unavailable for education.
Consequently, there is no lab session Fri 08 Jan 2016. The lectures in PAV proceed as scheduled.
[16-11-2015]
Because Oase does not accept our slides, we make them available here. The titles in the Schedule link to the slides.
[12-11-2015]
Drawings of automata and state machines may be done by hand. You can either scan them or take a snapshot with your phone camera; please, insert them properly into your document.
It may, however, be more convenient to use an on-line service like draw.io, which offers a very simple way of drawing diagrams with text labels, and downloading them in various formats.
[09-11-2015]
Exploratory assignment: Describe behavior of automata.
[09-11-2015]
The first lecture is on Wed 11 Nov at 14:45 (6th hour) in AUD 16 and (via video) AUD 10. Hour 5 is not used in the first week.
[04-11-2015]
The reader is available in the Lecture Notes Shop (opening hours and location)
[18-10-2015]
Course registration is closed.

Course information

Lecturers

In emails, always include [2IS80] in the Subject field.

Description

Informatics (also known as Computer Science) has become a fourth 'great scientific domain’, next to the natural, life, and social sciences. Especially within engineering, Informatics plays an increasingly significant role. This course is about the concepts, ideas, methods, and results that are fundamental to informatics as a science. An example of such a result is the discovery of problems that cannot be solved by computers, and that it will never be possible to do so!

See also the course page on OWInfo.

Prerequisites

For this course no specific prior knowledge is required.

Format

The course has three components:

  1. Lectures.
  2. Labs. During the labs you have the opportunity to work on the home work assignment. Instructors will be present to answer questions.
  3. Tutorials. During the tutorials the instructors will explain the solutions to home work assignments and answer any new questions that may arise.
Day Time Where What Who
Wednesday 13:45 - 15:30 AUD 10 Tutorial Group 1 (Instructor: Wieger Wesselink)
AUD 12 Tutorial Group 2 (Instructor: Jaap van der Woude)
AUD 16 Tutorial Group 3 (Instructor: Arthur van Goethem)
15:45 - 17:30 AUD 08 Lecture All students
Friday 8:45 - 10:30 AUD 07 Lab All students
10:45 - 12:30 PAV B1 Lecture All students

Grading

The final grade is based on the following items:

  1. four (4) homework assignments, the average of which counts for 40% of the final grade.
  2. a written exam which counts for the remaining 60% of the final grade.

Assignments

  1. Assignments have to be handed in by each student separately.
  2. Assignments have to be typeset in English as PDF. No handwritten solutions will be accepted.
  3. Assignments have to be handed in via Peach. Do not send assignments by e-mail.
  4. Assignments are due at 23:59. Late assignments will not be accepted.

Academic Dishonesty: All class work has to be done independently. You are of course allowed to discuss the material presented in class, homework assignments, or general solution strategies with the lecturers or your classmates, but you have to formulate and write up your solutions by yourself. You must not copy from the internet, your friends, or other textbooks. Problem solving is an important component of this course so it is really in your best interest to try and solve all problems by yourself. If you represent other people's work as your own then that constitutes fraud and will be dealt with accordingly.

Literature

Book cover

T.H. Cormen.
Algorithms Unlocked.
MIT Press, 2013.


Book cover

Selected chapters (available as a reader, see above) from:
A.K. Dewdney.
The New Turing Omnibus
Computer Science Press, 1993.


Schedule

Lectures Assignments
Week Date Topic Material Lecturer Due PDF
46 Computational Mechanisms
11-11-2015 1. Introduction (5th hour) Explore automata Tom Verhoeff
2. Finite automata and regular expressions Ch. 2 reader Bas Luttik P1
13-11-2015 3. Turing machines Ch. 31 reader Bas Luttik
47 18-11-2015 4. From universal Turing machines to Algorithms Ch. 17,31,51,66 reader + Ch. 1 book Bas Luttik 20-11-2015 A1
Algorithmics
20-11-2015 5. Sorting and searching 1 Ch. 2 + 3 book Bettina Speckmann P2
48 25-11-2015 6. Sorting and searching 2 Ch. 2 + 3 book Bettina Speckmann
27-11-2015 7. Graphs and shortest paths Ch. 5 + 6 book Bettina Speckmann
49 02-12-2015 8. Graphs and shortest paths Ch. 5 + 6 book Bettina Speckmann 04-12-2015 A2 (v2)
Information
04-12-2015 9. Information and data compression Ch. 4 + 9 book Tom Verhoeff P3, P3a+
50 09-12-2015 10. Error detection and correction Ch. 49 reader Tom Verhoeff P3b+
11-12-2015 No lecture (lab session proceeds as scheduled)
51 16-12-2015 11. Cryptography Ch. 8 book Tom Verhoeff 18-12-2015 A3
Limits of Computability
18-12-2015 12. The halting problem Ch. 10 book Bas Luttik P4
52 No lectures, TU/e closed
01 No lectures, TU/e closed
02 06-01-2016 13. Reduction and intractability Ch. 59 reader Bas Luttik
08-01-2016 14. NP completeness (no lab session) Ch. 59 + 66 reader Bas Luttik
03 13-01-2016 Instruction: work on assignment 4
15. Big picture Tom Verhoeff 15-01-2016 A4
Exam preparation
15-01-2016 No lab session
During lecture time slot: Discuss old exam
05 28-01-2016 13:30 - 16:30 written exam
08 26-02-2016 12:45 - 13:30: Inspect work for exam of 28 Jan 2016
Location: AUD 9
13 30-03-2016 12:45 - 13:30: Discuss exam of 28 Jan 2016 to prepare for re-sit
Location: AUD 12
15 14-04-2016 18:00 - 21:00 written exam (re-sit)