Readings
Unless otherwise noted, the readings are in Miller & Ranum, 2nd edition.
Except for the material in the Introduction chapter,
the readings related to Python are optional.
The online version of the textbook
does not use either chapter numbers, section numbers or page numbers.
Consequently, particular parts of the textbook are identified here by giving
the names of the chapter, section, and in some cases, subsection.
For convenient access by date, these readings are indexed and linked from
our
course calendar.
Reading for the "Introduction" lecture:
In the "Introduction" chapter, optionally read sections "Objectives"
through "What is Programming?" Then read "Why Study Data Structures
and Abstract Data Types?"
and "Why Study Algorithms?"
Here's another link to
Miller and Ranum.
Reading for the "A Little Python" lecture:
In the "Introduction" chapter, read section "Review of Basic Python"
through "Summary." If you want more details on Python, then
read or consult a reference or a tutorial such as
the tutorial at Python.org.
Reading for the "Math Review" lecture:
There is no special reading for this lecture. The data file for exponential growth is
available
here, and you can play with it in Excel
as suggested in the lecture slides.
Reading for the "Asymptotic Analysis" lecture:
In the "Analysis" chapter, read all sections.
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.
For the Python dict class: the last part of
the "Introduction" chapter's section on "Getting Started with Data: Built-in Collection Data Types".
For the binary-search-tree approach to dictionaries, M&R chapter on
"Tree and Tree Algorithms" sections starting with "Binary Search Trees"
and ending with "Search Tree Analysis."
Reading for the "Binary Search Trees" lecture:
In the "Trees and Tree Algorithms" chapter, read section "Balanced
Binary Search Trees."
Reading for the "AVL Trees" lecture:
In the "Trees and Tree Algorithms" chapter, read section "AVL Tree Performance" through "Summary."
Reading for the "Priority Queues" lecture:
In the "Trees and Tree Algorithms" chapter, read sections "Priority Queues
with Binary Heaps" and "Binary Heap Operations."
Reading for the "Binary Heaps" lecture:
In the "Trees and Tree Algorithms" chapter, read section
"Binary Heap Implementation."
Reading for the "Hashing" lecture:
In the "Sorting and Searching" chapter, in section
"Hashing" read the subsection on Hash Functions.
Reading for the "Hashing II" lecture:
In the "Sorting and Searching" chapter, in section
"Hashing" read the subsection on Collision Resolution.
Reading for the "Graphs" lecture:
In the "Graphs and Graph Algorithms" chapter, sections
"Objectives" through "Implementation."
Reading for the "Topological Sorting" lecture:
In the "Graphs and Graph Algorithms" chapter, the section
"Topological Sorting" and the (earlier in the chapter) sections
on "The Word Ladder Problem" through "Breadth First Search Analysis."
Reading for the "Shortest Paths" lecture:
In the "Graphs and Graph Algorithms" chapter, sections
"Shortest Path Problems" through "Analysis of Dijkstra's Algorithm."
Reading for the "Implicit Graphs" lecture:
In the "Graphs and Graph Algorithms" chapter, sections
"The Knight's Tour Problem" through "Depth First Search Analysis."
Reading for the "Comparison Sorting" lecture:
In the "Sorting and Searching" chapter, sections
"The Bubble Sort" through "The Merge Sort."
Reading for the "More Sorting" lecture:
In the "Sorting and Searching" chapter, sections
"The Quick Sort" and "Summary."
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 "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.
(Optional) reading for the "Programming Languages" lecture:
To be announced later.