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
- dr. Bas Luttik, MF 6.072, s.p.luttik@tue.nl
- prof. dr. Bettina Speckmann, MF 4.105, b.speckmann@tue.nl
- dr. Tom Verhoeff, MF 6.093, t.verhoeff@tue.nl
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:
- Lectures.
- Labs. During the labs you have the opportunity to work on the home work assignment. Instructors will be present to answer questions.
- 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:
- four (4) homework assignments, the average of which counts for 40% of the final grade.
- a written exam which counts for the remaining 60% of the final grade.
Assignments
- Assignments have to be handed in by each student separately.
- Assignments have to be typeset in English as PDF. No handwritten solutions will be accepted.
- Assignments have to be handed in via Peach. Do not send assignments by e-mail.
- 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
T.H. Cormen.
Algorithms Unlocked.
MIT Press, 2013.
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 | |
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) |