4 Course Content and Outline

The official kursplan (an official document identifying the topics and goals of the course) is available on the course web site. A more offering-specific outline follows.

The course will be divided into two parts.

Analysis and Design of Algorithms (75%):

In this part of the course, some of the basic techniques used in the analysis and design of non-numerical algorithms which have become central to the study of computer science in recent years will be examined. Both the theoretical and experimental aspects of the subject will be covered. In particular, the following questions will be considered.

• Both formal characterization and software profiling of algorithm performance will be given strong consideration, with special emphasis upon how the two methods complement one another.
• The presentation will be organized around design paradigms, so that the design as well as the analysis of algorithms will form a central focus.

Complexity of Problems and Problem Classes (25%):

In this part of the course, the intrinsic complexity of problems (as opposed to algorithms) will be examined. After briefly examining the inherent complexity of solving certain ubiquitous problems (such as sorting and searching), attention will be turned to the important class of NP-complete problems. These are often considered “intractable” in the literature. In this course, the focus will be upon various approximation and heuristic techniques which have proven useful in solving such intractable problems in practice will be studied. A theoretical presentation of the properties of the class NP is now part of the course Complexity Theory, and so this topic is no longer covered in detail in this course on the Analysis of Algorithms.

Due to time constraints, and because there are other courses available, material on algorithms for parallel computation will not be covered in this course.

An outline of the course is shown below. The numbers shown in the rectangular brackets (i.e., [..]) identify chapters and sections in the textbook. The numbers in angle brackets (i.e., ⟨…⟩) indicate the approximate number of 45-minute lecture periods which will be devoted to the topic.

• Reasonably detailed overhead slides will be available for many topics. The authoritative source for relevant (i.e., possible examination material) is the course lectures and these slides. In many cases, material not covered in the textbook may nonetheless be covered in lecture presentations.
• The number of 45-minute lecture ”hours” to be devoted to each topic is approximate. Adjustments may be made as the course progresses. In addition, some class time will be used to discuss the solutions to obligatory exercises.

1. Introduction [] ⟨1⟩
2. Basic tools for algorithm analysis [1] ⟨3⟩
   1. Mathematical techniques
   2. Experimental techniques
3. Algorithm Analysis and Design Strategies
   1. Divide-and-conquer [3] ⟨4⟩
   2. The greedy method [4] ⟨5⟩
   3. Dynamic programming [5] ⟨4⟩
   4. Basic search and traversal techniques [6] ⟨2⟩
   5. Backtracking [7] ⟨1⟩
   6. Branch-and-bound [8] ⟨2⟩
   7. Algebraic simplification and transformations [9] ⟨3⟩
4. Problem Classes and Problem Complexity
   1. Lower bound theory [10] ⟨1⟩
   2. NP-complete and NP-hard problems [11] ⟨2⟩
   3. Approximation algorithms for NP-hard problems [12] ⟨4⟩