CSE 373: Data Structures and Algorithms (Winter 2016)  

ReadingsLinks 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 UNIONFIND" lecture:
Wikipedia article on the disjointset data structure.
Reading for the "Disjoint Sets and UNIONFIND" lecture:
Wikipedia article on the disjointset data structure.
(Optional) reading for the "Applying UNIONFIND" lecture:
Wikipedia article on connectedcomponent labeling.
Optional reading on graphs:
"Graph Theory" by Victor Adamchik at CarnegieMellon University.
Reading for the "Minimum Spanning Trees" lecture:
the Wikipedia article on Kruskal's algorithm.
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 "DivideAndConquer 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 NPCompleteness" lecture:
the Wikipedia article on
NPCompleteness.
Reading for the "Algorithms and Problem Solving" lecture:
To be announced later.


University of Washington, Winter, 2016 