Back to induction review.

Solution algorithms + Analysis of time, space, correctness, for problems of various levels of abstraction:

Specific problem with specific input (sort 100 strings)

Specific problem with general input (sort n strings)

Algorithms for related groups of problems (sorting by comparing whole keys)

General classes of problems like P and NP (all problems that can be solved in "polynomial time")

In all but the first category we will also sometimes explore the existence of bounds, checking closeness to optimality.

Going back to introductory programming you solved problems. In 271 you did some analysis. We will look much more closely at analysis of specific problems and algorithms of similar problems. We will touch on more general analysis for large classes of problems.

We will introduce some analysis with probability: average case analysis. That will require introducing some basic probability concepts. Has everyone seem basic finite probability?

Be sure you have the math pretest and turn it in by the due date in the assignments.

First week: asymptotic growth, induction, maybe order bounds with recurrence relations.

Read Ch 1 - mostly review from 271.

Here are a few comments to consider as you read. Be sure to note where you have questions, and bring the questions to class!

The pseudo-code of the text happens to be very close to Python! It generally does not declare explicit type, uses indentation for blocks, not {...}.

Executable algorithms are good! Who know Python? Who would rather
deal with Python than Java? Besides the clean syntax, I like Python
for the interactive shell, where you can easily play around.
Where we go beyond the book's pseudocode, I will generally introduce
algorithms in Python.

We will mostly consider sequential algorithms. Take High Performance Computing or Distributed Computing to see more on parallel algorithms.

Proving correctness of algorithms will be important. This I where some careful logic will come in, and your background in proofs may be tested.

We are likely to skip a detailed discussion of string processing, geometric problems, and numerical problems, though it is useful to know there is a large body of knowledge around each of them. We will spend a lot of time on graph problems in this course. This section provides an overview of many of the problem areas in the book. It is good for a quick read now. The book is organized in a novel fashion, more strongly around problem solving approaches than around problem areas or specific data structures. For instance many books place most of their graph algorithms together, even if they have very different solution approaches. I will reorganize our progress mostly more traditionally.

This section is a review of many standard structures and definitions of some basic concepts that you might not have seen before. The Introductory Questionnaire addresses these areas to some extent, but this section has somewhat more detail. Be sure to note what in new and hard, and ask me to come back to it!!! For basic terminology it will be important to return to this section as we get to new problem areas.

See the Induction Review.

Next Chapter 2.