Although the lecture covers most of the required material, in addition to regular class attendance you are expected to read the covered sections of the textbook before and after they are discussed in class. Moreover, it is recommended that at the beginning of semester you read or scan through the course text lightly from cover to cover. It is suggested that you examine the table of contents of the textbook next. This provides a logical overview of the course from the author's perspective. When you begin your course of study, always read the introduction at the start of each chapter before you read the chapter itself. Do not skip the Exercises section. Following the above recommendations will allow you to achieve your goal in this course (e.g., a desired final grade) with less effort.

To prepare you to final exam, you will be provided a practice examination. This exam is a ``mini" version of the final, designed to help you focus on the types of questions which appear on the final exam. Answers are provided as a further study aid to check for understanding and the approach used.

This is a theoretical course. It assumes a previous introduction and knowledge of college-level algebra and calculus, discrete mathematics, and skill in programming in a high-level programming language. However, the prerequisite knowledge (except for college algebra) is briefly summarized in Chapter 1, 2, and 3. This course will give you a detailed insight into contemporary methods and techniques of algorithms' analysis and synthesis. You will learn them on a number of classic algorithms and their data structures the knowledge of whose is considered fundamental for any person with a college degree in Computer Science. I hope you will find the subject fun to study.

After passing this course you should understand the basic ideas of algorithms and the data they manipulate. In particular, you should be familiar with the concepts of algorithms' complexity (``big Oh", ``little oh", ``big Omega", ``big Theta", optimality, worst-case vs. average-case), data structures (esp. lists, trees, graphs), and techniques of algorithm design (divide-and-conquer, dynamic programming), its complexity analysis, and proving its correctness. You should acquire a sound knowledge and understanding of substantial number of representative samples of sequential algorithms (sorting, searching, selection, string matching, a variety of algebraic and graph algorithms), as well as some parallel ones, illustrating these concepts and techniques. Although memorizing programs is generally not required, you should be able to describe on examples their functional behavior. Moreover, you should know the limitations of performance of several classes of algorithms (lower bounds), as well as limitations of computers to solve problems (NP-completeness theory).

Although you are encouraged to read and study the entire textbook, the midterm and the final exam will cover only the following chapters and sections ("individual reading" chapters are only covered where indicated):

Chapter 1: (Section 1.2 left to individual reading) Entire chapter is critical for proper understanding of the rest of the book. It contains brief review of prerequisite knowledge of mathematics (especially: logarithms, approximating summation with integration, de L'Hôpital rule), and some computer-theoretic concepts: program correctness, worst-case and average-case complexity, lower bounds of classes of problems and optimality of their solutions, as well as calculus for evaluation of complexity (O (``big Oh"), o (``little oh"), (``big Omega"), (``big Theta")).

Chapter 2: (individual reading) reviews some standard material from the Data Structures course, in paricular, abstract data types and their typical implementations.

Chapter 3, sections 3.1 - 3.7: (individual reading) is a repository of techniques and proofs related to recursive procedures. You may expect that it will be covered by test 1 and final.

Chapter 4: Sections 4.1 - 4.9. In addition to detailed review of classic sorting algorithms you will learn how to establish the worst-case and average-case optimality within a class of solutions. Two such classes will be investigated: algorithms that sort by swapping only adjacent keys, and algorithms that sort by comparison of keys. Moreover, you will learn the Divide and Conquer method of algorithms' design, together with recurrence relations that characterize their running times.

Chapter 5: Sections 5.1 - 5.5 In addition to learning classic selection algorithms and methods (finding max and min, or max and second largest), you will become familiar with the adversary method of establishing lower bound of complexity of problems.

Chapters 7 - 8: Sections 7.1 - 7.6 and , 8.1 - 8.4 You will learn in detail classic algorithms for graphs, and implementations of their data structures which assure their best performance. All the algorithms discussed in this chapter are capable of searching certain properties in graphs they work on, and consequently, have numerous applications in the area of Knowledge Representation and Artificial Intelligence. They belong to the basic knowledge expected from everybody with a college degree in Computer Science. 

Chapter 9: Sections 9.1 - 9.5, (individual reading) is focused on finding connections (more precisely, paths) in realities represented by graphs. You may expect that it will be covered by test 2 and the final exam.

Chapter 10: Sections 10.1, 10.4, 10.6 Dynamic programming method is the main focus in this chapter. You will learn how to apply it on classic problems, as, for instance, constructing optimal binary search trees.

Chapter 13: Sections 13.1 - 13.3 and 13.7.1 This is the most theoretical chapter of the textbook. It contains introduction to NP-completeness theory that provides an advanced tool for identification of those ``hard" problems which, although solvable by means of computer program, do not posses practical solutions. The central open question of the theory is the celebrated ``P = NP?" problem. (In the recent past, there were rumors that this problem has been negatively solved; however, all the ``solutions" turned out wrong so far). This chapter will familiarize you with ``hard" problems, and show how seemingly similar versions of the same problem (e.g., the Coloring Graph Problem) may differ dramatically in their intrinsic complexity.

Chapter 14: Sections 14.1 through 14.5, (individual reading) is devouted to parallel versions of several standard algorithms. You may expect that it will be covered by the final exam.

Except for Chapter 1 which contains introductory material for the rest of the book, all chapters are self-contained and may be studied independently of each other. Chapter 13, however, as the most theoretically advanced part of the textbook, is recommended to study after Chapters 1 - 7 or later.

The midterm(s) and the final's questions will be a matter of considerable difficulty. For full credit they will require not only your solid knowledge of the subject but also certain level of your creativity, for instance, solving a problem, writing a (fragment of a) program, or evaluating its running time.

The midterm(s) is (are) closed-textbook. The time allowed for completion of the midterm is 1 hour.

The final examination is a closed-textbook multiple-choice exam. It requires scantron form 882-E. The time allowed for completion of the final is 2 hours.

Calculators are allowed but not required.

1. Time yourself carefully. Spending a lot of time on one or two questions while ignoring the others is not a good strategy. If a question seems very difficult to you, take your best shot at the answer and, if time allows, come back to it later.
2. Read every question very carefully so that you have a good understanding of it. If the question consists of more than one part, make sure to answer all of them.
3. Do every problem. An educated guess, if properly supported, often earns a partial credit, while a blank answer does not. However, a sloppily presented proof or derivation which the grader finds difficult to follow or understand may earn little or no credit, and is not good for grader/test taker rapport.
4. Be neat and orderly. If an answer is not prepared in an easily readable fashion, cross your answer out, write ``See the last page", and rewrite your answer there. Always show your complete calculations or proof for each problem solving question.
5. Label everything. Do not assume that anyone knows what you are thinking. Your goal is to convince the grader that you know the material, not to challenge him into discovering what you are trying to communicate.
6. Do not be afraid to use generous amounts of paper, as needed.