Readings

Links to online readings will be provided as needed during the course.

Reading for the "Introduction" lecture: Either: the Wikipedia article on Abstract Data Types, or the Mark Weiss book's section 1.1 "What's the Book About?" and section 3.1 "Abstract Data Types (ADTs)".
The Wikipedia definition for an abstract data type is a good one:

In computer science, an abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.

A nice summary of key ideas is provided at the Univ. of Wisconsin's web site on Abstract Data Types.

Reading for the "Proof by Induction" lecture: Explanation by Elizabeth Stapel at Purple Math. Another resource is Khan's online lecture at the Khan Academy. In Weiss, look at section 1.2 "Mathematics Review". The posted lecture slides PDF file on "Induction and Its Applications" can also be considered a reference.

Reading for the "Math Review" lecture: For a refresher on sets, binary relations, and functions, read this mathematical background paper. The data file for exponential growth is available here, and you can play with it in Excel as suggested in the lecture slides.

The definitions that you need to learn for Big O, Big Omega, and Big Theta are described in the lecture slides. For a more detailed explanation of what these mean, where they came from, etc., see the rather thorough Wikipedia article on Big O notation. Beware of the issue described there as "abuse of notation."

Reading for the "Dictionaries" lecture ...
For the concept of a dictionary: Associative Array article in Wikipedia.

Reading for the "AVL Trees" lecture ...
For a basic discussion: AVL trees at the Univ. of Auckland

Reading for the "Hashing I" lecture: Wikipedia article on hash tables. (through the section on separate chaining).

Reading for the "Hashing II" lecture: Wikipedia article on hash tables. (section on open addressing). The demo of hashing and collision resolution via separate chaining is also helpful.

Reading for the "Disjoint Sets and UNION-FIND" lecture: Wikipedia article on the disjoint-set data structure.

(Optional) reading for the "Applying UNION-FIND" lecture: Wikipedia article on connected-component labeling.

Optional reading on graphs: "Graph Theory" by Victor Adamchik at Carnegie-Mellon University.

Reading for the "Minimum Spanning Trees" lecture: the Wikipedia article on Kruskal's algorithm.

Stoimen's Web Log, article on "Computer Algorithms: Topological Sort of a Graph".

Comparison Sort (on Wikipedia). This page also contains links to separate articles on numerous specific sorting algorithms, such as Insertion Sort, Quick Sort, Heap Sort, etc.

(see previous entry)

Reading for the "Beyond Comparison Sorting" lecture: the Wikipedia articles on Bucket Sort and Radix Sort.

Reading for the "Algorithm Design Paradigms" lecture: the Wikipedia articles on Algorithm Design Paradigms. This article contains links to four additional articles: "Divide and Conquer" (reading for the following lecture), "Dynamic Programming" (do read this), "Greedy Algorithm" (do read this), and "Backtracking" (do read this).

Reading for the "Divide-And-Conquer Algorithms Paradigm" lecture: the Wikipedia articles on Divide and conquer algorithms and the Fast Fourier Transform. At the website An Interactive Guide To The Fourier Transform, the Fourier Transform is described as a method for converting a smoothie to a smoothie recipe. It's a clever way to describe the transformation performed by this transform.

Reading for the "P vs. NP and NP-Completeness" lecture: the Wikipedia article on NP-Completeness.

Reading for the "Algorithms and Problem Solving" lecture: To be announced later.