Class Lectures & Homeworks
CSCI 6212 - Design and Analysis of Algorithms
Course Description (3 credits)
Design and analysis of algorithms; Turing machines; NP-complete theory; algorithmic techniques: divide-and-conquer, greedy, dynamic programming, graph traversal, backtracking, and branch-and-bound; applications include sorting and searching, graph algorithms, and optimization.
Lecture 1 - Introduction
Lecture Description
Describe basic algorithmic definitions • Explain and begin to write pseudo code (pseudo-language) • Differentiate between functions and procedures • Show the structure of valid recursion • Explain what analysis of algorithms means, and begin to utilize related elements, including • The big-O notation • The Master Theorem • Stirling’s Approximation • Valuable summation formulas widely used in analysis of algorithms
Lecture Note
Lecture 2 - DATA STRUCTURES – PART I
Lecture Description
Explain what a data structure is, and what it means to design a data structure • Indicate when a data structure is needed, and specify the data structure that matches the situation • Describe standard data structures such as stacks, queues, singly/doubly linked lists, and discuss and compare/contrast different implementations of them • Define graphs, graph representations, and basic graph concepts • Define trees, tree representations, and basic related concepts
Lecture Note
Lecture 3 - DATA STRUCTURES – PART II
Lecture Description
Describe binary search trees (BSTs) and heaps • Explain the algorithms for insert, search and delete operations in BSTs, and derive their time complexities • Explain the algorithms of the delete-min and insert operation in heaps, and prove their logarithmic time complexity • Step through a comprehensive, non-trivial data-structure design process (for Union-Find), along with progressive enhancements • Distinguish yet relate between conceptual and physical implementations
Lecture Note
Lecture 4 - DIVIDE & CONQUER – PART I
Lecture Description
Describe the Divide & Conquer algorithmic design technique • Apply the technique to designing algorithms for an important problem, Sorting, in two different ways • Draw and appreciate the strong connection between recursion and Divide & Conquer • Carry out time complexity analysis of Divide & Conquer algorithms, by deriving and solving recurrence relations • Perform worst-case and average-case time complexity analysis
Lecture Note
Lecture 5 - DIVIDE & CONQUER – PART II
Lecture Description
Apply the Divide & Conquer technique in more elaborate ways to design an algorithm for selecting elements of arbitrary ranks from an input array • Carry out more involved time complexity analysis using induction
Lecture Note
Lecture 6 - THE GREEDY METHOD– PART I
Lecture Description
Describe another powerful algorithmic design technique, namely, the Greedy Method • Explain what optimization problems and optimization techniques are • Create and explore different greedy policies • Develop greedy algorithms for several important optimization problems • Prove non-optimality of some greedy solutions • Select the right data structures for some greedy algorithms
Lecture Note
Lecture 7 - THE GREEDY METHOD– PART II
Lecture Description
Prove the optimality of the greedy solution of the Minimum Spanning Tree (MST) problem • Prove the optimality of the greedy solution of the SingleSource Shortest Paths (SSSP) problem
Lecture Note
Lecture 8 - DYNAMIC PROGRAMMING – PART I
Lecture Description
Describe how Dynamic Programming (DP) works, including its major design steps • State and explain the principle of optimality • Prove the principle of optimality holds in some problems, but not in others • Begin to apply DP to derive powerful optimization algorithms • Compare and contrast DP with Divide & Conquer and with the Greedy Method
Lecture Note
Lecture 9 - DYNAMIC PROGRAMMING – PART II
Lecture Description
How Dynamic Programming (DP) works, including its major design steps • The principle of optimality, and how to state in a given problem • How to prove the principle of optimality (by contradiction) • How to apply DP to solve the Matrix Chain Problem, especially the derivation of a recurrence relation, and computing it in a table • How to use the optimal splits recorded in the table to construct the actual optimal solution
Lecture Note
Lecture 10 - GRAPH TRAVERSAL TECHNIQUES
Lecture Description
Describe and apply two graph traversal techniques, namely, Depth-First Search (DFS) and Breadth-First Search (BFS), as well as three tree traversal techniques. Namely, inorder, preoder and postorder traversal • Apply DFS and BFS to solve some standard graph problems, including connectivity, and special cases of shortest paths and minimum spanning trees • Apply DFS to check for biconnectivity and identify articulation points • Use the concepts and insights gained in this lecture to develop new graph algorithms for some interesting problems
Lecture Note
Lecture 11 - BACKTRACKING
Lecture Description
Systematically generate all objects of a finite family, called combinatorial objects (e.g., graphs, strings, permutations, cliques, cycles, etc.) • Describe the Backtracking algorithm for generating combinatorial objects • Specify and represent combinatorial objects of new combinatorial families in a generic, uniform way • Leverage the common components of Backtracking, and devbelop the problem-specific part of the code for each separate (new) combinatorial family
Lecture Note
Lecture 12 - BRANCH AND BOUND
Lecture Description
Describe the all-powerful optimization design technique: Branch & Bound (B&B) • Apply B&B to designing optimality-guaranteeing algorithms for new optimization problems by being able to • Derive valid approximate cost functions for new optimization problems, and • Prove the validity of approximate cost functions • Prove why B&B guarantees optimality when the approximate cost function used by the algorithm satisfies certain conditions
Lecture Note
Lecture 13 - LOWER BOUND THEORY
Lecture Description
Articulate the distinction between algorithm complexity and problem complexity • Describe the notion of lower bounds of computational problems, and explain their significance • Do the same for upper bounds • Explicate the notation of big-O, big-Ω, and big-Θ in the context of complexity of computational problems • Compute the lower bounds of several important problems • Apply certain techniques to derive lower bounds for new problems • Derive the achievable lower bound of sorting • Model comparison-based algorithms, and appreciate the need for models in proving lower bounds
Lecture Note
Lecture 14 - NP-COMPLETE THEORY – PART I
Lecture Description
Describe the definitions of NP, polynomial problems, exponential problems, intractable/undecidable problems • Explain what yes-no problems are, and convert optimization problems into yes-no problems • Develop NP algorithms for NP problems • Describe in preliminary terms polynomial-time transforms between yes-no problems
Lecture Note
Lecture 15 - NP-COMPLETE THEORY – PART II
Lecture Description
Taxonomy of computational problems • Yes-no problems • The NP class/family and its significance • Definition of NP problems and NP algorithms • Development of NP algorithms for a number of NP problems