Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 INF1: Algorithms and Data Structures
According to luminaries like David Harel and Donald Knuth
amongst others, the core of Computer Science is the study of
algorithms. The Concise Oxford Dictionary defines an
algorithm as a process or rules for (esp.) machine
calculations. More generally, an algorithm is a systematic method
(i.e. a precisely defined sequence of rules) for solving a given
problem. Its execution must not include any subjective decisions, nor
must it require the use of intuition or creative thinking.
One of aims of this course will be to introduce fundamental techniques
for the design of algorithms, and ways to argue for their correctness
and to analyze their efficiency. A person well-trained in computer
science knows how to deal with algorithms: how to construct them,
manipulate them, understand them, analyze them. This knowledge is
preparation for much more than writing good computer programs: it is a
general-purpose mental tool that will be a definite aid to the
understanding of other subjects. The reason for this general
usefulness of the study of algorithms may be summed up using the
following quotation from Donald Knuth:
A person does not really understand something until after
teaching it to a computer, i.e. expressing it as an
algorithm..... An attempt to formalize things as algorithms leads to a
much deeper understanding than if we simply try to comprehend things
in the traditional way.
Turning algorithms into computer programs requires the use of data
structures, i.e., ways to organize data in computer memory so that
certain key operations on data items can be efficiently performed. The
other main aim of the course will be to introduce some of the classic
data structures whose uses abound in the computer applications we
interact with daily.
Prerequisites and Related Courses
This course is part of a collection of lecture series in your degree
programme whose aim is to strengthen your analytical and problem
solving abilities. Anybody who deals professionally with information
technology artifacts needs both creativity and a capacity for
analytical thought. Computer Science is heavily based on logical
thinking, and this course will help you strengthen your ability in
solving problems logically and in documenting your solutions in as
understandable a way as possible.
The course builds upon your course on Matematik 2B
Forår 2001, but it assumes little by way of mathematical
prerequisites, apart from a willingness to think and work
systematically and logically. It will provide you with the mental
attitude that you will need to make the most of the courses on Syntaks og
Semantik and Netværksteknologi og Beregnlighed.
Some familiarity with programming, albeit not necessary, would be
useful, but I want to stress that this is not a programming
course. We shall mostly be using some kind of pseudocode to describe
algorithms.
Textbooks and References
The main textbook for the course will be the book Algorithms and
Data Structures: Design, Correctness and Analysis by Jeffrey H. Kingston (ISBN
0-201-40374-9). (Available for example at Amazon.co.uk. BookFinder
reports the prices for both new and used books at several stores.)
As supplementary reading on the science of computing as a whole and on
its algorithmic foundations, I also strongly recommend the book
Algorithmics: The Spirit of Computing by David
Harel. (Available for example at Amazon.co.uk. See
BookFinder
for information on the prices for both new and used copies of this
book at several stores.)
Other supplementary reading material will be provided for photocopying
in the course folder.
You may also wish to consult one of the following informative
resources on the web:
The course will consist of a series of 15 lectures. The schedule for
the lectures and their location may be found here. Any
variation to the original lecture plan will be communicated on this
page.
Our working language for the course will be English.
The following list of topics for the course lectures is
preliminary and should be taken with a large pinch of
salt. The actual theme of each lecture may vary, and will only be
finalized before the lecture actually takes place.
Lecture 1 (Monday, 10 September 2001, at
10:15): Introduction to the course; Introduction to algorithms, or
"What's it all About".
Lecture 2 (Monday, 17 September 2001, at
10:15): The correctness of algorithms, or "Doing it Right".
Lecture 3 (Monday, 24 September 2001, at
10:15): The analysis of algorithms, or "Doing it Cheaply".
Lecture 4 (Monday, 1 October 2001, at
10:15): Algorithm design, or "Doing it Methodically".
Lecture 5 (Monday, 8 October 2001, at
8:15): More on dynamic programming; Abstract Data Types.
Lecture 6 (Monday, 22 October 2001, at
10:15): Lists.
Lecture 7 (Monday, 29 October 2001, at
10:15): Stacks and queues. The ADT of Trees (intro).
Lecture 8 (Monday, 5 November 2001, at
10:15): The ADT of Trees.
Lecture 9 (Monday, 12 November 2001, at
10:15): The ADT Symbol Table and its implementation using Binary
search trees and Hashing.
Lecture 10 (Thursday, 15 November 2001, at
10:15): Sorting.
Lecture 11 (Monday, 19 November 2001, at
10:15): More on Sorting (Quicksort, Radix sort). Graphs and their
implementation.
Lecture 12 (Thursday, 22 November 2001, at
10:15): Algorithms on graphs: Topological sorting, cycle detection,
breadth-first search and depth-first search.
Lecture 13 (Monday, 26 November 2001, at
10:15): Algorithms on graphs (part 2): Algorithms for the shortest
path problem. Bellmann-Ford and Dijkstra's algorithm.
Lecture 14 (Thursday, 29 November 2001,
at 10:15): Algorithms on graphs (part 3): Algorithms by Kruskal and
Prim for the minimum spanning tree problem.
Lecture 15 (Monday, 3 December 2001, at
10:15): A primer on NP-completeness.
Exercise Classes and Advice on Modus Operandi
As usual, each lecture will have an associated exercise class. The
exercises mentioned on the web page for a lecture should be solved
during the exercise class that precedes the following lecture. For
example, the exercises listed on the web page for lecture 1 should be
solved before lecture 2. There will be no exercise class preceding the
first lecture.
In general, I shall give you more exercises than you might conceivably
be able to solve during one exercise class. The exercises marked with
a star are those that I consider more important for your
understanding. All the exercises will be "doable", and working them
out will greatly increase your understanding of the topics covered in
the course. The best advice I can give you is to work them all out by
yourselves, and to make sure you understand the solutions if the other
members of your group (or me) gave you the solutions on a golden
plate. Above all, don't give up if you cannot find the key to the
solutions right away. Problem solving is often a matter of mental
stamina as much as creativity.
I should say immediately that you should not expect to read
an algorithm as if it were part of a novel: such an attempt would make
it pretty difficult to understand what is going on. An algorithm must
be seen to be believed, and the best way to learn what an algorithm
does is to try it. You should always take pencil and paper and work
through an example of each algorithm immediately upon
encountering/inventing one. This is a simple and painless way to gain
an understanding of a given algorithm.
Above all, try to be critical of your solutions to the exercises. You
may not need (some of) the material covered in this course in your
future careers, but having an analytical and critical attitude will
always help you.
The importance of solving the exercises cannot be
understated. "What we learn, we learn by doing", and this is
all the more true for the material in this course. Previous experience
shows that the people who work through the exercise sets are those
that pass the exam because they develop the problem solving and
presentation skills that will serve you for a lifetime. It is simply
too late to begin solving, and writing down solutions to, the
exercises at the exam. Mind you, it is not my intention to patronize
you. I am just giving you a sensible piece of advice---that's all.
Exam
The exam will be a individual, internally evaluated and
written. The mark for the course will be given following the
standard range from 00 to 13.
This page will be actively modified over the autumn term
2001, and is currently undergoing heavy restructuring. You are invited
to check it regularly during the autumn term. The page is dormant in
the spring term.
Let me know of any error you find in
the course web pages.