Manual for the course Computability and Complexity

Tags: Problem solving in groups, Course material, practicals, course website, problem set, quiz, computer science students, cover sheet, teaching assistants, Computability, pushdown automata, central aim
Content: Manual for the course Computability and Complexity Hans HuЁttel 30th August 2004
1 This manual is very important!
2 Aims of the course
3 course material
4 The format of the course and its aims
4.1 Problem Solving in groups is far from ideal . . . . . . . . . . . . . 3
4.2 The 'half life' of knowledge is too short . . . . . . . . . . . . . . . 3
4.3 Many students should improve their work discipline . . . . . . . . 4
4.4 Improving assessment skills . . . . . . . . . . . . . . . . . . . . . 4
5 Teaching and training
5.1 A short story about football . . . . . . . . . . . . . . . . . . . . . 4
5.2 Formative evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 5
6 A closer look at a session
6.1 Students that participate in practicals . . . . . . . . . . . . . . . 6 6.2 Students that do notE^participate in practicals . . . . . . . . . . . 6
7 Practical matters
8 Other activities of a session
8.1 Lectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
8.2 Quiz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
9 Frequently asked questions
1 This manual is very important! For this course I have chosen a format which is radically different from other courses taught at the present semester (and in general). It is therefore very important that you read this manual thoroughly so that you do not get any unpleasant surprises later on. This is also very much the case for students who are taking this course for a second or third time. Please also visit the course website 2 Aims of the course The formal aim of the course is to ensure that The student obtains knowledge of fundaMental models of computability and the known limitations of what is computable in theory and in practice. This is a mathematically oriented course on the Theory of Computation. Some of you will already have come across related courses that introduce models of computation such as finite-state automata, pushdown automata and contextfree grammars. Computability and Complexity is about a general modelE^of algorithms, the Turing machine, and the many results concerning what algorithms can and (especially) cannot do. To some extent, this course requires knowledge of finite-state automata, pushdown automata and context-free grammars. Unfortunately not all of you may have these prerequisites. I will try to compensate for this (see below). 3 Course material The textbook of the course is Michael Sipser. Introduction to the Theory of Computation, PWS Publishing. This book, referred to as ITTTOC, can be bought in the university bookshop in the A building. I have also written a short note for one of the sessions. This note can be downloaded from the website of the course. 2
4 The format of the course and its aims Most courses that I know of consist of a practical, where students work on solving selected problems, and a lecture where the lecturer of the course gives an overview of a particular topic. My course has practicals and lectures, too, but the practicals are radically different. I would like to achieve the following goals: 1. Students should learn the subject in such a way that it becomes a permanent part of their knowledge. 2. Students should improve their skills w.r.t. assessing themselves and others. 3. Students should discover that a regular and substantial effort is the best method for learning the subject such that the subject becomes a permanent part of their knowledge. 4. Students should discover that the practicals are the most important part of the course. 5. Students should discover that a regular and substantial effort throughout the course is the best way of preparing for the examination. Here is what we do: · Students work on solving a small number of select problems during the week leading up to the next session. · For the actual session (usually a Friday), the plan is always the following 8.40 Deadline for handing in solutions. 8.45-10.15 Practical, that consists in commenting solutions made by other students. 12.30 Deadline for handing in comments. 12.30-12.40 Quiz in lecture theatre. 12.40-14.10 Lecture about new material. 4.1 Problem solving in groups is far from ideal Ever since I first taught a course at Aalborg University I have advocated the standard format of practicals, namely that students should solve problems in groups ­ normally these are the project groups, since these are there anyway. However, I have discovered a number of problems with the format: 3
· Many groups have students that are very active and others that are passive onlookers. Being passive is too tempting and too easy; if others are active, being passive usually does not cause any problems. The group format therefore becomes a hindrance to the central aim of a practical ­ that everyone should learn to practice their subject. · In some groups, students solve problems on their own. If they communicate, they do not do so in a systematic way, nor do they get any systematic feedback concerning their solutions. · Many students wrongly perceive the practicals as being less important than the lectures. Many students think of 'real teaching' as any teaching activity where the teacher is always present. During a practical, the teacher is not always around and therefore it becomes tempting to partake in activities not related to the course (e.g. working on the group project). · Det er svжrt at sidde og fordybe sig, hvis man er mange sammen. Man er sammen med de samme mennesker, man ser i projektsammenhжng, og de samme uformelle pauser og snakkestunder kommer til at fylde uforholdsmжssigt meget i den korte шvelsestid. It is high time that we try to find a better alternativ. 4.2 The 'half life' of knowledge is too short There is plenty of evidence that students forget what they have been taught at an alarming rate. For instance, British research has shown that a large group of third-year maths undergraduates had serious problems answers a number of standard questions from their first-year courses.En del hel undersшgelser viser desvжrre at kundskaber i de fag. Many of them remembered nothing or very little. [1]. my experience is similar. It is strange to meet Computer Science students working on their Dat 6 project who remember nothing from their Dat 2 courses. The cause of this apparent paradox seems to be that many students only devote a concentrated effort to the course material during the last few days leading up to the exam. However, the primary aim of the course is notE^that one passes ­ it is that you learn. If you have learned, passing becomes much less of an effort. 4.3 Many students should improve their work discipline I recently made an anonymous survey of another course. I asked each student how much time she spent preparing for a session. About half of the students replied that they spent less than half an hour. 4
4.4 Improving assessment skills Very often, lecturers and Teaching Assistants are asked by students if a solution is correct. Such questions are natural and we are of course happy to answer them. On the other hand, there comes a day when the lecturer and the teaching assistants are no longer there to help. The students have graduated and now hold jobs where they themselves have to find out if their solutions are correct. The teaching format should therefore help each student assess the quality of a proposed solution. 5 Teaching and training A central aim of all teaching is that the student obtain sufficient knowledge for us to conclude that the student "knows the subject" and therefore "passes". In other contexts, this is also central. The Norwegian researcher Per Lauv°as has pointed out [3, 2] that we can in fact learn a lot about teaching from sports. 5.1 A short story about football Below is a (complety fictitious) store from the world of sports: I have a deep fascination of football, so I have joined a local football club. My first match will be in June; it will determine if I can get a permanent place on their team. However, I do not attend training. The weather is cold in February and besides, I don't feel very fit. Sometimes I do show up, though. I set on a bench and watch the other players. I listen to the comments from the coach and, occasionally, I take notes. Sometimes I watch football on TV but always switch off when the playing gets too fast and intense. Five days before the June match I start learning the rules and I decide to attend training. However, playing football is really quite hard and I always end up losing my breath ­ after all, I am not used to running around for long periods of time. On the day of the June match I am still not quite sure about the off-side rule and I profoundly hope that the match does not evolve in such a way that someone will ask me to take a penalty kick. How big is my chance of getting a permanent place on the team? Most people would probably agree that my chances are extremely slight. However, one often observes similar behaviour from many students taking a course. 5
5.2 Formative evaluation There are two essential aspects of all training in sports: 1. You train regularly and for longer periods of time. 2. You get frequent comments from the coach and from others participating in the training so that you can adjust your training efforts to improve your weak sides as much as possible. A similar systematic approach to practicals will help ensure that students learn things well and that their knowledge does not degrade as rapidly. The type of peer assessment suggested here ­ that students get comments from lecturers and from other students and that these comments are meant to help them learn more ­ is also known in teaching circles as formative evaluation. 6 A closer look at a session As I have already explained briefly, each session is structured as follows: · Students work individuallyE^on solving selected problems in the days before the session. The solutions must be in writing. If you have difficulties solving a particular problem, you must try to explain where the difficulties are. I have made a set of guidelines that students should use when writing their solutions. · Students should hand in their solutions no later than 8.40 on the day of the session. The teaching assistants will re-distribute the solutions in such a way that solutions remain anonymous to others and such that no students get their own solutions. · Those students who have handed in solutions, spend the time from 8.45 to 10.10 in the group rooms two by twoE^(or three, if the Number of students in a group is odd) commenting solutions. Students must have a fixed partner from the same group. The teaching assistants will help them with this task. Comments must be substantial and comment on 1. What is correct and incorrect. 2. What is not clear from the solution. 3. Good aspects of the solution. 4. Whether it is possible to understand the line of reasoning employed in the solution. 5. Whether the terminology has been used correctly. 6
6. Advice for improvement, based on the solution.indhold. I have made a set of guidelines that should help ensure that all students give good and substantial comments. If there is any time left, students can work on solving new problems suggested by the teaching assistant. The group room is a designated teaching facility. Students that did not hand in solutions are not allowed to sit in the group room during the practical. · At the end of the practical students hand in their comments. This is done in the lecture theatre; a box is provided for solutions from each group. · After the practical there will be a 90 minute lecture (3 times 30 minutes) at 10.15. This lecture will cover new material. Before the lecture there will be a short, anonymous quiz which takes no more than 10 minutes. · After the lecture, all commented solutions are returned to students along with an official solution provided by me. 6.1 Students that participate in practicals The goal is that most (hopefully all) students participate in the practical. If you participate in all practicals1 (i.e. in the entire formative evaluation process) you will get a reduced exam syllabus. The teaching assistants and I will therefore record who has handed in solutions. Students who participate in practicals will get an official solution and can have their solutions commented on by a teaching assistant (or by me). Each of us can handle two solutions, chosen on a first-come-first-served basis. 6.2 Students that do notE^participate in practicals If you do not participate in all the practicals, you will get a full exam syllabus consisting of all the material that has been covered throughout the course. Moreover, there will be no assistance from teaching assistants. Some students may be unable to attend all practicals, either because they have to follow other required courses at another semester or because they live far away. In this case, students may obtain the same syllabus reduction by handing in solutions to 7 somewhat larger problem sets. A requirement is that the solutions are approved (i.e. deemed sufficiently correct) by me. 7 Practical matters · Every group has its own box marked with the number of the group. The box is placed outside Ulla's office. 1With the usual exemptions for those who fall ill etc. 7
· Solutions must be individual and must be handed in no later than 8.40 on the day of the session. · Solutions must be hand-written and placed in a transparent A4 plastic pocket. A separate cover sheet must provide the following details: ­ Full name ­ Group number ­ University e-mail address This cover sheet can be obtained from the course website. The solution itself must not contain any such information, as anonymity is of paramount importance. 8 Other activities of a session There are a number of other activities during a session. 8.1 Lectures The lecture is an Oral Presentation of 3 times 30 minutes during which I give an overview of the text on which the next session is based. I use blackboard and chalk, i.e. no slides. 8.2 Quiz The quiz is an anonymous test with a few short questions that cover central aspects of the session text. The correct answers will be published on the course website after the quiz. The aims of the quiz are twofold: Firstly, you can use the quiz for finding out how well you have understood the topic of today's session. Secondly, I can use the answers that I get to find out if the session has achied its goal. In other words, the quiz is also part of the formative evaluation. 9 Frequently asked questions The course presumes some knowledge of formal language theory. I have never had a course on this. What should I do? During the first month of the course you should read chapters 1 and 2 of ITTTOC. I have made a special additional problem set which you may hand in. The deadline is monday 4 October 12.00. Please note: This problem set is not related to the offer concerning syllabus reduction. 8
What should I do if I fall ill or something serious happens that prevents me from attending the practical? If you fall ill, you should of course not be punished by not being able to claim a syllabus reduction. Illness must be documented by providing me with a signed statement from your medical doctor, following the same rules that apply for exams. In other serious matters, please ask me. If you are absent for a long period of time, you should consider handing in the 7 special problem sets instead. Can we collaborate on solutions? The purpose of the practical is to help the student improve his/her learning. The answer is therefore no. We cannot control whether you have indeed collaborated but if teaching assistants or students, who comments solutions, discover that some solutions look remarkably similar, we will contact the authors. Collaboration, copying solutions from books or WWW pages is cheating. If we have good reason to believe that someone is cheating they will not be able to get a syllabus reduction. What should I do if I cannot complete the solution of problem? This is not a problem ­ the purpose of the practical is to help you learn! Complete as much as you can, describe your line of reasoning and exactly where and why you got stuck. The guidelines for solutions should help you here. References [1] Johnston Anderson, Keith Austin, Tony Barnard, Janet Jagger. Do ThirdYear Mathematics Undergraduates know what they are supposed to know?, teaching and learning Undergraduate Mathematics,, Newsletter No.8, March 1998. [2] Per Lauv°as. Mappevinden bl°aser i nord ­ men i hvilken retning?, IPN-Nyt nr. 12, 2003. [3] Per Lauv°as. Vurderingsformer i Kvalitetsreformen: Implementeres intensjonene eller er reformen havnet p°a feil spor?, foredrag i NRШA, 2003. 9

File: manual-for-the-course-computability-and-complexity.pdf
Published: Mon Aug 30 21:27:00 2004
Pages: 9
File size: 0.1 Mb

, pages, 0 Mb
Copyright © 2018