Tik-76.123 Exercises for foreing students
In order to pass this course, an exam is required. The first possible
exam is held at December 16 (see the exam schedule for more details).
However, exercises are very important part of the course.
That is why a few extra points for the exam are given for those
who have done most of the exercises and are willing to
represent their solutions on the exercise sessions (75%, 60%, 45% and 30%
of exercises done gives 4, 3, 2 and 1 point(s) for the exam, respectively).
Unfortunately, because of the nature of the exercise sessions,
those are given in Finnish only. That means, special arrangements
has made for foreing students.
I have decided to offer an other way to gain those extra points.
That means, I will publish a set of exercises which are picked up
from the text book and foreing students may return their
papers for me using email or snail mail. I will try to choose
those exercises so that they cover most of the course material
(and also those exercises solved on the exercise sessions).
The set of exercises are published here. I try to release 5-7
exercise for every week (about 10-12 weeks time). Returning
a paper for every week is recommended. Some kind of deadlines
will appear after a while (let's say there is at most 1-2 weeks
to return a paper after it's published here).
The text book used is
-
T.Cormen, E.Leiserson, and R.Rivest: Introduction to Algorithms, The MIT
Press & McGraw-Hill Book co., 1990.
Assignment 1 (deadline 5 Oct 1998)
- Problems 1-1: Comparison of running times
- Exercises 2.1-1
- Exercises 2.2-4
- Problems 2-2: Relative asymptotic growths
- Exercises 3.2-1
- Extra exercise: 3.1-3
Assignment 2 (deadline 12 Oct 1998)
- Exercises 5.4-3
- Exercises 23.1-2
- Exercises 23.2-1
- Exercises 23.3-2
- Exercises 23.4-3
- Exercises 23.4-5
- Extra exercise: 5.2-3
Assignment 3 (deadline 14 Oct 1998)
- Exercises 23.4-1
- Exercises 4.1-1
- Exercises 4.1-2
- Exercises 4.2-3
- Exercises 18.1-1
- Exercises 18.1-2
- Extra Exercise: 18.1-3
Assignment 4 (deadline 21 Oct 1998)
- Exercises 8.4-1
- Exercises 18.2-2
- Exercises 18.3-2
- Exercises 18.4-3
Assignment 5 (at least 5 points) (deadline 2 Dec 1998)
Write an essey (2 to 4 typed pages) on Self-adjusting search trees.
Cover at least the following topics
- splaying,
- searching,
- insertion,
- deletion,
- splitting,
- joining,
- amortized analysis and
- comparison to AVL- and red-black -trees.
Splay trees are described in a number of texts and papers
-
"Fundamentals of data structures in C", Horowitz, Sahni,
and Anderson-Freed, Computer Science Press, pp 542-547.
-
"Data Structures and Their Algorithms", Lewis and Denenberg,
Harper Collins, 1991, pp 243-251.
-
"Self-adjusting Binary Search Trees" Sleator and Tarjan,
JACM Volume 32, No 3, July 1985, pp 652-686.
-
"Data Structure and Algorithm Analysis", Mark Weiss,
Benjamin Cummins, 1992, pp 119-130.
-
"Data Structures, Algorithms, and Performance", Derick Wood,
Addison-Wesley, 1993, pp 367-375.
Assignment 6 (deadline 2 Nov 1998)
- Give an efficient algorithm to compute binomial coefficients.
Analyze your algorithm. (Hint. dynamic programming)
- Give an efficient algorithm to compute exponentials (a^n).
Analyze your algorithm. (Hint. divide and conquer method)
- Exercises 10.1-2
- Exercises 26.2-7
- Problems 14-2: e)
Assignment 7 (deadline 9 Nov 1998)
- Exercises 10.2-2
- Exercises 10.3-1
- Exercises 31.2-1
- Exercises 35.2-7
- Exercises 35.3-6
I have decided to stop releasing new assignments while there is no students returning any papers. If you are interested in doing some exercises, please contact me (email address below)
Last updated 5.11.1998,
Ari Korhonen,
archie@cs.hut.fi.
URL: http://www.cs.hut.fi/~archie/ASA/foreing.html