CS 704 Algorithms

by Rajeev Wankar

Brief Description

In this course you will learn several fundamental principles of algorithm design. You'll learn the divide-and-conquer design paradigm, with applications to fast sorting, searching, and multiplication. You will learn how to apply greedy and dynamic programming for some problems and compute the complexity of algorithms. Backtracking and Branch and bound algorithms give solution to many intereting problems, you will learn few of them. We will study how graph-processing algorithms, including minimum spanning tree and shortest paths algorithms work. The theory of NP Hard and Complete problems will also be discussed. We will also study string processing algorithms.

Required Materials

Lecture Notes

• Introduction
  • 1. Introduction to Algorithms, history, Basic Algorithms analysis, Estimation of running time [Extra Slides on Analysis]
• Elementry Data Structures
  • 2. Tree, Binary Tree, Heap. Heap creation algorithms and complexity
  • 3. Heap sort and complexity, Disjoint Union & Find, Complexity, applications
• Divide and Conquer
  • 4. Control Abstraction, Binary Search & complexity, MaxMin, MergeSort & Complexity
  • 5. QuickSort & Complexity, Strassen Matrix Multiplication & Complexity
• Greedy Techniques
  • 6. Knapsack problem, Huffman Code, Single Source Shortest Path Problem & Complexity,
• Dynamic Programming
  • 7. Principle of Optimality, D&C Vs Greedy Vs Dynamic Programmng, DynamicFloyd’s Algorithm for All pairs shortest path problem & Complexity, 0-1 Knapsack problem, Recursive Formula for subproblems
• Basic Search and Traversal Techniques
  • 8. Search and traversal techniques for graphs, Breadth First Search (BFS)& Complexity, Depth First Search (DFS)& Complexity,Code Optimization
• Backtracking
  • 9. Definitions, Formulation, N-Queens problem, Terminology regarding tree organization of solution space, Graph Coloring Problem & Complexity
• Branch and Bound
  • 10. LC Search, N-Queens Problem
• NP-Hard and NP-Complete Problems
  • 11. Non deterministic algorithms, Nondeterministic decision algorithm, Classes P & NP, NP-Complete, NP-Hard, Non deterministic Satisfiability
• String Matching
  • 12. Strings, Pattern matching algorithms, Brute-force algorithm, Boyer-Moore algorithm, Knuth-Morris-Pratt algorithm, Complexity, Demos

  ---

  Assignmenets

• Homework: hw0, hw1, hw2, hw3, hw4, hw5
• Exams: midterm 1, midterm 2, final