Weekly Note 1, DM18, Spring 2007
Lecture February 1
-
Introduction to the course.
-
Overview of a compiler.
-
Lexical Analysis (scanning).
Background material: Appel Chapter 1 and 2, Flex-documentation.
With regards to literature and material on flex, see the
literature page.
The tool flex is used in combination with the programming
language C. If you have not programmed in C before, then
it would be a good idea to read about it and try to write
a few small programs. References to material on C can be
found via the literature page.
Exercises February 5
-
Form groups of three students. You may form these by yourselves,
but we have to be informed.
Students taking the full 15 ECTS version (or 9+6 ECTS for
Datatechnology students taking the full course) should not be
grouped with students taking only the 9 ECTS version.
The teaching assistant will assist in solving problems and
finding groups for everyone.
-
If you do not know
C
, then read about it,
write some little programs, and ask questions at the
discussion sections, if there is anything you are in doubt of.
If C
is new to you, it is important to start looking
at it quickly. If you have diffulties with the problems below,
then pose your own programming problems. The most important
is to get started with the language.
-
Implement the following primitive hash table with the operations
insert
, delete
, and lookup
.
The elements in the hash table are referred to as keys.
They are integers and they are
placed in an array. The size of the array must be a prime.
The hash function, which is used to decide where a given
key should be placed in the array, should be of the form
a * x mod "table size"
,
where a
is a different prime.
As a simplification compared with a normal hash table,
you can assume that no keys are placed in the same entry in the array.
The implementation should be made in ANSI-C
.
Use the compiler gcc
.
Make a few tests.
-
Implement binary search trees with the operations
insert
, delete
, and lookup
.
You do not have to implement any kind of rebalancing.
The implementation should be made in ANSI-C
.
Use the compiler gcc
.
Make a few tests.
-
Read about
make
and explain the fundamental principles
and features. You do not have to go into detail with any advanced
applications. As a start, read the entire introductory section
and the section on syntax. Then
familiarize yourself with the remaining content,
e.g., by reading the introduction to each chapter.
With regards to literature and material on C
and
make
, see the
literature page.
Announcements
-
Those students who want to use DM18 as their bachelor project
must sign a statement confirming this.
It is not possible later to decide to use DM18 as the
bachelor project if one did not sign up for this at the
beginning of the course.
The engineering study board has decided that datatechnology students
are not allowed to use DM18 as a bachelor project.
The procedure for computer science students is the following:
no later than February 9 at 12:00, you must have sent an e-mail
to the lecturer with your full name,
e-mail address (the one you read daily),
IMADA login,
and first 6 digits of your CPR number. Please use
"DM18: bachelor project" as the subject of the mail.
The secretaries' office will then prepare statements and you
will be informed as to when you can come by and sign.
-
At the exercises February 5, you will be divided up into groups.
If you are not able to show up for the exercises that week,
send an e-mail to the lecturer containing your name,
study program (normally "datalogi" or "datateknologi"),
e-mail address (the one you read daily),
IMADA/MIP login, and whether you are taking the
9 ECTS or the 15 ECTS version (the size option only applies to
datatechnology students).
Please use "DM18: group" as the subject of your mail.
-
Be advised that the course project will be posed in many parts.
The first part will be posed during the first week of the course
and will have a hard deadline about two weeks later.
See the next weekly note and the course home page.
Last modified: Tue Feb 6 13:01:57 CET 2007
Kim Skak Larsen
(kslarsen@imada.sdu.dk)