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
11 Jan: Sequential and binary search
16 Jan: Sorting, lower bounds, and heap
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
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