ICS 161, Design and Analysis of Algorithms
Winter 1996 Lecture Notes


The following lecture notes describe topics from the Winter 1996 offering of ICS 161. They are placed here in the hope that they will remain helpful for future 161 students, however there is no guarantee that they cover the same material as current 161 offerings.

If you are a UCI student, DO NOT PRINT OUT COPIES OF THESE PAGES. Printed copies are available for purchase from the Engineering Copy Center.

9 Jan: Introduction - Fibonacci numbers
11 Jan: Sequential and binary search

16 Jan: Sorting, lower bounds, and heap sort
18 Jan: Three divide-and-conquer sorting algorithms

23 Jan: Integer and string sorting
25 Jan: Order statistics and selection

30 Jan: Deterministic linear-time selection
1 Feb: Graph algorithms

6 Feb: Minimum spanning trees
8 Feb: Shortest paths and topological ordering

15 Feb: Breadth first search and depth first search

20 Feb: Strongly connected components
22 Feb: Finite automata and string matching

27 Feb: KMP string matching algorithm
29 Feb: Common substrings, dynamic programming

5 Mar: Regular expression matching and more dynamic programming
7 Mar: Computational geometry

12 Mar: NP-completeness


ICS 161 -- Dept. Information & Computer Science -- UC Irvine
Last update: