CS-251A Data Structures and Algorithms

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

Hints on How to Pass this Course Smiling

1. Welcome!
2. 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.

3. No Programming:
4. 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.

5. Algorithms for Humans:
6. 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.

7. Correctness of Algorithms:
8. 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.

9. Induction Proofs:
10. 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.

11. Course Web Page:
12. 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 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.

• 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, 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.

• Course Outline:

• 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). 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.

13. Class Tests and Final Exam: