**CS-251A Data Structures and Algorithms**

*"To iterate is human;
to recurse divine" - L. Peter Deutch*

*Hints on How to Pass this
Course Smiling*

**Welcome!****No Programming:****Algorithms for Humans:****Correctness of Algorithms:****Induction Proofs:****Course Web Page:****Logistics Information:****Calendar and Bulletin Board:****Lecture Descriptions, Homework and Play:****Course Outline:****WEB Course Contents:****Class Tests and Final Exam:****Assignments and Late Assignment Policy:****Teaching Assistants:****Enjoy the Course!**

Welcome to **Computer Science 308-251A: Data Structures and Algorithms.**
This course is an introduction to the design and analysis of algorithms.
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.

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.

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 use English in a precise way.

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 concentrate on various techniques for proving the correctness
of algorithms.**

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 algorithm design and correctness proof 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.**

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.

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.

This web page contains the calendar of events for the course such as the in-class exam and quizzes, the dates the assignments are handed out and due, and a very short title of each lecture. The bulletin board at the beginning contains messages from me to you of important day to day events, matters related to the assignments, etc and must be checked every week-day.

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, handouts and web material. It also contains suggested play. While this section is not required, 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.

This page contains an skeletal outline of the 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)**.
Many of the course reading assignments will concern pages in this section.
Here you will also find alternate descriptions of material that is in the
text book. It sometimes 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.

There are **two** in-class tests and **one** final exam . 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 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 always cover everything we have
NOT covered in the course.** The material I learned as a student
in university 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 assignments and exercises** on your own.**
Only personal discovery leads to true understanding. 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.

Please write ** legibly**.

I am unforgivingly strict with late assignments. **Assignments
MUST be handed in on the day due and BEFORE the lecture begins.**
Every day that the assignment is late, starting with the day due and including
weekend days, will result in a penalty of 10% of the original worth of
the assignment.

The TA's are responsible for marking the assignments and the quizzes and 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.

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.**

*Godfried Toussaint*