CS253 Sylabus & Progress

CS253 Syllabus

Introduction

Search:

Book material: click here (for reference only)
Computer program = algorithm + data structure: click here
Data structure: concept vs. implementation: click here

Unorderd Maps (hashing) --- overlap with CS171
- The Map abstract data type (operations) click here
- Implementing a Map ADT: with a linked list --- click here
- Hash table: an O(1) implementation of Unordered Map:
  - Introduction: click here
  - Hash function: click here
  - Handling collisions: click here
    - Separate chaining: click here
    - Open Addressing: click here
      - Delete procedure in Open Addressing: click here
  - Implementing a map using a hash table (open addresing): click here
  - Performance of hashing: click here
  - Maintaining good performance in Hashing: click here
- Making your data structure more flexible (with interfaces and parameterized types): click here
- My old teaching material on Goodrich's HashMap implementation (for your eyes only, I am not discussing this in class, the code is too complicated for an average student): click here
Ordered maps: (entries that have an ordering property)
- Introduction to ordered maps click here
- An application using ordered maps: click here
- An naive (O(n)) implementation of ordered maps using a sorted array: click here
- Skip lists: a faster (O(log(n)) (ordered) linked list data structure for ordered maps
  - The Skip List data structure: click here
  - Implementing a skip list: click here
  - A probabilistic analysis of skip lists: click here
Advanced implementation of Ordered Maps: Search Trees
- Review of binary search trees and its use to implement Ordered Maps: click here (A quick review of CS171 material)
- AVL trees: a guaranteed O(lg(n)) bin search tree
  - Introduction: click here
  - Height of an AVL tree with n nodes: click here
  - Data structure to implement a height-aware BST (prelude to AVL tree): click here
  - Inserting (+rebalancing) in an AVL tree: click here
  - Deleting (+rebalancing) in an AVL tree: click here
- Red-Black trees:
  - Introduction: click here
  - Inserting in a Red-Black tree: click here
  - Adjusting a Red-Black tree after an insert operation: click here
- Splay trees: a probabilistical O(lg(n)) bin search tree
  - Introduction: click here
  - Computing the average performance with the Amortization technique: click here
  - An average (amortization) performance analysis on Splay trees (O(lg(n)): click here
- 2,4-trees: a multi-way search tree
  - Multi-way search trees: click here
  - The 2,4-tree: click here
  - Inserting into the 2,4 tree:
    - Theory: click here
    - Implementation: click here
  - Deleting from the 2,4 tree:
    - Delete operation without underflow: click here
    - Handling overflow using entry transfer: click here
    - Handling overflow using node merge: click here
    - Cascading a delete operation: click here
    - Implementation: click here
  - Other multiway search trees: click here
  - Slide set 1 (old): click here
  - Slide set 2 (old): click here
Advanced Sorting (discussed in CS171 - skip - won't be on exams)
Text processing:
- Searching in texts: (pattern matching)
  - Brute force approach:
    - Finding pattern by brute force: click here
  - Prelude to string matching: string traversal technique click here
  - The Knuth-Morris-Pratt (KMP) method:
    - The KMP string matching algorithm: click here
    - Computing the KMP failure function: click here
    - Performance analysis of the KMP algorithm: click here
    - (Very good external notes on KMP: click here )
  - The Boyer-Moore method:
    - The Simplified Boyer-Moore algorithm: click here
    - The Boyer-Moore-Horspool algorithm: click here
    - References:
      - Original publication of the Boyer-Moore Algorithm: ``A Fast String Searching Algorithm'', R.S. Boyer and J. S. Moore., Communications of the ACM, 20(10), 1977, pp. 762-772. click here
      - Very good notes on Boyer-Moore: click here (Local PDF copy: click here)
      - ``Variation of Boyer-Moore Algorithm: A compararive analysis'': click here
      - Boyer-Moore Algorithm for small size alphabets: ``String Search over Small Alphabets'', Matyas Sustik and J. S. Moore., click here
- Indexing texts: ("retrieve" -- tries)
  - Introduction to indexing: click here
  - The standard trie: click here
  - The compressed trie: click here
  - The suffix trie: click here
  - Search engines: click here
- Compressing texts: (The Huffman (enthropy) encoding scheme)
  - Intro to data compression: click here
  - Runlength encoding -- fax machines: click here
  - Huffman encoding -- using a heap-like tree to find shortest codes: click here
    Huffman code lecture slides by Tom Przybylinski: click here (it has another example on constructing Huffman code)
- Text similarity testing:
  - The LCS Problem description which is used as an intro to dynamic programming: click here
Recursive problem solving techniques / Dynamic Programming
- The Longest Common Subsequence (LCS) --- i.e., the DNA and "Text sequence" alignment problem:
  - The Longest Common Subsequence problem: click here
  - Review: the recursive problem solving technique: click here
  - Recursive solution for LCS: click here
  - Dynamic programming of the LCS algorithm: click here
- A linear space algorithm for the LCS problem:
  - A linear space algorithm to find the length of the LCS: click here
  - A linear space algorithm to find the LCS string - the Herschberg's algorithm: click here
  - Reference: A linear space algorithm for computing maximal common subsequences by D. S. Hirschberg: click here
- Minimum edit distance (or smallest Levenshtein distance) between 2 strings: click here
- Making change for an amount of money: click here
- Knapsack problems
  - The knapsack problems and an introduction to constrained optimization: click here
  - The 0-1 Knapsack problem: click here
  - The Unbounded Knapsack problem: click here
Constrained linear optimization
- Real-number valued linear optimalization --- Simplex method:
  - Intro to Constrained Optimization: click here
  - The Simplex method:
    - Setting up the Simplex tableau: click here
    - Pivoting a Simplex tableau: click here
  - Handling "≥"-constraints - the 2-phase Simplex method: click here
  - Infeasible LP problems (LP problems with no solution): click here
  - Handling "="-constraints: click here
  - Complexity of LP and running time of the Simplex Method: click here
- Integer-valued linear optimalization --- Integer programming:
  - Intro to the Integer programming: click here
  - The Branch and Bound technique for Integer programming: click here

Graph algorithms (discussed in CS171 - skip)

Intro to Graphs: click here
Data Structures used to represent Graphs and their operations: click here
Graph traversal algorithms:
- Depth-first search: click here
- Breadth-first search: click here
Directed Graphs:
- Representing and traversing directed graphs: click here
- Strongly connected di-graphs: click here
- Transitive closure of di-graph (Floyd-Warshall Algorithm): click here
Directed Acyclic Graphs (DAG):
- Topological ordering of nodes in a DAG: click here
If you need a refresher or want to study these graph algorithms (e.g. Applying for the MS program at Emory), please click on the above links and study the material.

Shortest Path (Dijkstra's Algorithm): (discussed in CS171 - skip)

Weighted graphs and path length: click here
Finding shortest paths from one source -- Dijkstra's Algorithm: click here
Proof of correctness: click here
If you need a refresher or want to study these graph algorithms (e.g. Applying for the MS program at Emory), please click on the above links and study the material.

Minimum Spanning tree: (discussed in CS171 - skip)

Prim-Jarnik Algorithm: (not available) click here
Kruskal's Algorithm: (not available) click here
Lecture slides 1: click here
Lecture slides 2: click here
If you need a refresher or want to study these graph algorithms (e.g. Applying for the MS program at Emory), please click on the above lecture slides links and study the material.

Longest Path in a DAG (directed acyclic graph): (notes are not ready --- skip)
- Longest path: click here
Network flow:
- Introduction: click here
- Flow augmenting paths: click here
- The Max flow Algorithm: click here
- The Max flow/min cut Theorem : click here
- The Max flow problem as an Linear Program: click here
Matching in bi-partite graphs: The Marriage Problem
- Introduction to match making: click here
- Bi-partite matching algorithm: click here
The Assignment Problem
- Introduction: click here
- Prelude to the Hungarian Algorithm for the Assignment problem:: click here
- The Hungarian Algorithm for the Assignment problem: click here
The Transportation Problem
- Introduction: click here
- Prelude to the Hungarian Algorithm for the Transportation problem: click here
- The Hungarian Algorithm for the Transportation problem: click here
PERT and CPM: Critical path analysis
- Introduction: click here
Algorithmically Unsolvable and Hard-to-solve Problems
- Unsolvable problems: click here
- Hard-to-solve problems - brief intro into the class NP: click here
Introduction to Online Algorithms
- Introduction: click here
- An online algorithm for finding the majority element: click here
- An online algorithm for finding frequent elements: click here