Justin Pearson http://user.it.uu.se/~justin/, email: justin.pearson at it.uu.se
Link to Online Evaluation system.
Old exams can be found on Pierre Flener's Webpage it might be good to look at the PK2 exams marked as by the previous instructor (me) for an idea of the style of the exams.
The main objective is to make you familiar with some fundamental principles and methodologies of algorithm and data-structure design and evaluation. We will use the functional programming language Standard ML (SML) as the teaching medium. You will learn when to use each discussed algorithm and data structure, when not to, and what to consider when designing or choosing an algorithm or data structure. The lectures are in English, by the instructor, and have a slight theoretical flavour, but with many examples. Also see the popular-science description of this course.More practice of algorithm and data-structure design (via programming in SML) is acquired through assignments. Several assignments are to be prepared at home, then tried on the computer in labs under assistant supervision, then submitted, and finally graded, but also discussed in lessons by the assistants.
The following two textbooks will be used:Note that PK2 students may replace CLRS by the following textbook:
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Introduction to Algorithms (second edition) (errata)
The MIT Press, 2001
(called CLRS below)
- Michael R. Hansen and Hans Rischel
Introduction to Programming using SML (errata)
Addison-Wesley, 1999
(called HR below)For HR and L, use voucher code ZP016F for free delivery if ordering directly at the Pearson Education publisher. I don't know if this voucher works anymore.
- Anany Levitin
Introduction to the Design & Analysis of Algorithms
Addison-Wesley, 2003
(called L below)
- Dictionary of Algorithms and Data Structures at NIST, USA
- Jeffrey D. Ullman: Elements of ML Programming, second edition, Prentice Hall, 1997
- Lawrence C. Paulson: ML for the Working Programmer, second edition, Cambridge University Press, 1996
- R. Bosworth: Functional Programming Using Standard ML, McGraw Hill, 1995
- M. Felleisen, D.P. Friedman, D. Bibby, and R. Milner: The Little MLer, MIT Press, 1998
- P. Henderson: Functional Programming: Application and Implementation, 1980
- Ch. Reade: Elements of Functional Programming, Addison-Wesley, 1989
- Å. Wikström: Functional Programming Using SML, Prentice Hall, 1987
- Riccardo Pucella: Notes on Programming SML/NJ
- Stephen Gilmore: Programming in Standard ML'97: An On-line Tutorial
- Moscow ML, a light-weight implementation of SML
- MLton, an open-source, whole-program, optimising SML compiler
- Standard ML of New Jersey, an open-source SML compiler with associated libraries, tools, and documentation
- Standard ML of New Jersey: User's Guide
- Standard ML Basis Library
- Philip Wadler: Functional Programming Column at ACM SIGPLAN Notices
- Frequently Asked Questions about ML
To be able to follow the course productively, get practice, and work on the programming assignments, you should have an easily accessible Internet-connected computer with the following software installed: The Unix labs at MIC have this software properly pre-installed. If you plan on using other computers, try to have this software properly installed there before the course starts.
For administrative reasons, the first two-hour-lecture is mandatory: contact the instructor if you cannot make it for some reason, ideally in advance.Attendance at the other lectures is highly recommended, as the essential aspects (in the eyes of the instructor) will be pointed out and as the slides are not self-contained at all: they are only a support for the lectures, but not equivalent to their content.
Programs of the slides (the specifications are on the slides). The lectures include adapted material from Yves Deville, John Hamer, John Morris, Chris Okasaki, and Justin Pearson. Free printed copies of the slides are handed out in the classroom.
- Introduction & Revision (Slides)
(read Chapter 1 of CLRS; also revise Chapters 1-9, 17, and 18 of HR)- Algorithm Analysis 1 (Slides A) (pages 3.28 to 3.36 of Slides B)
(read Chapter 3 of CLRS; you may skip everything about little-oh and little-omega)- Algorithm Analysis 2 & Sorting (Slides A) (Slides B)
(read Chapters 2, 4, and 7 as well as pages 123-126 of CLRS; you may skip everything about invariants as well as Sections 4.4 and 7.3)- Stacks and Queues (pages 6.6 to 6.18 of Slides)
(read pages 197-199 and Section 10.1 of CLRS)- Trees (pages 6.19 to 6.28 of Slides BT) (Slides AVL) (Applet for AVL trees) (Applet for AVL trees)
(read Sections B.5 and 10.4, as well as Chapter 12 of CLRS; you may skip Section 12.4; AVL trees are not covered in CLRS, but in Section 6.3 of L; also revise Chapter 8 of HR)- Heaps (Slides) (Applet for binomial heaps)
(read Chapters 6 and 19 of CLRS; you may skip Section 6.4; binomial heaps are not covered in L)- Hashing (Slides)
(read Chapter 11 of CLRS and self-study Section 11.4; you may skip Sections 11.3.3 and 11.5) More Hashing.pdf- Greedy Algorithms (Slides) (Maundy money)
(read page 370 as well as Sections 16.2 and 16.3 of CLRS; you may skip the proof and everything about dynamic programming)- Graphs (Slides) (Applet for Dijkstra's shortest-paths algorithm)
(read Section B.4, pages 525-526 and 580-587, as well as Sections 22.1, 22.2, and 24.3 of CLRS)- Constraint Processing (Slides A) (Slides B)
(this material is not covered in any of the textbooks)- Conclusion (Slides)
(this material is not covered in any of the textbooks)If you have a pressing question about the lecture material or course organisation, then contact the instructor at a lecture for an immediate answer, but not in his office. You can also contact him at justin.pearson at it.uu.se with a brief description of the issue and suggested time(s) for a meeting that is normally to be held at his office: you will be given an appointment. Only in exceptional cases will an answer be given by email, as email is not an effective teaching medium.
The assistants supervise 5 SML labs and give 5 SML lessons.The AD1 assistant in 2007 is Ruslan Fomkin.
Attendance at the SML labs and SML lessons, and SI lesson is highly recommended (and sometimes mandatory, see the rules below), because without significant, constant practice and feedback, it is provably very hard to prepare properly for any exam.
SML assignments of 2007:
- AD1 assignment 1 of 2007 (lab on 30 Jan, deadline at 08:14 on 02 Feb, lesson on 7 Feb)
- AD1 assignment 2 of 2007 (lab on 06 Feb, deadline at 08:14 on 09 Feb, lesson on 14 Feb)
- AD1 assignment 3 of 2007 (lab on 12 Feb, deadline at 08:14 on 16 Feb, lesson on 21 Feb)
- AD1 assignment 4 of 2007 (lab on 20 Feb, deadline at 08:14 on 23 Feb, lesson on 27 Feb)
- AD1 assignment 5 of 2007 (lab on 02 Mar, deadline at 08:14 on 07 Mar, lesson on 12 Mar)
If you have a pressing question about the SML assignments or infrastructure, then contact your assistant(s) at a lab or lesson for an immediate answer, but not in their office. You can also contact them by email with a brief description of the issue and suggested time(s) for a meeting that is normally to be held at their office: you will be given an appointment. Only in exceptional cases will an answer be given by email, as email is not an effective teaching medium.
Rules about submitting solutions to the SML assignments:
These rules are effective as of 19 Mar 2007. The instructor reserves the right to modify them at any moment, should special circumstances call for this.
- All solutions must be documented in English and submitted via the online course manager system. Use your UpUnet password A. All emailed and hardcopy solutions will be ignored, except in cases of force majeure. All deadlines are hard, except in cases of force majeure, so the course manager only allows the submission of solutions to non-expired deadlines. Grading will only start after a deadline, and will normally be finished within 36 hours, that is before the lesson for that assignment. The content of that lesson may reflect the correct or incorrect aspects of your solution.
- The submission until the first deadline of an assignment of an acceptable solution earns you a godkänd (G) grade for that assignment. If your solution is not acceptable but a serious attempt, then you earn a komplettering (K) grade. If your solution is submitted after the deadline or is not a serious attempt, then you earn an underkänd (U) grade and lose the right to have any further solutions to this assignment graded this academic year. The acceptability and seriousness thresholds are at the discretion of the instructor and the assistants. The acceptability threshold is higher than at the exam, as the aim is to learn and to prepare for the exam. It includes at least correctness, completeness, and compliance with the coding convention (English version) of this course.
- If you get a K grade for an assignment with first deadline D, then you must attend the lesson for that assignment and you may submit an improved solution until normally 7 · 24 hours after D, with exceptions as posted above. If you cannot attend that lesson in a case of force majeure, then let the assistant know the reason by email as early as possible, ideally before that lesson. Note that one objective of a lesson is to tell everything that is needed to prepare an acceptable solution. Note that the current version of the course manager only allows one resubmission until the resubmission deadline. A lesson is also of interest to students who earned a G grade on the discussed assignment, as interesting issues will be raised. An acceptable improved solution earns a G grade for that assignment. An unacceptable, missing, or late improved solution or a missed lesson upon a K grade earns a U grade for that assignment and you lose the right to have any further solutions to this assignment graded this academic year.
- Every solution must be prepared by a group of one or two students. Do not use the group submission feature of the course manager, but submit two identical copies of the solution and clearly indicate who the two students are. Also see the ethics rules of this course.
- Students from previous academic years who have not yet been awarded the credit point(s) for the SML or C assignments should formally re-register via IT kansliet for the course, at the latest on the day is starts, so that they are on the formal course roster and get a course-manager account for the current academic year. They are assigned all the SML and C assignments of the current academic year, under the deadlines and rules of the current academic year.
SML or C assignments from previous academic years:
The SML part of the course has a total of 4 credit points, distributed over an exam and the assignments:The course manager is not automatically creating accounts for every student that is formally registered to the course this academic year (see Uppdok). Such account creation is done by the instructor after the first, mandatory lecture, based on the roll-call performed there and the Uppdok list of confirmed students. So if you do not have a course manager account, it is because you missed the first, mandatory lecture.
- We have individual, closed-book, written exams where calculators are not permitted. Submitted answers must comply with the coding convention and ethics rules of this course. An exam has so-called G questions and VG questions, totalling 70 G points and 30 VG points, respectively. The G questions test the most basic course knowledge and skills that a student should have to a rather high degree in order to pass the course.
No make-up opportunities will be created for near-passes, as the instructor evaluates those cases very carefully before announcing the results.
- For AD1: A mark of at least 49 G points earns 3 credit points and a godkänd (G) passing grade. Any other mark on the G points earns an underkänd (U) failure grade. Earned VG points do normally not compensate for missing G points, while every G point in excess of 49 G points counts as 0.5 VG points. If passing, then a mark of at least 20 VG points earns an upgrade to a väl godkänd (VG) passing grade.
- For PK2: A mark of at least 49 G points earns 3 credit points and a godkänd (3) passing grade. Any other mark on the G points earns an underkänd (U) failure grade. Earned VG points do normally not compensate for missing G points, while every G point in excess of 49 G points counts as 0.5 VG points. If passing, then a mark of at least 26 VG points earns an upgrade to a med beröm godkänd (5) passing grade, and a mark from 11 to 25 VG points earns an upgrade to an icke utan beröm godkänd (4) passing grade.
- For AD1 and PK2: The 1 credit point for the SML assignments is awarded, with a godkänd (G) grade, upon collection of G grades for minimum four of the five SML assignments, including SML assignments 1 and 5, which are thus mandatory.
The course manager is not automatically reporting awarded credit points to Uppdok. Such reporting is done manually by the instructor at the end of the study period, immediately after all the submitted assignment and exam solutions have been graded. The instructor then has no influence over the actual processing speed at IT kansliet. Also, the instructor's ink signature confirming the processed reports is then needed before the points can actually show up on your Uppdok transcript. So be patient and do not complain until at least a month after the official end of the concerned study period.
Exams from previous academic years:
There are no solutions in distributable form for these exams.
- AD1: Aug 2006, May 2006, Mar 2006, Aug 2005, Jun 2005, Mar 2005, Aug 2004, Jun 2004, Mar 2004, exams by the previous instructor
- PK2: Aug 2006, May 2006, Jan 2006, Aug 2005, May 2005, Aug 2004, May 2004, Aug 2003, Jun 2003, exams by the previous instructor: Aug 2002, May 2002, Jan 2002, Aug 2001, Jun 2001, May 2001
Course evaluations are important and should include all opinions, including those of students who have no complaints:Last modified: Tue Sep 4 12:02:48 MEST 2007
- A formal, anonymous, final evaluation of the PK2 course will be conducted in the classroom on tba.