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 18.02.2009
(lecture split into 30 min test + 60 min lecture).
- 12 marks: Midterm examination 2 on Wednesday 08.04.2009
(lecture split into 30 min test + 60 min lecture).
- 26 marks: Laboratory Assignments: The first 24 assignments handed
in carry each one mark; for 26 marks it is necessary to complete
all 28 assignments. For more information, see the
Assignment Section.
- Assignments Deadline for assignments 0-9 is Friday 20.02.2009
and for assignments 10-27 is Friday 17 April 2008, 14:00 hrs.
Note that all examinations are closed book examinations. No material
is permitted. The midterm tests will consist of 12 questions graded
in a "0 or 1 schema", the final examination will consist of 10 questions
consisting of 5 subquestions, each graded in a "0 or 1 schema". A grade 1
for a question requires a correct (or in some cases almost correct) answer.
- Lectures:
The lecture is 2 hours per week on Wednesdays, 12.00-14.00h in
SoC1 Lecture Theatre 34.
- 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 4 (COM1#B-11). The
laboratory sessions start in Week 3 (30.01.2009).
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:
The building SoC1 alias S17 is located opposite to the building S15 on
the Lower Kent Ridge Road and is the
old building of the School of Computing.
The building COM1 is the
new building of the School of Computing.
It is considered as the starting point of a series
of buildings COM1, COM2, COM3, ... while the building SoC1 will be given
up in 2009 or 2010. The main entrence to COM1 is at the place on the
map where the red star is situated 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.
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 2009 differ by one or two days from those in year 2008.
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 2009, so all slides referring to 2008 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 (this viewer 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 (14.01.2009):
ps-file;
pdf-file;
Travelling
Salesman Tour through all Swedish towns;
Euclidian Algorithm.
Lecture 1 is related to Chapter 1 of the textbook "Algorithmics".
Lecture 2 (21.01.2009):
ps-file;
pdf-file.
Lecture 3 (28.01.2009):
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 (04.02.2009):
ps-file;
pdf-file;
Finding Maximum;
Mergesort;
Pivotsort;
Dynamic Programming.
Lecture 4 is based on Chapter 4 of
the textbook "Algorithmics".
Lecture 5 (11.02.2009):
ps-file;
pdf-file.
Lecture 5 is based on Chapters 5 and 6 of the textbook "Algorithmics".
Lecture 6 (18.02.2009):
ps-file;
pdf-file;
Buttons and Windows;
Code Optimization.
First half first midterm, second half selected topics on Java Script.
Lecture 7 (04.03.2009):
ps-file;
pdf-file;
Computing Powers and Factorials;
Monkey Puzzle;
Satisfiability Problem.
Lecture 7 is based on Chapter 7 of
the textbook "Algorithmics".
Lecture 8 (11.03.2009):
ps-file;
pdf-file;
an example of a compressible text is the one of the
Factorial of 5000 generated
by this program.
Lecture 8 is based on Chapter 8 of the textbook "Algorithmics".
Lecture 9 (18.03.2009):
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 (25.03.2009):
ps-file;
pdf-file.
Lecture 10 is based on Chapter 10 of the textbook "Algorithmics".
Lecture 11 (01.04.2009): ps-file;
pdf-file.
Lecture 11 is based on Chapters 11 and 12 of the textbook "Algorithmics".
Lecture 12 (08.04.2009):
ps-file;
pdf-file.
Towers of Hanoi as object.
Lecture 12 is based on Chapter 13 of the textbook "Algorithmics".
First half first midterm, second half lecture.
Lecture 13 (15.04.2009):
ps-file;
pdf-file.
Lecture 13 is based on Chapter 15 of the textbook "Algorithmics".
Note that deadline for the first 10 assignments is the laboratory of
Week 6 and the last 18 assignments is the laboratory of week 13 (Friday
17.04.2009).
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 < 25 gives n marks, so
0 exercises 0 marks, 1 exercise 1 mark, 2 exercises 2 marks, ...,
24 exercises 24 marks. Doing all exercises gives 26 marks.
It is recommended that you devote two hours a week for learning how to
program in Java Script. In the case that you need assitance 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.
Frank Stephan