GEM 1501 - Problem Solving For Computing

Brief Description

This course the opportunities and shortcomings of today's computer technology for solving practical problems. After a exploration of problems and computer-based problem solving, the student will be exposed to basic principles of algorithms, data structures and programming. An introduction to general problem solving techniques such as divide-and-conquer is complemented by a discussion of correctness and efficiency of algorithms. The course emphasizes the limitations of computers for problem solving, covering undecidability, intractibility and NP-completeness and the practical consequences of these shortcomings.

Topics

  1. What are problems?
  2. Algorithms and data
  3. Programming languages
  4. Introduction to algorithmic methods
  5. Correctness of algorithms
  6. Efficiency of algorithms
  7. Algorithmic methods
  8. Limitations of computers (I): Intractable problems
  9. Limitations of computers (II): NP-complete problems
  10. Excursion: Public-key encryption
  11. Limitiations of computers (III): Undecidable problems

Course Material

The textbook for this course is Algorithmics - The Spirit of Computing by David Harel.

The course material is augmented with selected material from Computers Ltd. by David Harel as well as notes on particular problem solving techniques.

Date Subject Slides Notes Additional Material
8/1 Course introduction; What problems? PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Were distributed in class (Part I of textbook "Algorithmics") Examples given in the notes are from The Chess Mysteries of Sherlock Homes, Raymond Smullyan, and from Consciousness, Susan Blackmore. The graph problem and the number problem given in class are from Which way did the bicycle go? by D.E. Konhauser, D. Velleman, and S. Wagon.
22/1 Algorithmics PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Were distributed in class (Part II of textbook "Algorithmics") -
29/1 Programming Languages PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Chapter 3 in textbook "Algorithmics"; material on Language Processing is available in Additional Notes on Lecture 03
 For the part "Data Structures in Oz", see Chapters 1 through 3 in Tutorial of Oz.
5/2 Algorithmic Methods PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Chapter 4 in textbook "Algorithmics" -
12/2 Correctness and Efficiency of Algorithms PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Chapters 5 and 6 in textbook "Algorithmics" -
19/2 Inefficiency and Intractability PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Chapter 7 in textbook "Algorithmics" -
26/2 Undecidability and Midterm PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Chapter 8 in textbook "Algorithmics" -
4/3 Undecidability; Universality (I) PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Chapter 8 and beginning of Chapter 9 in textbook "Algorithmics" -
11/3 Universality (II) PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Chapter Chapter 9 in textbook "Algorithmics" -
18/3 Parallelism and Concurrency PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Chapter Chapter 10 in textbook "Algorithmics" -
25/3 Probabilistic Algorithms PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Chapter Chapter 11 in textbook "Algorithmics" -
1/4 Algorithmic Intelligence? PDF in color
PDF in color, 4 up
PDF in b/w PDF in b/w, 4 up
 Chapter Chapter 12 in textbook "Algorithmics" -

Assignments and Self-Assessments

Assessments and assignments are distributed online in the table below.

Date handed out Time due Assessment/Assignment Solution
8/1 14/1 01.ps (PostScript)
01.pdf (PDF) 		to be discussed in first lab session
20/1 no formal submission 02.ps (PostScript)
02.pdf (PDF) 		to be discussed in first lab session
27/1 no formal submission During the lab session in the week starting on 26/1, we work through a tutorial introduction to the basics features of the Oz/Mozart system. See Demo.oz for the demo code. to be discussed in first lab session
29/1 no formal submission The goal of the lab session in the week starting on 2/2 is to understand data structures in Oz as presented in the lectures. As preparation for the lab, please work through the first three chapters of the Tutorial of Oz. The lab used as an example the problem of "Towers of Hanoi". Please play with the example program Towers.oz.
9/2 no formal submission The goal of the lab session in the week starting on 9/2 is to understand functions, expressions and recursion in Oz. The lab used as an example the program "Merge Sort". As a preparation for your own program for Merge Sort in Oz, you may want to look at the example program MergeSort.oz.
16/2 no formal submission The goal of the lab session in the week starting on 16/2 is to enhance the understanding of algorithms in Oz. The lab used as an example the program "Money". A sample solution for this program is given in Money.oz.
1/3 Submit via email before Monday 15/3, 12 noon. 03.ps (PostScript)
03.pdf (PDF)
Take a look at some sample data (from the book, page 88) at Weary.oz
 Sample solution at Weary.oz
31/3 no formal submission 04.ps (PostScript)
04.pdf (PDF)
 To be discussed in the last lab session (week of 29/3 - 2/4)

Other Course Information

Prerequisites
Instructor
Martin Henz, consultation: Whenever you want to see me, please propose a meeting time by email to henz@comp.nus.edu.sg.
Teaching Assistants
not yet available
Lectures
14 sessions, 2 hrs/wk, time: Thursday 12 noon - 2 pm, place: SOC1, LT34,
first lecture: 8/1/2004
Lab Sessions
Weekly lab sessions in PC LAB1, SOC1, Level 8, the following three slots:
The lab sessions start in the week of January 26-January 31.
Textbook
Algorithmics—The Spirit of Computing, by David Harel. The book will arrive in the Science Co-op bookstore the latest the third week of January 2004 (as promissed by Co-op).
The course material is augmented with selected material from Computers Ltd., by David Harel , and other material distributed in class.
Assessments and Assignments
One assessment/assignment will usually be given out each week. Assessments serve for students to assess their own understanding of the material. Assessments will not be marked. They will be discussed during lab sessions on student demand.
Discussion group
An general IVLE discussion group is set up for GEM1501. There is also a special discussion group for every topic covered.
Midterm Exam
The midterm exam was on 26/2/2004, 1:00-1:45, in LT34. It was an open-book, multiple choice exam. Any printed and written material was allowed.

Here are the questions and answers.

Final Examination
not available yet

Martin Henz