Date: Wed, 20 Nov 1996 22:33:23 GMT Server: Apache/1.0.3 Content-type: text/html Content-length: 4367 Last-modified: Wed, 30 Oct 1996 04:24:28 GMT B403 (Spring `97) home page

B403 (Spring `97)
Introduction to Algorithm Design and Analysis

[ General Information | Course Outline | Lectures | Assignments ]


General Information

Course description: This course is for students interested in designing computer algorithms and analyzing their efficiencies. The study of algorithms is at the very heart of computer science. The course will cover basic algorithm design techniques, including divide and conquer, recurrence, dynamic programming, greedy algorithms, and reduction to known problems, as well as basic algorithm analysis techniques, including worst case analysis, average case analysis, and probabilistic analysis. We will study various searching and sorting algorithms as well as a number of graph algorithms.

Prerequisites: C221 and C343 (or their honors equivalents) and Mathematics M216, or instructor's permission | Credits: 3

Instructor: Y. Annie Liu | Email: liu@cs.indiana.edu | Office: 201E Lindley Hall

Hours: MW 2:30PM-3:45PM, in Lindley Hall 019 | Office Hours:MW 3:45PM-4:45PM

Textbook: Introduction to Algorithms by Thomas Cormen, Charles Leiserson, and Ronald Rivest. MIT and McGraw-Hill, 1990 (Fifteenth printing, 1995)


A clarification: This course does not have programming projects. However, if you like programming, you should know that algorithms are written as pseudo code and, if you are good at them, you can turn them into real code easily. These algorithms are used in many applications, and there are programs written for them already. You may play with those programs if you like, but you will have to know the algorithms to understand how the programs work.

Tentative Course Outline

  • We will first introduce analysis of algorithms. This includes asymptotic notation, summations and recurrences, counting and probability, lower bounds. They will not be introduced in abstract, instead we will discuss sorting and related algorithms (insertion sort, mergesort, quicksort, heapsort, median and order statistics) as well as Strassen's matrix multiplication algorithms (Parts I-II: chapters 2-4, 6, 7-10, 31.2)

  • We will then discuss data structures. They include hash tables, binary search trees, red-black trees, skip lists, and augmenting data structures. The last piece will start the study of algorithm design, although some design techniques (recurrence, divide-and-conquer) will have been covered while introducing analysis techniques. (Part III: chapters 12-15)

  • We will then study advanced algorithm design techniques (dynamic programming, greedy algorithms) and analysis techniques (amortized analysis). These techniques will not be introduced in abstract, instead we will discuss problems such as longest common subsequence, activity selection, and minimum spanning tree. This last example will start study of graph algorithms. (Part IV: chapters 16-18, 24)

  • We will then discuss graph algorithms. This include basic algorithms like depth-first search, breadth-first search, topological sort, and strongly connected components, as well as more advanced algorithms for single-source/all-pairs shortest paths problems and network flow problems. (Part VI: chapters 23, 25-27)

  • We will at the end introduce a few selected topics. Possible choices are parallel algorithms, incremental/dynamic algorithms, polynomials and FFT, string matching, and computational geometry. (Part VII: chapters 28?, 29?, 32?, 34?, 35?)

    Lectures


    Assignments


    liu@cs.indiana.edu Last updated October 29, 1996