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:

CSA603 and CSA607 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)