Announcements

[21-11-2014]

Drawings of automata and state machines may be done by hand. You can either scan them or take a snapshot with your phone camera, but please insert them properly into your document.

[13-11-2014]

Exploratory assignment: describe behavior of automata.

[11-11-2014]

The reader is now available in the shop, see http://w3.tue.nl/en/services/diz/operational_services/facility_services/reproshop_and_lecture_notes_shop/lecture_notes_shop/ for opening hours and location.

[10-11-2014]

The first lecture is on November 12 in the Blauwe Zaal at 14.45 o'clock (hour 5 is not used this first week only).

[10-11-2014]

Link to Peach.

[09-11-2014]

Course registration is closed.

[08-10-2014]

Course registration is open.

Course information

Lecturers

• dr. Bas Luttik, MF 7.072, s.p.luttik@tue.nl
• prof. dr. Bettina Speckmann, MF 6.094, b.speckmann@tue.nl
• dr. Tom Verhoeff, MF 7.098, t.verhoeff@tue.nl

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	LG 1.105	Tutorial	Group 1 (Instructor: Ruurd Kuiper)
		AUD 10	Tutorial	Group 2 (Instructor: Kevin Verbeek)
		PT 9.05	Tutorial	Group 3 (Instructor: Hans Zantema)
	15:45 - 17:30	AUD 01	Lecture	All students
Friday	8:45 - 10:30	AUD 16	Tutorial	Group 1 (Instructor: Ruurd Kuiper)
		MA 1.41	Tutorial	Group 2 (Instructor: Kevin Verbeek)
		MF 7	Tutorial	Group 3 (Instructor: Hans Zantema)
	10:45 - 12:30	AUD 01	Lecture	All students

Grading

The final grade is based on the following items:

1. 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. 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

Schedule

	Lectures				Assignments
Week	Date	Topic	Material	Lecturer	Due	PDF
46	12-11-2014	Introduction		Tom Verhoeff
	12-11-2014	Finite automata and regular expressions	Ch. 2 reader	Bas Luttik
	14-11-2014	Turing machines	Ch. 31 reader	Bas Luttik
47	19-11-2014	From universal Turing machines to Algorithms	Ch. 17,31,51,66 reader + Ch. 1 book	Bas Luttik
	21-11-2014	Sorting and searching	Ch. 2 + 3 book	Bettina Speckmann	21-11-2014	A1
48	26-11-2014	Sorting and searching	Ch. 2 + 3 book	Bettina Speckmann
	28-11-2014	Graphs and shortest paths	Ch. 5 + 6 book	Bettina Speckmann
49	03-12-2014	Graphs and shortest paths	Ch. 5 + 6 book	Bettina Speckmann
	05-12-2014	Information and data compression	Ch. 4 + 9 book	Tom Verhoeff	05-12-2014	A2
50	10-12-2014	Error detection and correction	Ch. 49 reader	Tom Verhoeff
	12-12-2014	No lecture and no instruction, open day
51	17-12-2014	Cryptography	Ch. 8 book	Tom Verhoeff
	19-12-2014	The halting problem	Ch. 10 book	Bas Luttik	19-12-2014	A3
52		No lectures, TU/e closed
01		No lectures, TU/e closed
02	07-01-2015	Reduction and intractability	Ch. 59 reader	Bas Luttik
	09-01-2015	NP completeness	Ch. 59 + 66 reader	Bas Luttik
03	14-01-2015	Instruction: work on assignment 4
		Lecture: Big picture		Tom Verhoeff
	16-01-2015	Instruction: discuss old exam
		No lecture			16-01-2015	A4
05	29-01-2015	13:30 - 16:30 written exam
10	16-04-2015	18:00 - 21:00 written exam (re-sit)