CS-251A Data Structures and Algorithms

Lecture Descriptions, Homework and Play

Text Book: Data Structures and Algorithms in JAVA by Michael Goodrich and Roberto Tamassia

Week: 1-2-3-4-5-6-7-8-9-10-11-12-13-14

Week 1-Sept 2

Lecture #1: Induction Proofs

1. Introduce course
2. Introduction to induction proofs
1. Example of 3-coloring triangulated polygons

Problem Assignment #1 - due September 16

1. Induction proof (triangles in arrangements of lines)
2. Induction proof (sum of squares of numbers)
3. Induction proof (circle map coloring)
4. The collapsing compass computer (translate a segment)

Reading Assignment

1. Text: Preface and Chapter 1
2. Web: 2.1 - Notes on methods of proof

Suggested Play

1. Web: 1.1.3 - Pythagoras proof applets
2. Web: 1.2.1 - Straight-edge-and-compass constructions applet of Francois Labelle

Week 2-Sept 7 and 9

Lecture #2: Ancient Models of Computation

1. The collapsing compass computer
1. Euclid's second proposition
2. Constructive (direct) proofs
3. Case-analysis in proofs

1. The sum of the first n natural numbers
1. Constructive direct proof
2. Induction proof
2. Proof by contradiction
1. Number of prime numbers
2. Diameter of a convex polygon
3. Constructive case analysis
1. 3-coloring the plane
4. Counting regions in the plane
1. Arrangement of lines

Reading Assignment

1. Text: 2.1 - 2.6, 2.13, 2.14, 7.1
2. Web: 1.2.10.2 - A New Look at Euclid's Second Proposition (Handout)
3. Web: 2.1 - Notes on methods of proof

Suggested Play

1. Web: 1.2.7.1 - Euclid's second proposition applet
2. Web: 1.1.3.1 - Pythagoras' theorem applet
3. Web: 1.2.3 - The straight edge and compass
4. Web: 2.2 - Classical fallatious proofs

Week 3-Sept 14 and 16

Lecture #4: Graphs

1. If and only if
2. Graph theory terminology
3. Properties of trees
4. Inductive proof of Euler's formula
5. Strong induction: triangulating polygons via diagonal insertion

Lecture #5: Big "Oh" notation

1. QUIZ #1, homework #1 due, homework #2 out (due Sept. 30)
2. Big "Oh" Notation
3. Minimal spanning trees

Problem Assignment #2

1. Growth of functions
2. Big "Oh" notation
3. Recursion and the Fibonacci function
4. Minimal spanning trees of points

Reading Assignment

1. Text: 2.7 - Euler's formula
2. Web: 4.1 - Interactive introduction to graph theory
3. Web: 4.2 - Introduction to graph theory (Luc Devroye's notes)
4. Text: 2.11 - Arithmetic-Geometric Mean Inequality
5. Web: 4.4 - Web Tutorials: Introduction to Graph Theory
6. Web: 1.3.1, 1.3.2, 1.4.1, 1.4.1.1- Turing Machines, RAM's, Complexity and Recursion
7. Text: 3.1, 3.2 - Big "Oh" notation

Suggested Play

1. Web: 20.3 - Minimal spanning tree applet
2. Web: 4.11 - Euler's theorem
3. Web: 20.1.2.1 - Triangulating polygons via ear-cutting (Ian Garton's tutorial with applet)
4. Web: 20.2 - Art Gallery Theorem (applet)

Week 4-Sept 21 and 23

Lecture #6: Turing Machines and Random Access Machines

1. Review quiz #1
2. Little "oh" notation, L'Hospital's rule
3. Digital models of computation
1. Turing machines
2. Random access machines
4. Ceiling and floor functions
1. Computing the maximum gap in O(n) time

Lecture #7: Recursion

1. More on maximum gap
2. Recurrence Relations and Fibonacci sequences

Reading Assignment

1. Web: 1.3.1 - Introduction to Turing machines
2. Web: 1.3.2 - Turing machines and Random Access Machines
3. Text: Chapter 3
4. Web: 1.4.1.1 - Recursion (Luc Devroye's class notes)

Suggested Play

1. Web: 1.4.1.1 - Fibonacci math
2. Web: 1.4.1.1 - Fibonacci and nature
3. Web: 1.4.1.1 - Fibonacci home page

Week 5-Sept 28 and 30

Lecture #8:

1. Algorithms for computing the Fibonacci function
1. Exponential - O(2^n)
2. Linear - O(n)
3. Logarithmic - O(log n)
2. More induction
1. Triangulating sets of points
2. Two-ears theorem

Lecture #9: QUIZ #2, homework #2 due, homework #3 out (due Oct 14)

1. Binary search
2. A master theorem of recursion
3. Divide and conquer
4. Sorting
1. Insertion sort
2. Selection sort
3. Bubble sort
4. Divide and conquer (merge sort)
5. Bucket sort with floor functions

Problem Assignment #3

1. Turing machines
2. Matrix powering and the Fibonacci function
3. The skyline problem (Divide and Conquer)
4. Graphs (properties of vertices of odd degree)

Reading Assignment

1. Text: 9.2 - Exponentiation
2. Text: 5.6 - The skyline problem (divide and conquer)
3. Text: Chapter 6 up to and including 6.4.3
4. Web: 1.4.1.1 - Fibonacci algorithms (David Eppstein)
5. Web: 20.1.2.3 - Two-Ears theorem (Ian Garton)
6. Web: 19.2.1.6 - Bucket sorting with floor functions

Suggested Play

1. Web: 1.4.1.6 - Fibonacci numbers and domino tilings
2. Web: - 19.2.1.1 - Sorting animation applets

Week 6 - October 5 and 7

Lecture #10:

1. Lower bounds on the complexity of problems (comparison model of computation)
1. Searching in a list (optimality of sequential search)
2. Searching in an ordered list (optimality of binary search)
3. Optimality of merge-sort (decision trees)

Lecture #11:

1. Proof that bucket-sort takes O(n) expected time
2. Searching data bases:
1. Range search
2. Nearest neighbor search

Reading Assignment

1. Text: 6.4.6 - Lower bound for sorting
2. Web: 1.4.2 - Lower bounds (Luc Devroye's class notes)
3. Handout: Range searching (geometric searching)
4. Web: 6.7.1 - Projection methods for nearest neighbor search

Suggested Play

1. Web: 1.4.2 - MasterMind applet (decision trees)
2. Web: 6.7.1 - Nearest neighbor search applet

Week 7 - Oct 12 and 14

Lecture #12:

1. Prune-and-search methods:
1. Finding an ear of a polygon in linear time
1. Point-in-polygon problems
2. Area of a polygon
3. The geometric series
4. Proof that a reflex vertex admits a diagonal

Lecture #13: homework #3 due, homework #4 out (due Oct 28 but postponed to Nov 2)

1. Finding the closest pair:
1. By brute force
2. By induction
3. Via repeated nearest neighbor searches
4. The nearest neighbor graph
5. The closest-pair via divide and conquer
1. In one dimension in O(n log n) time
2. In two dimensions
1. In O(n log^2 n) time
2. In O(n log n) time

Problem Assignment #4

1. Number of comparisons in binary search
2. Element uniqueness
3. Non-collinearity of points
4. Computing maximal points of a set

Reading Assignment

1. Handout: Area of a polygon
2. Text: 8.2 - Point-in-polygon testing
3. Web: 14.1 - The geometric series
4. Web: 14.2 - Finding an ear in linear time with prune-and-search
5. Text: 8.5 - Closest pair

Suggested Play

1. Web: 14.2 - Ear-cutting applet

Week 8 - Oct 19 and 21

Lecture #14:

1. Binary search trees:
1. Inserting and deleting items from BST's
2. The Euler-Tour traversal of a tree
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
2. One-dimensional range searching
3. Balanced multi-way search trees I:
1. 2-4 trees
2. Inserting items in 2-4 trees

Lecture #15: QUIZ #3

1. Balanced multi-way search trees II:
1. Deleting items from 2-4 trees
2. Applications:
1. Plane-sweep algorithm for closest-pair searching

Reading Assignment

1. Text: 4.3.3 - Binary search trees
2. Web: 5.1.2 - Tree traversals (preorder, inorder and postorder)
3. Web: 5.1 - Introduction to trees (Luc Devroye's class notes)
4. Web: 5.3.3 - Binary search trees (Luc Devroye's class notes)
5. Web: 5.5.1 - (2,3,4)-trees

Suggested Play

1. Web: 5.3.3 - Binary search tree applet (Luc Devroye's class notes)
2. Web: 5.1 - Tree traversal applet (Luc Devroye's class notes)
3. Web: 6.8.1 - Closest-pair applet

Week 9 - Oct 26 and 28

Lecture #16:

1. Review solutions to quiz #3
2. Graph isomorphism
3. Graph planarity
4. Eulerian tours and the Konigsberg bridge problem

Lecture #17:

1. The Euler-Hierholzer Theorem
2. Searching mazes and labyrinths
1. Ancient Greek algorithm (Ariadne's thread)
2. Gaston Tarry's algorithm (1895)

Reading Assignment

1. Web: 4.2 - Introduction to graphs (Luc Devroye's class notes)
2. Web: 4.3 - Graph isomorphism
3. Web: 4.4 - Graph planarity
4. Web: 4.14 - The Bridges of Konigsberg Problem
5. Web: 4.6.2 - Euler circuits
6. Text: 7.2 - Eulerian graphs
7. Text: 4.6 - Adjacency matrix
8. Handout: Doubly-connected edge list
9. Web: 6.3.1 - Depth-first search (Luc Devroye's class notes)
10. Web: 6.4 - Breadth-first search (Luc Devroye's class notes)

Suggested Play

1. Web: 4.2 - Adjacency matrix and list applet
2. Web: 6.1.1 - A Maze Game
3. Web: 6.1.2 - 3D Maze Applet
4. Web: 6.3.1.1 - Depth-first search applet
5. Web: 6.4.1 - Breadth-first search applet

Week 10 - Nov 2 and 4

Lecture #18: homework #4 due, homework #5 out (due Nov 16)

1. Data structures for graphs
1. Adjacency matrices
2. Adjacency lists
3. Doubly-connected edge lists for plane graphs
2. Depth-first search in a graph
3. Breadth-first search in a graph
4. Hill climbing algorithms
5. Greedy algorithms
1. The diameter of a convex polygon
1. Via depth-first search

Problem Assignment #5

1. Balanced search trees (2-4-trees)
2. Planar graphs
3. Hamiltonian graphs

Lecture #19:

1. Hamiltonian graphs
1. Relation to Eulerian graphs
2. Digraphs and tournaments
1. Proof that tournaments are Hamiltonian
3. Dense graphs
1. Proof of Ore's theorem on Hamiltonicity of dense graphs
4. The diameter of a convex polygon
1. Via rotating caliper graph
2. Proof that the diameter is an antipodal pair

Reading Assignment

1. Text: 7.3 - Depth-first search and breadth-first search
2. Web: 4.16 - Rotating caliper graph
3. Handout: Multiway trees: 2-4-trees
4. Text: 7.12 - Hamiltonian tours

Suggested Play

1. Web: 20.6 - Polygonization applet

Week 11 - Nov 9 and 11

Lecture #20:

1. Simple Hamiltonian cycles in point sets:
1. Polygonizing planar sets of points
1. Star-shaped polygonizations
2. Monotonic polygonizations
3. Spiral polygonizations
2. Orthogonal polygonizations
1. Reconstructing simple polygons from their vertex set
2. Testing self-intersections in polygons
3. Computing segment intersections via plane-sweep technique and balanced search trees

Lecture #21: QUIZ #4

1. Map and graph coloring:
1. Dual graphs
2. Two-colorability
1. Maps determined by arrangements of lines and circles
2. Closed-curve maps
3. The scheduling problem as graph coloring
1. Cromatic number of a graph

Reading Assignment

1. Handout: Rotating calipers and diameter
2. Text: 8.3 - Constructing simple polygons
3. Text: 8.6 - Intersections of horizontal and vertical segments
4. Web: 4.13.1 to 4.13.5 - Map coloring

Suggested Play

1. Web: 20.6 - Polygonization applet
2. Web: 20.6.1 - Polygon reconstruction applet (orthogonal connect-the-dots)
3. Web: 4.11.1 - Minimum spanning tree applet

Week 12 - Nov 16 and 18

Lecture #22: homework #5 due, homework #6 out (due Dec 2)

1. Induction proof of 5-color theorem
2. Three-colorability
1. Triangulated polygons
2. Line-arrangement graphs
3. O(n^2 log n) time algorithm
3. Minimum spanning trees
1. Kruskal's algorithm
2. Baruvka's algorithm

Problem Assignment #6

1. Greedy algorithms and least-cost Hamiltonian cycles in graphs
2. Hamiltonian cycles in dense graphs (Ore's theorem)
3. Convex hulls of points

Lecture #23:

1. Convex hulls of points:
1. Rosenberg & Landgridge algorithm - O(n^3)
2. Jarvis Algorithm (gift wrapping) - O(nh)
1. Expected number of points on the convex hull
3. Beneath-beyond algorithm - O(n^2)
4. Divide-and-conquer - O(n log n)
5. Graham's algorithm - O(n log n)
1. The 3-coins algorithm for monotone polygons and chains in O(n) time
6. Lower bound on the complexity of the convex hull problem via reduction from sorting

Reading Assignment

1. Text: 7.6 - Minimum-cost spanning trees
2. Web: 4.11.1 - Minimum spanning trees (Luc Devroye's class notes)
3. Web: 4.11.2 - Minimum spanning trees (David Eppstein's class notes)
4. Web:4.11.3 - Kruskal's algorithm tutorial
5. Text: 8.4 - Convex hulls
6. Web: 20.10 - Convex hulls of points

Suggested Play

1. Web: 4.11.3 - Kruskal algorithm applet
2. Web: 20.10 - Convex hull applets

Week 13 - Nov 23 and 25

Lecture #24:

1. Priority queues via the heap data structure
1. application to sorting (heapsort)
2. application to minimum spanning trees (Kruskal's algorithm)
2. More convex hulls
1. Throw-away principle - O(n) expected time (Quickhull)

Lecture #24: Course Evaluations

1. Prune-and-search methods revisited:
1. Quicksort
2. Randomized quicksort
3. Selection
1. Via sorting
2. Via heaps
3. Randomized selection
4. Finding the median of a set of numbers in linear time

Reading Assignment

1. Text: 4.3.2 - Heaps
2. Web: 5.6 - Tutorial on heaps
3. Web: 19.2.1.4 - Heapsort tutorial
4. Web: 19.2.2 - Selection and order statistics
5. Web: 14.3 - Linear time selection (Luc Devroye's course notes)
6. Web: 14.4 - Linear time selection (David Eppstein's course notes)

Suggested Play

1. Web: 5.6 - Heap applet

Week 14 - Nov 30 and Dec 2

Lecture #26: Review course material

Lecture #27: In-Class 75-minute Test