This section introduces algorithms as abstractions of programs, and motivates why we need to do analysis of algorithms rather than just run empirical tests of programs. It then introduces some mathematical and conceptual tools for doing analysis. Two useful sorting algorithms are used for illustration; we’ll return to sorting later.

**#1**- Chapter 1: Introduction to Course Format and to Algorithms**#2**- Chapter 2: Examples of Analysis with Insertion and Merge Sort**#3**- Chapter 3: Growth of Functions and Asymptotic Concepts

In this section we introduce problem solving and analysis methods (chapters 3-5), some of which have been covered in ICS 241, and also review review basic data structures and algorithms (chapters 10-12) that were introduced in ICS 211. The chapters from the text are interleaved and paired up in a manner that uses the basic dictionary and set data structures and algorithms to illustrate the problem solving and analysis methods. Hopefully this is mostly review of the two prerequisite courses with some added depth.

**#4**- Chapter 10: Stacks, Queues, Lists and Trees (Review)**#5**- Chapter 5 and Goodrich & Tamassia section: Probabilistic Analysis and Randomized Algorithms; Skip list example**#6**- Chapter 11: Hash Tables**#7**- Chapter 4: Divide & Conquer and Associated Analysis Methods**#8**- Chapter 12: Binary Search Trees

We continue into more advanced applications of trees (chapters 6 and 13), also
providing the basis for another efficient sorting algorithm. We compare
additional sorting algorithms to those from Chapter 2. Sorting is one of the
most fundamental and common applications of computers, so efficiency is very
important. We consider the broader question of how fast *any* sort algorithm
can be. This is an example of a powerful method of computer science: reasoning
about sets of possible algorithms rather than specific algorithms.

**#9**- Chapter 6: Heapsort and Priority Queues**#10**- Chapters 7 & 8.1: Quicksort, Theoretical Limits, and O(n) sorts**#11**- Chapter 13 & Sedgewick Chapter 15: Balanced Trees

This part introduces two further problem solving methods, *dynamic
programming* and *greedy algorithms*, with example applications. We then cover
another important analytic method, _amortization _, with examples in the
analysis of the union-find representation of sets. (Chronologically, #14
graphs will be introduced in this sequence to help you get started on a
programming assignment, but conceptually they belong in the next section.)

**#12**- Chapter 15: Dynamic Programming**#13**- Chapter 16: Greedy Algorithms & Huffman Codes**#15**- Chapter 17 - Amortization**#16**- Chapter 21 - Sets and Union-Find

Graphs are a very flexible data structure for which many applications exist. Equipped with various problem solving and analytic tools, we examine the most important algorithms on graphs – including some of the most classic work in computer science – and their applications.

**#14**- Chapter 22: Graph Representations and Basic Algorithms*(covered earlier)***#17**- Chapter 23: Minimum Spanning Trees**#18**- Chapter 24: Single-Source Shortest Paths**#19**- Chapter 25: All Pairs Shortest Paths**#20**- Chapter 26: Maximum Flow

There are a number of other important or common application areas that have their own specialized algorithms of interest: multithreading (parallel algorithms), matrix operations, linear programming, operations on polynomials, number-theory, string matching, and computational geometry. These are covered in the text, but we can’t fit them all in. Linear Programming will be examined because it fills out an area not covered well above (numeric algorithms), and also has interesting connections to previous material (e.g., you can solve flow problems with a linear program). Two other topics will be covered more lightly in class (no homework).

**#21**- Sedgewick Chapters 5 and 38; Chapter 29: Linear Programming**#22**- Chapter 27: Multithreading**#23**- Chapter 32: String Matching

Finally, abstracting further from algorithms to problems, we deal with the
important question of whether an efficient algorithm is known (or even
possible) for a given problem, and what to do if none are known. We encounter
the most important open problem in theoretical computer science (indeed in all
of mathematics), which is of *practical* interest because awareness of
“intractable” problems and approximation algorithms could save you
considerable trouble if you encounter one of these very common problems on the
job! The seminal book on this topic is the most cited reference in computer
science.

**#24**- Chapter 34 - Complexity Theory & NP-Completeness**#25**- Chapter 35 - Approximation Algorithms