# ICS 161: Design and Analysis of Algorithms

## Fall 1995

- Class meetings: Tu Th 9:30-10:50am
- Discussion section meetings: W 1-1:50pm or 2-2:50pm
- Professor:
Dan Hirschberg
- Electronic Mail: dan@ics.uci.edu
- Office: CS 414D
- Phone: X-6480
- Office Hours: after class or by appointment

- Teaching Assistants
- Steve Seiden - sseiden@ics.uci.edu, CS358E, M F 10-10:50am
- Vitus Leung - vitus@ics.uci.edu, CS245, Tu 2-2:50pm

- Reference Texts:
- Baase,
Computer Algorithms (2nd ed.),
Addison-Wesley, 1988.
- Brassard and Bratley,
Algorithmics Theory and Practice,
Prentice-Hall, 1988.
- Aho, Hopcroft, and Ullman,
The Design and Analysis of Computer Algorithms,
Addison-Wesley, 1974.

- Prerequisites: ICS 23, 51; Math 2abc, 6ab.
- Add/drop policy:
- Adds permitted through end of week 2
- Drops permitted through end of week 6

## Course Goals

To develop an understanding of efficiency of algorithms,
to learn some algorithmic design techniques,
and to analyze the complexity of the resources required
by algorithms for a variety of applications.
## Course Outline

- Introduction [B 1; BB 1, 2.1]
- Course requirements, induction proofs, D-charts
- Complexity and asymptotics [B 1.4]
- Models of computation [AHU 1.5]
- Examples of algorithm analysis

- Searching, sorting, lower bounds [B 1.5, 2, 3; BB 10.1]
- Searching - sequential, binary, interpolation [B 1.5]
- Insertion sorts - straight, binary, Shellsort [B 2.2, 2.6]
- Lower bounds on sorting - inversions, travel, decision[B 2.4]
- Heapsort
- Distribution sorts - bucket, lexicographic [B 2.7]
- Lower bounds on selection [B 3.1-3.3, 3.5]

- Divide-and-conquer [B 2.3, 3.4, 7.3.4; AHU 2.6, 3.6-3.7, 6.2]
- Selection of median [B 3.4; AHU 3.6-3.7]
- DC paradigm - MaxMin, Integer multiplication [AHU 2.6]
- DC Theorem
- Time analysis of Mergesort, Quicksort [B 2.3]
- Strassen matrix multiplication [AHU 6.2], The skyline problem

- Dynamic programming [B 6; BB 5]
- Product of matrices, Substring problems [B 6.2.1, 6.3]
- Optimal binary search trees [B 6.2.2]
- Nim, Fibonacci numbers

- Graph algorithms [B 4, 8.1-8.3; BB 3.2, 6.1-6.4; AHU 5]
- Minimum spanning trees - Prim, Kruskal [B 4.2]
- Depth-first search - components, biconnectivity [B 4.4-4.5]
- Transitive closure, shortest paths [B 4.3, 8.2]

- Other topics [B 9; AHU 10; BB 6.6, 8, 10.3]
- Backtrack programming - knight's tour, 8 queens [BB 6.6]
- Branch and bound - 0/1 knapsack, travelling salesman
- NP-complete problems
- Probabilistic algorithms [BB 8.4]

## Grading

- 20% -- Weekly homework
- 40% -- Two midterm examinations
- 40% -- Final exam

## BBOARD

Read ics.161 for announcements.
Also, please post questions about anything. If you don't understand
something, others probably don't either and will have the same question.

Dan Hirschberg

Department of Information and Computer Science

University of California, Irvine, CA 92717-3425
Last modified: August 30, 1995