Due to a reorganisation, this course has been unified with the corresponding course at GU. Hence, formally this course as such is not given anymore. However, for a period of time there will still be retakes of the exam as it is required. Check the page Tentamensdatum, nedlagda kurser for information on exams dates. Information about the course replacing this course can be found here Beräkningsmodeller, TDA181/INN11.
Here you will find the latest news from the course. Remember to check this section regularly!Back to contents.2004-08-31: Check section Exam for a link to the last exam and its solutions.
2004-03-25: The exams are already corrected. It will take possible a couple of days before the results are available in the computer system or in the usual board (straight beneath "Café Linsen"). There will be a "tentagranskning" on Friday 2nd of April, from 12 to 13 in room 6103 (6th floor from EDIT building).
You can look at some numbers about the exams here.
2004-03-05: The second return of lab 4 has been moved one week to March 19th! Check the section Assignments.
2004-03-02: Exercises on week 7:
KJ: Some of 10.4-5, 10.7-9, 11.1-2.
NAD: 10.2, 10.6-7, KP6.9, KP6.11.
2004-03-02: On last lecture, KJ will do exam's exercises. He will take the last exams in reverse chronological order, that is, first the one in January 04, then August 03 and last March 03. Howe much he will be able to cover is unclear. Check the section Exam in order to see the exercises.
2004-03-01: A web page with a questionnaire to evaluate the course is now available. Click here to give your opinion on the course!
2004-02-27: Monday's lecture will probably not take the 2 hours. We could use the remaining time to discuss/answer/go through anything in the course were you have problems. So, if you have time, come to the lecture with some questions on the things you have problems!
Remember, Kristofer will give the last lecture where he will present old exams and discuss the solutions.
2004-02-23: Exercises on week 6:
KJ: For Wednesday it will be some (not all) of the following: 9.7-9, 9.14-16, 9.19-22, 10.1-2.
NAD: This week we will work with some of the following exercises: 9.14-16, 9.19-21, 10.1-2, 10.5-7.
2004-02-09: Exercises on week 5:
KJ: The plan is to do some of the following: 8.6-11, 9.1-2.
NAD: This week we will work with some of the following exercises: 8.4, 8.8, 8.10-12, 9.1-2, 9.7, 9.15.
2004-02-17: This note is for those working in groups for the programming assignments. Please notice that both of you should register and submit the assignment! Otherwise the system cannot keep track of whether you have done the assignment or not!
2004-02-12: The fourth assignment is already available. Check section Assignments.
2004-02-10: As for this week, Nils Anders will be available for questions in his room on Fridays 15-17 and not on Thursdays 15-17.
2004-02-09: Exercises on week 4:
KJ: The plan is to do some of the following: 6.4, 7.4, 7.6-7, 8.1, 8.6-9.
NAD: This week we will work with some of the following exercises: 6.2, 7.4, 7.7, KP5.1-2, 8.2, 8.6, 8.8-9.
2004-02-09: The instructions on how to submit your programming assignments are now available! Check the section Assignments.
2004-02-02: Exercises on week 3:
Kristofer's group: The plan is to do some of the following: 4.2, 4.5-7, 5.2, 5.4, 7.1.
Nils Anders' group will work with some of the following exercises: 4.5-6, 5.1-2, 5.4, 7.2-3.
2004-01-30: The second assignment is already available. Check section Assignments. We are working on an electronic submission. Seems promising but it has not been sufficiently tested. Hence, the instructions on how to submit the assignment will be available some time next week.
2004-01-27: I was asked to remind you to read these instructions if you have problems reading your email from your laboration account.
2004-01-22: The first assignment is already available. Check section Assignments.
2004-01-20: The first set of exercises is already available. Check section Exercises.
To reach all the teachers involved in the course you can write to the following address: grund@mdstud.chalmers.se.Lecturer:
Ana Bove, bove(at)cs(dot)chalmers(dot)se, room 6116 - telephone 772 1020 in E-building, CTH.Tutors:
Nils Anders Danielsson, nad, room 6453 - telephone 772 1084 in E-building, CTH;
Kristofer Johannisson, krijo(at)cs(dot)chalmers(dot)se, room 6122 - telephone 772 5412 in E-building, CTH.
Back to contents.
In this course, we study the concepts of program, programming language and computation from a more general and mathematical point of view than in the introductory programming courses. Among other things, we study several so called models of computation. These can be seen as simplified programming languages which still contain a kernel of constructions necessary to get full expressive power. Examples of models of computation are the lambda-calculus, which is the basis of any functional programming language, and Turing machines, a very simple (theoretical) computer defined in the 30's by the mathematician Alan Turing. We discuss the limitations of the expressive power of programming languages - for example Turing's result that there is no computable solution of the so called halting problem. The course also contains an introduction to techniques for defining the syntax and semantics of programming languages in a precise way. More concretely, the different subjects we will study in the course are the following:
Further Reading Material and Relevant Links
The lectures will take place on Mondays 13.15 - 15 in EC and on Thursdays 13.15 - 15 in EA. The course starts on Monday the 19th of January and it lasts 7 weeks. See the link to the schema of D2/LP3.Back to contents.Preliminary Schedule
Please check this table regularly for possible changes!
Few days before each lecture I will make available a ps and a pdf file with the slides of the lecture. It will be very convenient for you if you can print this file before the lecture.
Nr.Lecture Date Content of the Lecture Source Relevant Literature L1 (CW 1) Mo 19 Jan. Administrative issues. Introduction. (ps, pdf) computable functions L2 (CW 1) Th 22 Jan. Sets, (Mathematical) Induction and Relations. (ps, pdf) [KP 2.1--2.8] L3 (CW 2) Mo 26 Jan. Functions and Countable Sets. (ps, pdf) [KP 2.9.1--2.9.3, KP 3.1] L4 (CW 2) Th 29 Jan. Countable Sets. Finite automata. (ps, pdf) [KP 3.1, 6.1] L5 (CW 3) Mo 2 Feb. Finite automata and Finite state machines. Primitive and structural recursion. (ps, pdf) primitive recursive functions, [KP 6.1, 2.9.4--2.9.6] L6 (CW 3) Th 5 Feb. Primitive recursive functions. Recursive functions. (ps, pdf) primitive recursive functions, [KP 2.9.4, 6.3] L7 (CW 4) Mo 9 Feb. Lambda calculus. (ps, pdf) [KP 5.1--5.3] L8 (CW 4) Th 12 Feb. Lambda calculus. (ps, pdf) [KP 5.1--5.3] L9 (CW 5) Mo 16 Feb. Lambda calculus. PCF. (ps, pdf) Computability via PCF L10 (CW 5) Th 19 Feb. PCF. (ps, pdf) Computability via PCF L11 (CW 6) Mo 23 Feb. PCF. Computability via PCF. (ps, pdf) Computability via PCF L12 (CW 6) Th 26 Feb. Computability via PCF. Turing Machines. (ps, pdf) Computability via PCF, [KP 6.2] L13 (CW 7) Mo 1 Mar. Turing Machines. Halting problem on Turing Machines. (ps, pdf) [KP 6.2] L14 (CW 7) Th 4 Mar. Exams. Exam [KP] refers to the relevant part in the course book Beräkningsbarhet för dataloger: Från lambda till P;
Exercises Classes in Big Groups:
Wednesdays 13.15 - 15 in ES52 by Kristofer Johannisson;
Fridays 10 - 11.45 in EL42 by Nils Anders Danielsson.You can attend the group that suits you best as long as the 2 groups have about the same amount of students. To have an idea about how each group will function, here are the words each assistant has written on himself:
Kristofer Johannisson (Wednesdays 13.15 - 15, ES52): My style could be described as "KJ's sessions will be more traditional: KJ mumbling to the blackboard and/or himself while the students are free to take a nap.". Politically correct version: "KJ's sessions will be more traditional, where most of the time will be devoted to presenting solutions to and answering questions about the problems in front of the whole class."
Nils Anders Danielsson (Fridays 10 - 11.45, EL42): In Nils Anders' sessions you will mostly solve exercises in small groups. Some material will be discussed in the big group, mainly the tricky parts. However, the aim is for you to learn by having fruitful discussions in the smaller groups.
Don't worry if you don't have time to finish all exercises in a certain session; after each part of the course the solutions can be downloaded from the web page.
Feel free to suggest improved forms of teaching.Exercises Classes in Small Groups:
Mondays 15.15 - 17 in Ideläran rooms 4 to 12 (inclusive) (second floor) though not on Monday the 19th of January.
See the link to the schema of D2/LP3.The proposal of distribution of students into the different rooms in Ideläran is as follows:
Room Students with lab accounts 4 grund-1 to grund-8 5 grund-9 to grund-16 6 grund-17 to grund-24 7 grund-25 to grund-32 8 grund-33 to grund-40 9 grund-41 to grund-48 10 grund-49 to grund-56 11 grund-57 to grund-64 12 grund-65 to the end You can change groups if you wish provided that the groups are more or less equally distributed.
Exercises and Solutions
Grundläggande datalogi för D2 - Övningar: Complete set of exercises (ps, pdf).
Solutions to Grundläggande datalogi för D2 - Övningar: Solutions to exercises 1-3 (text), solutions to exercises 4 (text), solutions to exercises 5-6 (text), solutions to exercises 7 (text), solutions to exercises 8 (text), solutions to exercises 9 (text), solutions to exercises 10 (text), solutions to exercises 11 (text).
Obs:They will be available after the corresponding exercises have been discussed in the exercise groups.
Back to contents.
During the course I will make 5 assignments available; most of them are programming assignments. They are not obligatory but they will give extra points on the exams in March and August 2004 for those whose assignments were approved. Each approved assignment gives one extra point, provided it was submitted (and approved) in time.Back to contents.Assignments are to be solved individually or in groups of 2 students. The latter is actually preferred. You will choose your partner yourself. You can choose a different partner for each assignment and alternate between working alone/working with a partner.
Assignments
- Assignment 1: Induction, Functions and Countable Sets: (ps, pdf);
- Assignment 2: An Interpreter for Primitive Recursive Functions: (ps, pdf);
- Assignment 3: Translating Lambda-terms into Combinators: (ps, pdf);
- Assignment 4: Implementing PCF in Haskell: (ps, pdf);
- Assignment 5: Computable Functions: (ps, pdf).
Before you start doing any assignment, read these lines about "fusk"!
Submission Dates
Available on First Submission First Return Last Submission Last Return Corrected by Assignment 1 23 January 6 February 13 February 20 February 27 February Nils Anders Danielsson Assignment 2 30 January 13 February 20 February 27 February 5 March Kristofer Johannisson Assignment 3 6 February 20 February 27 February 5 March 12 March Ana Bove Assignment 4 13 February 27 February 5 March 19 March* 26 March* Nils Anders Danielsson Assignment 5 20 February 5 March 12 March 19 March 26 March Kristofer Johannisson The dates marked with "*" have been changed (on March 5th).
In order to obtain the bonus point corresponding to an assignment, you should submit the corrected version of it at the latest on the "Last Submission" date for the assignment. Observe that you only have one return per assignment! If the assignment is not passed on the second submission you will not obtain the bonus point corresponding to that particular assignment. Notice also that you get one point for each passed assignment and that you do not need to do all the assignments to get points.
Submission Instructions
- For non programming assignments (case of assignment 1 so far), the submission is done manually. Clip all the papers concerning your solution together with a lab submission form (the same one you use for actual labs) filled with your name(s) and personal number(s) in the lab cabinet (located in the 6th floor "vid Linsen"). The box reserved for the course is tagged "Grundläggande datalogi". The corrected assignments will be placed to the right of the small door where you submitted the lab.
- We will use the Fire lab submission system, where you upload your files to our server using a web interface.
For more details in programming submission read this page (lab submission).When resubmitting an assignment you should followed the same procedure as you followed for the first submission. If the submission is done manually, make sure to include the papers with the previous corrections in order to facilitate the revision.
I will distribute the lab accounts during the first 2 lectures of the course. If for any reason you didn't get a lab account after the first week of the course, you should contact me.Instructions for the Lab Accounts
Below you can find some instructions concerning lab accounts:
- To get a lab account you should fill your name and person number in the form I will supply. When you have done this, you will get the name of the account and its password, which you should keep in a safe place. You are strongly encouraged to change the password when you first log-in into the account;
- If you have any problems with the account you should contact the Helpdesken, which is opened from Mondays to Friday from 10 to 16, email helpdesk@mdstud.chalmers.se;
- To get more quota/pquota you should contact me;
Back to contents.
During the 7 weeks of the course, there will be 6 lab slots assigned to this course, all of them in lab room ED6225B in the E-building, CTH. It will be possible to book a computer on those times. The booking lists can be found on the notice board under café linsen. Make sure you book only one computer per slot!Back to contents.The time slots reserved for the course are:
During the times marked with "*", Kristofer Johannisson would be available in his room (6122) if you have any questions.
- Monday 17-19
- Tuesday* 10-12
- Wednesday 8-10
- Thursday 15-17
- Thursday 17-19
- Friday# 15-17
During the times marked with "#", Nils Anders Danielsson would be available in his room (6453) if you have any questions.
Here you can see all the reserved times in doc and html styles.
The exam is scheduled for Friday the 12th of March, 14.15-18.15 in the M building (check this page and this other to confirm!).
The only material you are allowed to take with you to the exam is the book Haskell: The Craft of Functional Programming by Simon Thompson.Exam results in courses held by Computing Science will from now on be published on a board straight beneath "Café Linsen"
During the course there should be at least 3 evaluation meeting between the responsible of the course (Ana Bove) and 5 student representatives.
The student representative for this course are:To email them with any comment you might have on the course, add "@dtek.chalmers.se" after the word between brackets.
- Vilhelm Verendel (vive);
- Prarthanaa Khokar (prarthan);
- David Waern (davve);
- David Gullmarsvik (gullet);
- Peter Holmdahl (pethol).
You are also welcome to email me bove(at)cs(dot)chalmers(dot)se) any comment you might have.The first meeting took place on Thursday 29th January. To read what has been discussed in the meeting click here: meeting protocol (txt) by Vilhelm Verendel (student representative).
The second meeting took place on Thursday 12th February. To read what has been discussed in the meeting click here: meeting protocol (txt) by Vilhelm Verendel (student representative).
The third and last meeting took place on Thursday 6th May. To read what has been discussed in the meeting click here: meeting protocol (txt) by David Waern (student representative).
Back to contents.
Page last modified on October 20th, 2004 by Ana Bove.