CSE 606 Data Structures and Algorithms (4)

Course Description:

Abstract data types and their implementation as data structures using object-oriented programming. Lists, stacks, queues, tables, trees, and graphs. Recursion, sorting, searching, and algorithm complexity. Three credit hours lecture, one credit hour lab. 

Prerequisite:

CSE 603 and CSE 607 or permission of instructor 

Course Objectives:

  • Apply appropriate data structures and abstract data types (ADTs) such as bags, lists, stacks, queues, trees, tables, and graphs in problem solving.
  • Apply object-oriented principles of polymorphism, inheritance, and generic programming when implementing ADTs for data structures.
  • Create alternative representations of ADTs either from implementation or the standard libraries.
  • Apply recursion as a problem solving technique.
  • Identify appropriate ADTs and data structures for various sorting and searching algorithms.
  • Analyze time and space requirements of common sorting and searching algorithms.

Required topics (approximate weeks allocated):

  • Trees (2)
    • Representations
    • Traversal algorithms (iterative and recursive):BFS and DFS
    • Binary search trees
    • Heaps
    • B-trees
  • Graphs (1)
    • Implementations: adjacency lists and adjacency matrices
    • Traversals: DFS and BFS
  • Tables (1)
    • Internal vs. External access
    • Hashing
    • Collision resolution
  • Counting and proofs (0.5)
    • Inclusion-exclusion principle
    • Pigeonhole principle
    • Binomial theorem
  • Mathematical foundations of algorithms (2)
    • Asymptotic complexity
    • Recurrence relations
    • Analysis of loops
    • Analysis of recursion
    • Solving recurrence relations
  • Sorting/searching and algorithm complexity (1)
    • space and time complexity of basic sorting/searching algorithms
  • Program Correctness (0.5)
  • Some selection of algorithms from the following categories. (4.5 weeks)
    • Sorting and order statistics (examples follow)
      • HeapSort (0.5)
      • Randomized algorithms and Quicksort running-time bounds (1)
      • Sorting in linear time (0.5)
      • Median and order statistics (0.5)
    • Dynamic programming (examples follow) (1)
      • Matrix-chain multiplication
      • Longest common subsequences
    • Greedy algorithms (examples follow) (1)
      • activity selection
      • Huffman coding
      • Fractional Knapsack
    • Amortized analysis (1)
    • Graph algorithms (examples follow)
      • Topological search (0.5)
      • Minimum spanning trees: Kruskal and Prim algorithms (0.5)
      • Dijkstra's shortest path algorithm (0.5)
      • Maximum flow: Ford-Fulkerson algorithm (1)
    • Polynomials and FFT (1)
    • Number-theoretic algorithms (0.5)
    • String matching (examples follow) (1)
      • Rabin-Karp
      • Knuth-Morris-Pratt
    • Computational Geometry (1)
  • NP-completeness (2)
    • Polynomial time
    • Polynomial-time verification
    • NP-completeness and reducibility
    • NP-completeness proofs
    • NP-completeness problems
  • Exams/Review (.5)