Readings
Read Chapter 1. There is more discussion of the question
of "what is an algorithm" as well as some examples of other types of
problems where efficient algorithms are important.
If you are interested in more discussion of Merge, MergeSort, and/or
Insertion Sort and/or to see how the text presents pseudocode, it is
in Chapter 2.
Chapter 2, Section 2 also has more analysis of
Insertion Sort (the book discusses the various costs we can
consider), and discussion of the random access machine (RAM) model.
Chapter 3 has write-ups of the formal definitions (and more discussion of)
Big-O, Big-Omega, and Theta, little-o, little-ω and the growth of
functions in general. Particularly, Section 3.2 has some definitions and
rules you might find helpful about monotonicity, floors, ceilings, and
logarithms.
We have covered Chapter 4 material (solving recurrences) in class.
There are patterns (which may help us when designing algorithms)
to many recursive trees, and the Master Theorem can be used in some
situtions to determine the Θ bound without the use of a tree.
Please note that the book refers to "guessing a form of the solution,
and then using constructive induction" as the "substitution method."
Chapter 6 looks at the Heap structure and how it can be used in a
comparison-based sort.
Chapter 7 of the CLRS text explores Quicksort in more detail, as well
as the expected runtime analysis.
Chapter 8 discusses linear-time sorting algorithms that are not
comparison-based such as counting sort, radix sort, and bucket sort.
We discussed their limitations and ways in which to determine their run-times.
We have covered the Chapter 9 material (min, max, min and max together,
median finding and general selection). You might find the discussion in
the text gives a different presentation of the same material.
Chapter 9 also looks at the analysis of the randomized selection algorithm's
expected runtime.
From Chapter 12 we looked at the binary search tree, and the AVL tree in
detail. We mentioned the Splay variation on the binary search tree.
Chapter 16, sections 1 and 2 has
discussion of what is officially called the "activity-selection"
problem. You might be interested in reading section 3 which
discusses Huffman codes, whose construction uses a greedy algorithm,
if you did a Huffman tree in a previous course.
Chapter 22 has graph theory, some terminology, and some algorithms
that can be used with graphs (such as BFS and DFS) and some of their uses
(eg: reachability, strongly connected components, topological sort).
Chapter 23 discusses the Minimum Spanning Tree problem.
We discussed the analysis of a faster matrix multiplication algorithm.
A full discussion of this is in Chapter 28, Section 2. We did not go
into that level of detail, but rather focused on the algorithm as a
different type of divide-and-conquer, and the runtime as described by
recurrence relations.
Chapter 34 discusses NP-Completeness - we looked at the basic concepts
of NPC but that topic will not be on the final exam. In CMSC451, you
explore this more carefully, see more types of NPC problems, and see
more techniques for reducing problems to other problems.
Appendix A has refreshers on things sich as simplifying summations
and helpful rules and formulas involving arithmetic series and
geometric series, and integral approximations.
Appendix B.4 has some more graph-related definitions.