Readings
05/02
We have been discussing 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). This
material can also be seen in Chapter 22 and Appendix B.4 of CLRS. We will
continue to explore graph problems (and problems that can be expressed as
graphs) over the next two class sessions, leading us into a discussion of
NP-Complete problems.
04/22
We discussed optimization problems in general, and the dynamic
programming solution, and greedy solution, to one in class last week.
You can read through Chapter 16, sections 1 and 2 to see more
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.
04/05
We will be discussing linear-time sorting algorithms that are not
comparison-based (Chapter 8). We will refresh on why comparison-based
sorting is known to require Ω(nlogn)
comparisons,
and then discuss several ideas for linear-time sorting algorithms, such
as spaghetti
sort, counting sort, radix sort, and bucket sort. We will discuss their
limitations and ways in which to determine their run-times.
03/30
Today we will discuss tree-related topics (Chapters 12 and 13). We will
look at the binary search tree, discuss the AVL and Red/Black and Splay
variations on the binary search tree. We will discuss the Heap structure
and how it can be used in a comparison-based sort (Chapter 6). We will
not cover the full chapters, but rather discuss the key concepts. You
should read these chapters (or equivalent material on these structures)
for a more complete discussion of related algorithms.
03/15
We have been discussing QuickSort (Chapter 7) in class. We explored the
best case, and the worst case(s). We explored the nature of this divide
and conquer algorithm, and saw that even if the division was a small
percentage, we would have cnlogn run-time.
We also analyzed the expected run-time of the algorithm over all
possible input scenarios.
03/02
We have now completed our coverage of Chapter 9 material (min, max,
min and max together, median finding and general selection).
I did not assign this reading in advance due to how I wanted to
present the material, but you might find the discussion in the text
gives a different discussion of the same material.
02/18
We are currently working on Chapter 4 material (solving recurrences) in class.
As we look at a few more recursive trees, we will work towards seeing where
there are patterns (which may help us when designing algorithms), and
also discuss the Master Theorem (and its weaknesses).
02/14
Read Chapter 3, page 49 for a list of transitivity, reflexivity,
symmetry, and also transpose symmetry for asymptotic relationships.
We will continue our discussion of solving recurrences on Thursday.
02/11
Read Chapter 3 for more formal definitions and discussion of Big-O,
Big-Omega, and Theta. On Tuesday we will complete this topic (specifically
the use of limit-based definitions) and then revisit the question of how
to solve recurrences if we aren't told what the general growth function
looks like (ie: how do we make a good guess to start).
02/07
Read Chapter 2, Section 1 for more discussion of Insertion Sort and/or
to see how the text presents pseudocode.
Read Chapter 2, Section 2 for more analysis of Insertion Sort (the book
discusses the various costs we can consider), and discussion of the
random access machine (RAM) model.
Read Chapter 2, Section for more discussion or Merge, and if you want
to read ahead for Thursday's discussion of MergeSort.
01/30
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.
Assuming we are looking at comparisons, and working on the assumption
that you can perform 220 comparisons per second, consider
approximately how large n could be so that you could solve a
problem of each of the following complexities in the specified time
period.
|
1 Second | 1 Minute | 1 Hour | 1 Day | 1 Month | 1 Year | 1 Century
|
| log2n | | | | | | | |
|---|
| n | | | | | | | |
|---|
| n log2n | | | | | | | |
|---|
| n2 | | | | | | | |
|---|
| n3 | | | | | | | |
|---|
| 2n | | | | | | | |
|---|