GEM 1501 - Problem Solving For Computing
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.
- What are problems?
- Algorithms and data
- Programming languages
- Introduction to algorithmic methods
- Correctness of algorithms
- Efficiency of algorithms
- Algorithmic methods
- Divide-and-conquer
- Greedy algorithms
- Dynamic programming
- Traversal/search
- Limitations of computers (I): Intractable and NP-complete problems
- Limitiations of computers (II): Undecidable problems
- Simulation and Universality
- Parallel Computing
- Probablistic Computing
- Is there artificial intelligence
The students can make up to 100 marks in the course. They are
obtainable as follows:
- 50 marks: Final examination.
- 12 marks: Midterm examination 1 on Wednesday 29.02.2012
(lecture split into 60 min lecture + 30 min test).
- 12 marks: Midterm examination 2 on Wednesday 04.04.2012
(lecture split into 60 min lecture + 30 min test).
- 26 marks: Laboratory Assignments: Each assignments counts 1 mark;
complete 26 out of 28 assignments to get full marks.
For more information, see the
Assignment Section.
- Assignments Deadline for assignments 0-5 is Friday 17.02.2012;
for assignments 6-15 is Friday 23.03.2012; for assignments
16-27 is Friday 13.04.2012. Each time in the corresponding
laboratories. Please use laboratories regularly to have the
assignments ready in time.
Note that all examinations are closed book examinations. No material
is permitted. The midterm examinations and the final examinations will
be of a bit different format than in the previous years;
solutions
to old examinations can be found on the internet.
- Lectures:
The lecture is 2 hours per week on Wednesdays, 12.00-14.00h in
the Seminar Room next to LT19 (SR@LT19). Note that this venue differs
from the previous years.
- Laboratory Sessions:
Laboratory sessions will be held in small groups. There are two
groups on Friday 12.00-14.00h and Friday 14.00-16.00h.
The room is Programming Lab 5 (COM1#B-10). The
laboratory sessions start in Week 3.
You should regularly participate the laboratory sessions and
try to hand in as many assignments as to can. For rules of
marking assignments, see above.
As there are several laboratory groups per week, a student can
choose always the one which suits most. Weak students are
permitted to come to several sessions if they need this to
catch up. Nevertheless, students have to register for exactly
one of the sessions.
- Locations:
When clicking on the below maps, do enlargement "(+)" twice after
having loaded the map.
The seminar room
SR@LT19 is siutated at the side of the
cantine between NUS Buisiness School BIZ2 and School of Computing COM2
next to the lecture theatre LT19. The building
COM1
is the main building of the
School of Computing.
There is the building COM2 directly next to it. The
main entrance to COM1 is from the car park CP13 and from the entrance
there are directions how to reach the basement and the programming labs in it.
Everyone receives a unix account at the computer
sunfire.comp.nus.edu.sg. There is a new
procedure which permits students to create the account
by themselves.
You can apply on this webpage to
request a new account.
This webpage also tells what
to do in the case that the password is forgotten.
Please note that the password-input of the School of Computing
can process only passwords of up to 8 characters. If your password
is longer and you cannot log in, please change the password to a
shorter one and try again. In the case that you still have problems,
you can either contact Frank Stephan (fstephan@comp.nus.edu.sg) or
the Helpdesk of the School of Computing (helpdesk@comp.nus.edu.sg,
COM1#01-06).
The main purpose of the accounts is to do the assignments. If you
want to use your own laptop computer and find a way to display and print
webpages, this is also ok. But then you have to rely on yourself
for technical questions concerning your operating system.
The textbook for this course is
Algorithmics - The Spirit of Computing, Third Edition
by David Harel with Yishai Feldman,
Addison Wesley, 2004. See this link for
more information.
The programming language used for this year's exercises is Java Script
and the corresponding textbook is
Java Script - A Beginner's Guide, Second Edition
by John Pollock, McGraw-Hill/Osborne, 2004.
The course material is augmented with selected material from
Computers Ltd.
by David Harel as well as notes on particular problem solving techniques.
Links for further information.
Editor PICO,
EDITOR VI,
Hyper Text
Meta Language (HTML) and
Java Script.
If you use Editor PICO, please make the window in which it runs large
enough; otherwise the editor makes linebreaks into the text which cause
Java Script syntax errors.
A short introduction to Java Script
for GEM1501 is available. This introduction is of course
not as perfect as a text book but it should contain the most important
information. Suggestions for improvement are welcome: Send them to
fstephan@comp.nus.edu.sg. Please read this introduction prior to the
first laboratory session.
Warning: Slides are detailed but not self-explanatory. The lecture
is only based on Harel's book, it is not identical with it. These
two facts mean the following:
- A lot of information is put onto the slides. For this reason,
you do not have to keep so much notes as you would have to do
without slides. Furthermore, as a lot of the material from
the lecture is written down onto slides, there are approximately
50 slides per lecture.
- Although the slides are comprehensive, not all information is
there. It is recommended to attend the lectures in order to
understand those things which are only explained orally and
not written down. Slides are not lecture notes, but an auxiliary
medium used during teaching a class.
- The lectures are based on the book of Harel, but not identical
with it. So some material might be added and many other things
are omitted.
- Java Script is added to Harel's book as it is good not only to
learn the content on a theoretical level but also to apply the
knowledge by writing easy programs; better said, by completing
such programs. There is an
Intorduction
to Java Script
and you should make yourself familiar with the content
of this page prior to the start of the laboratory sessions.
The first assignments are just to learn some minimum knowledge
of Java Script.
The below material will be updated. Note that the dates in the
year 2012 differ by a few days from those in year 2011.
The slides will be mainly based on the old ones, but some information
and material might be modified. The new slides will always carry
the date 2012, so all slides referring to 2011 are old.
The sample programs will be modified only if really needed.
These slides are viewable only under some but not all versions of
Adobe Acrobat Viewer. If you have problems, try to use GSView of the company
Ghostgum
in place of Adobe (the viewer GSView can read both, ps-files and pdf-files);
for Apple computers, try to convert the ps-file with the Previewer into
an Apple-pdf-file.
Lecture 1 (11.01.2012): What Problems? -
ps-file;
pdf-file;
Travelling
Salesman Tour through all Swedish towns;
Euclidian Algorithm;
Harel book
Lecture 1 is related to Chapter 1 of the textbook "Algorithmics".
Lecture 2 (18.01.2011): Algorithmics -
ps-file;
pdf-file.
Mechanical loom;
Punch card;
Fibonacci function
.
Lecture 3 (25.01.2012): Programming Languages and Data Types -
ps-file;
pdf-file;
Salary Addition with Datatypes Array and Record;
List
of programming languages on Wikipedia.
Lectures 2 and 3 are both based on Chapters 2 and 3 of
the textbook "Algorithmics". Since the laboratory sessions
require knowledge of the programming language Java Script,
algorithms and programming languages are introduced in parallel.
Lecture 4 (01.02.2012): Algorithmic Methods -
ps-file;
pdf-file;
Finding Maximum;
Mergesort;
Pivotsort;
Dynamic Programming.
Lecture 4 is based on Chapter 4 of
the textbook "Algorithmics".
Lecture 5 (08.02.2012): Correctness and Efficiency -
pdf-file;
(older slides: ps-file;
pdf-file.)
Lecture 5 is based on Chapters 5 and 6 of the textbook "Algorithmics".
Lecture 6 (15.02.2012): Inefficiency and Intractability -
ps-file;
pdf-file;
Satisfiability Problem;
Computing Powers and Factorials;
Monkey Puzzle.
Lecture 6 is based on Chapter 7 of
the textbook "Algorithmics".
Lecture 7 (29.02.2012): Selected topics of Java Script and
First Midterm Examination -
ps-file;
pdf-file;
Buttons and Windows;
Code Optimization.
First half lecture on selected topics on Java Script, second half
first midterm examination.
Lecture 8 (07.03.2012): Noncomputability and Undecidability -
ps-file;
pdf-file.
Lecture 8 is based on Chapter 8 of the textbook "Algorithmics".
Lecture 9 (14.03.2012): Universality -
ps-file;
pdf-file;
Turing machine examples (interactive
and offline) from
the lecture.
Lecture 9 is based on Chapter 9 of the textbook "Algorithmics".
Lecture 10 (21.03.2012): Parallelism and Concurrency -
pdf-file;
(older slides at ps-file;
pdf-file.)
Lecture 10 is based on Chapter 10 of the textbook "Algorithmics".
Lecture 11 (28.03.2012): Probabilistic Algorithms -
pdf-file;
(older slides ps-file;
pdf-file;
the quicksort algorithm from the lecture.)
Lecture 11 is based on Chapters 11 and 12 of the textbook "Algorithmics".
Lecture 12 (previously 13) (04.04.2012): Algorithmic Intelligence -
pdf-file;
(older slides ps-file;
pdf-file.)
Lecture 12 is based on Chapter 15 of the textbook "Algorithmics".
Second half second midterm examination.
Lecture 13 (previously 12) (11.04.2012): Software Engineering
pdf-file; (older slides ps-file;
pdf-file.
Towers of Hanoi as object.)
Lecture 13 is based on Chapter 13 of the textbook "Algorithmics".
Lecture 14 (11.04.2012): Revision pdf-file;
Deadlines of Assignments: Assignments 0-5 in Laboatory of Week 6
(Fri 17/02/2012), assignments 6-15 in Laboratory of Week 10 (Fri 23/03/2012)
and remaining assignments in Laboratory of the last week (Fri 13/04/2012).
You can work on the assignments in the laboratory sessions.
The goal is to aquire basic programming skills.
For this the programming language Java Script is used so that
you do not need a compiler and can control your results with a browser.
- There are 28 assignments; 6 first assignments to train Java Script
programming skills and 22 further assignments related to topics of
the course which fall into an easier and more difficult group.
- Students may have help for one assignment per laboratory
session and get 1 marks for this assignment, so if you
come regularly you might make 1 marks per session. Besides
one assignment with help, as many further assignments without
help can be handed in per laboratory session.
- Doing n exercises with n < 26 gives n marks, so
students have to do 26 out of 28 assignments to get full marks.
Try at least to get 20 marks by doing exercises 0-19; that is,
by doing the basic exercises and
the medium difficult ones.
It is recommended that you devote two hours a week for learning how to
program in Java Script. In the case that you need assistance in the
laboratory sessions, do not hesitate to ask for it.
Basic exercises to train programming in Java Script.
- Analyzing numbers
(Exercise to correct syntax errors).
- Java Script Keywords.
- Easy Functions.
- For-Loops and While-Loops.
- Outputting Numbers as Words.
- Computing Function Values Iteratively.
Exercises related to the topics of the course.
- Euclid's Algorithm.
- Bubble Sort.
- Towers of Hanoi.
- Digit Hunting.
- Arrays and Records.
- Multiplication Table.
- Mergesort.
- Big O Calculus.
- Binary Search in Mathematics.
- Traveling Salesman on SMRT.
- Finite State Automaton.
- Post's Correspondence Problem.
- Turing Machine and Palindromes.
- Fast Parallel Sorting of 10 Inputs.
Advanced Exercises.
- Computing the determinant of a matrix.
- Playing strategies for Tic Tac Toe.
- Improving the Monkey Puzzle Page.
- Satisfiability and Resolution.
- ATM Money Withdrawl Game.
- Polynomial Time with Counter Automata.
- Multiplying polynomials with as few
multiplications as possible.
- Code breaking - test codes and select
the right one after statistical analysis.
The course mainly follows the one given by
Martin Henz
in 2004 and the slides will be based on his material; his old
slides are available on the
information page for GEM 1501 from 2004
for those who want to have a further source of information on the
material covered in the course.
Nevertheless, the examinations are based on the current material only.
Stéphane Bressan
and
Frank Stephan