Computer Algorithms

Sara Baase is a Professor of Computer Science at San Diego State University, and has been teaching CS for 25 years. Dr. Baase is a three-time recipient of the San Diego State University Alumni Association's Outstanding Faculty Award, and she has written a number of textbooks in the areas of algorithms, assembly language and social and ethical issues related to computing. She earned her doctorate at the University of California, Berkeley. Allen Van Gelder is a Professor of Computer Science at the University of California at Santa Cruz, where he has been teaching CS for 12 years. He received his Ph.D. in Computer Science at Stanford University, and is a past recipient of the Presidential Young Investigator Award. 0201612445AB04062001

1. Analyzing Algorithms and Problems: Principles and Examples.


Introduction.



Java as an Algorithm Language.



A Usable Subset of Java.



Organizer Classes.



Java-Based Pseudocode Conventions.



Mathematical Background.



Sets, Tuples, and Relations.



Algebra and Calculus Tools.



Elements of Logic.



Analyzing Algorithms and Problems.



Correctness.



Amount of Work Done.



Average and Worst-Case Analysis.



Space Usage.



Simplicity.



Optimality.



Lower Bounds and the Complexity of Problems.



Implementation and Programming.



Classifying Functions by their Asymptotic Growth Rates.



Definitions and Notation.



How Important Is Asymptotic Order?



Properties of O, Theta, and Omega.



The Asymptotic Order of Commonly Occuring Sums.



Searching an Ordered Array.



Some Solutions.



Worst-Case Analysis of Binary Search.



Average-Behavior Analysis.



Optimality.



2. Data Abstraction and Basic Data Structures.


Introduction.



ADT Specifications and Design Techniques.



ADT Specifications.



ADT Design Techniques.



Elementary ADTs — Lists and Trees.



Recursive ADTs.



The List ADT.



Binary Tree ADT.



The Tree ADT.



In-Tree ADT.



Stacks and Queues.



Stack ADT.



Queue ADT.



ADTs for Dynamic Sets.



Priority Queue ADT.



Union-Find ADT for Disjoint Sets.



Dictionary ADT.



3. Recursion and Induction.


Introduction.



Recursive Procedures.



Activation Frames and Recursive Procedure Calls.



Hints for Recursion — Method 99.



Wrappers for Recursive Procedures.



What is a Proof?



Induction Proofs.



Induction Proof Schema.



Induction Proof on a Recursive Procedure.



Proving Correctness of Procedures.



Definitions and Terminology.



Elementary Control Structures.



The Single-Assignment Paradigm.



Procedures with Loops.



Correctness Proofs as a Debugging Tool.



Termination of Recursive Procedures.



Correctness of Binary Search.



Recurrence Equations.



Recursion Trees.



Divide-and-Conquer, General Case.



Chip and Conquer, or be Conquered.



Why Recursion Trees Work (*).



4. Sorting.


Introduction.



Insertion Sort.



The Strategy.



The Algorithm and Analysis.



Lower Bounds on the Behavior of Certain Sorting Algorithms.



Divide and Conquer.



Quicksort.



The Quicksort Strategy.



The Partition Subroutine.



Analysis of Quicksort.



Improvements on the Basic Quicksort Algorithm.



Merging Sorted Sequences.



Worst Case.



Optimality of Merge.



Space Usage.



Mergesort.



Lower Bounds for Sorting by Comparison of Keys.



Decision Trees for Sorting Algorithms.



Lower Bound for Worst Case.



Lower Bound for Average Behavior.



Heapsort.



Heaps.



The Heapsort Strategy.



FixHeap.



Heap Construction.



Implementation of a Heap and the Heapsort Algorithm.



Accelerated Heapsort.



Comparison of Four Sorting Methods.



Shellsort.



The Algorithm.



Analysis and Remarks.



Radix Sorting.



Using Properties of the Keys.



Radix Sort.



5. Selection and Adversary Arguments.


Introduction.



The Selection Problem.



Lower Bounds.



Adversary Arguments.



Tournaments.



Finding max and min.



Finding the Second-Largest Key.



Introduction.



The Tournament Method.



An Adversary Lower-Bound Argument.



Implementation of the Tournament Method for Finding max and secondLargest.



The Selection Problem.



A Divide-and-Conquer Approach.



A Linear-Time Selection Algorithm (*).



Analysis of the Selection Algorithm (*).



A Lower Bound for Finding the Median.



Designing Against an Adversary.



6. Dynamic Sets and Searching.


Introduction.



Array Doubling.



Amortized Time Analysis.



Red-Black Trees.



Binary Search Trees.



Binary Tree Rotations.



Red-Black Tree Definitions.



Size and Depth of Red-Black Trees.



Insertion into a Red-Black Tree.



Deletion from a Red-Black Tree.



Hashing.



Closed Address Hashing.



Open Address Hashing.



Hash Functions.



Dynamic Equivalence Relations and Union-Find Programs.



Dynamic Equivalence Relations.



Some Obvious Implementations.



Union-Find Programs.



Weighted Union.



Path Compression.



Analysis of wUnion and cFind (*).



Applications.



Priority Queues with a Decrease Key Operation.



The Decrease Key Operation.



Pairing Forests.



7. Graphs and Graph Traversals.


Definitions and Representations.



Some Examples.



Elementary Graph Definitions.



Graph Representations and Data Structures.



Traversing Graphs.



Overview of Depth-First Search.



Overview of Breadth-First Search.



Comparison of Depth-First and Breadth-First Searches.



Depth-First Search and Recursion.



Finding Connected Components with Depth-First Search.



Depth-First Search Trees.



A Generalized Depth-First Search Skeleton.



Structure of Depth-First Search.



Directed Acyclic Graphs and Topological Sort.



Strongly Connected Components of a Directed Graph.



Definitions.



A Strong Component Algorithm.



Analysis.



Biconnected Components of an Undirected Graph.



Articulation Points and Biconnected Components.



The Bicomponent Algorithm.



Analysis.



Generalizations.



8. Graph Optimization Problems and Greedy Algorithms.


Introduction.



Prim’s Minimum Spanning Tree Algorithm.



Definition and Examples of Minimum Spanning Trees.



An Overview of the Algorithm.



Properties of Minimum Spanning Trees.



Correctness of Prim’s MST Algorithm.



Managing the Fringe Efficiently with a Priority Queue.



Implementation.



Analysis (Time and Space).



Lower Bound.



Single-Source Shortest Paths.



Background.



Properties of Shortest Paths.



Dijkstra’s Shortest-Path Algorithm.



Implementation.



Kruskal’s Minimum Spanning Tree Algorithm.



Analysis.



9. Transitive Closure, All-Pairs Shortest Paths.


The Transitive Closure of a Binary Relation.



Definitions and Background.



Finding the Reachability Matrix by Depth-First Search.



Transitive Closure by Short Cuts.



Warshall—s Algorithm for Transitive Closure.



The Basic Algorithm.



Warshall—s Algorithm for Bit Matrices.



Distances in Graphs.



Computing Transitive Closure by Matrix Operations.



Multiplying Bit Matrices — Kronrod’s Algorithm.



Introduction.



Kronrod—s Algorithm.



Lower Bound (*).



10. Dynamic Programming.


Introduction.



Multiplying a Sequence of Matrices.



Constructing Optimal Binary Search Trees.



Separating Words into Lines.



Some Comments on Developing a Dynamic Programming Algorithm.



11. String Matching.


A Straightforward Solution.



The Knuth-Morris-Pratt Algorithm.



Pattern Matching with Finite Automata.



The Knuth-Morris-Pratt Flowchart.



Construction of the KMP Flowchart.



Analysis of the Flowchart Construction.



The Knuth-Morris-Pratt Scan Algorithm.



The Boyer-Moore Algorithm.



The New Idea.



And the “Old” Idea.



The Boyer-Moore Scan Algorithm.



Remarks.



Approximate String Matching.



Exercises.



12. Polynomials and Matrices.


Introductory Comments.



Evaluating Polynomial Functions.



Algorithms.



Lower Bounds for Polynomial Evaluation.



Preprocessing of Coefficients.



Vector and Matrix Multiplication.



Review of Standard Algorithms.



Winograd’s Matrix Multiplication.



Lower Bounds for Matrix Multiplication.



Strassen’s Matrix Multiplication.



The Fast Fourier Transform and Convolution (*).



Introduction.



The Fast Fourier Transform.



Convolution.



Appendix: Complex Numbers and Roots of Unity.



13. NP-Complete Problems.


P and NP.



Decision Problems.



Some Sample Problems.



The Class P.



The Class NP.



The Size of the Input.



NP-Complete Problems.



Polynomial Reductions.



Some Known NP-Complete Problems.



What Makes a Problem Hard?



Optimization Problems and Decision Problems.



Approximation Algorithms.



Bin Packing.



The First Fit Decreasing Strategy.



Other Heuristics.



The Knapsack and Subset-Sum Problems.



Graph Coloring.



Some Basic Techniques.



Approximate Graph Coloring Is Hard.



Wigderson’s Graph Coloring Algorithm.



The Traveling Salesperson Problem.



Greedy Strategies.



The Nearest Neighbor Strategy.



The Shortest Link Strategy.



How Good Are the TSP Approximation Algorithms?



Computing with DNA.



The Problem and an Overview of the Algorithm.



DNA Background.



Adleman’s Directed Graph and the DNA Algorithm.



Analysis and Evaluation.



14. Parallel Algorithms.


Parallelism, the PRAM, and Other Models.



Introduction.



The PRAM.



Other Models.



Some PRAM Algorithms.



The Binary Fan-In Technique.



Some Easily Parallelizable Algorithms.



Handling Write Conflicts.



Boolean or on n Bits.



An Algorithm for Finding Maximum in Constant Time.



Merging and Sorting.



Introduction.



Merging.



Sorting.



Finding Connected Components.



Strategy and Techniques.



The Algorithm.



PRAM Implementation of the Algorithm.



Analysis.



A Lower Bound for Computing a Function on n Bits.



A: Java Examples and Techniques.


A Java “Main Program.”



Library IntListLib Examples.



Generic Order and the “Comparable” Interface.



Copy via the “Clone” Interface.



Subclasses Extend the Capability of Their Superclass. 0201612445T04062001