# 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)
• 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)