CS-251A/B
Data Structures and Algorithms
"To iterate is human; to recurse
divine" - L. Peter Deutch
Hints on How to Pass this
Course Smiling
-
Welcome!
Welcome to Computer Science 308-251A/B: Data Structures and Algorithms.
This course is an introduction to the design and analysis of algorithms
and their data structures. Below you will find a description of the main
ingredients involved in taking this course with hints for passing, enjoying
and making the best out of it. Please study it carefully.
-
No Programming:
This course is NOT a programming
course and there will not be any programming assignments. The course is
instead concerned with the principles behind the design of efficient
algorithms for solving a variety of different classes of problems in different
contexts. It is NOT concerned with
the details of implementing algorithms on real computers with "real" programming
languages such as FORTRAN II, APL, C or JAVA. Instead we will use idealized
computers (mathematical models of computers if you like) such as the
Straight-Edge-and-Compass,
the Turing Machine and the Real RAM (Random Access Machine
with real numbers as inputs) to measure the computational complexities
of our algorithms. We will also use idealized data structures to
study the algorithms and their storage requirements.
-
Algorithms for Humans:
Although in this course we are concerned with designing algorithms
that are ultimately intended for machines to process, we are NOT
interested
in communicating with the machines but rather with each other. We are interested
in communicating with humans about algorithms. Therefore we will
NOT
use code in this course. Code was designed to be understood
by machines not humans. We will describe algorithms in a natural language
such as English
and in the
language of mathematics as has been done for thousands of years.
Furthermore mathematics should not be confused with mathematical notation.
The essence of mathematics lies in the precision of concepts and not in
symbolic notation. Mathematical notation will be minimized. Algorithms
described in code will get a mark of ZERO. Students using
mathematical notation gratuitously will be penalized. Mathematical
notation should be used only when absolutely necessary if it helps the
reader. Remember that storage space is no longer a problem and we need
not save precious space at the cost of making things difficult to read.
In this course we will learn how to think and use English in a precise
way.
-
Correctness of Algorithms:
One of the most important properties of an algorithm is its correctness.
In fact this is so important that many people refuse to call a procedure
an algorithm if it is not guaranteed to give the correct solution. Many
"algorithms" inhabiting the computers in society at large are
incorrect. This can cause great cost and tragic suffering. For
example, patients have been killed by overdoses of radiation because of
incorrect
algorithms. The American astronauts aboard the space shuttle Challenger
were killed because of an incorrect geometric algorithm used in rebuilding
the booster rockets. In fact a nuclear world war could be caused by an
incorrect algorithm. Therefore it is very important to design correct algorithms.
In later computer science courses students often have trouble proving the
correctness of algorithms. Therefore this course
will emphasize various techniques for proving the correctness of algorithms.
-
Induction Proofs:
In later computer science courses students have the most trouble with
induction
proofs.
In a very important sense this is the most relevant method of designing
algorithms and proving correctness for computer scientists since it lies
at the heart of recursion and divide-and-conquer,
two fundamental techniques for obtaining efficient algorithms. Therefore
this course has as one goal for the students to master proofs by induction.
Induction
proofs will be a recurring theme in the course.
-
Course Web Page:
Students should consult the course web page regularly. It can be found
at: http://www-cgrl.cs.mcgill.ca/~godfried/teaching.html.
This page contains several sections we will now describe.
-
Logistics Information:
This section of the course web page details the performance evaluation
of the students, the coordinates of the lecturer and teaching assistants,
the text book used in the course and similar matters.
-
Calendar and Bulletin Board:
This web page contains the calendar of events for the course such as
the in-class exams. The bulletin board at the beginning contains messages
from me to you of important day to day events, matters related to the exams,
etc and must be checked every week-day.
-
Lecture Descriptions, Homework and Play:
This web page contains a detailed list of topics covered in every lecture.
It contains the reading assignments made every week from the text book,
practice problems, handouts and web material. It also contains suggested
play. Students are strongly encouraged to play with the applets suggested
in this section. Students who do will be at an advantage as it greatly
facilitates learning the material in this course.
-
Course Outline:
This page contains an skeletal outline of the course contents.
-
WEB Course Contents:
This page contains much of the material that we will cover in the course
that is not contained in the course text book (Udi
Manber: Introduction to Algorithms).
We will make up for the text book's light treatment of data structures
with material in this web page. Many of the course reading assignments
will concern pages in this section. Here you will also find alternate descriptions
of material that is contained in the text book. It helps students
to learn when they read different explanations of the same thing
by different people. This web page also contains the applets for the suggested
play section of the assignments. Finally, this page also serves as a library
to satisfy your general curiosity concerning material that is interesting
and directly relevant to the course. Hence it contains much more material
than what we will cover and I do not expect you to read it all. However,
I do suggest you browse through all of it and read what is most interesting
to you.
-
Class Tests and Final Exam:
There are two 75-minute in-class tests during the term and one final
exam after the course is finished. All these are closed
book. However, I am not interested in measuring your memory.
Computers are much better than we humans at that. The tests will measure
your ability to think creatively. Students often ask: what material will
be covered in the test? My answer is always the same. I don't want to insult
your intelligence by asking you only to regurgitate material we have covered.
A machine can do that much better than we can and I don't want to treat
you like machines. I want to test you on what machines cannot do (yet),
and that is to generalize or apply your knowledge to solve new problems
in new contexts. Therefore my tests will also
cover material we have NOT covered in the course. The material
I learned as a university student concerning radios, cathode ray tubes
and transistors is useless to me now. Many of the things I teach now did
not exist ten years ago. The models of computation and algorithms we use
now may be obsolete ten years from now. On the other hand, the creative
problem solving techniques and critical thinking skills I learned as
a student can be applied to things other than transistors, such as the
latest trends in computational geometry. How can you do well on my tests?
University is (still, thank heaven, although fast eroding) a place for
discussing knowledge in a free and open atmosphere, and I encourage you
to discuss all matters of the course with your class mates. On the other
hand the modern harsh reality dictates that obtaining a university degree
is also a certification method for certain skills - hence the tests. The
best way to study for the tests in my course is to do the practice assignments
and exercises on your own before consulting with other students.
Only
personal discovery leads to true understanding. The questions in the exams
will be similar to the practice assignmnets. The text book by Udi Manber
also contains many exercises at the end of each chapter with answers at
the back of the book. Doing these exercises on your own is an excellent
way to learn how to design algorithms in particular and how to think creatively
and critically in general. Think of your brain as another muscle in your
body. To get it in shape requires practice, practice and more practice.
-
Assignments:
The assignments are there for you to practice. They will not be marked
nor collected. However you are encouraged to consult the TA's if you have
difficulty with them. The exams will contain problems similar to those
in the assignments. This is another good reason to do them. Try them first
on your own, then in consultation with friends. After a couple of weeks
the solutions will be posted so that you can check your progress. Before
each exam the TA's will give tutorials on these assignments to help you
further prepare for the exams.
-
Teaching Assistants:
The TA's are responsible for marking the class tests and final exam.
If you have any questions about how you were marked please go see them.
If you have general questions about the course material please see them
too. They are there to help you.
-
Enjoy the Course!
If for some reason the TA's cannot help you please come and see me.
In any case please come by sometime to say hello and tell me how you are
doing in the course. My door is wide open during
my office hours and I would love to meet you in person.
Godfried Toussaint