Exam Syllabus

Related Courses

  • CS 310 Data Structures
  • CS 560 Algorithms and Their Analysis
  • CS 660 Combinatorial Algorithms

References

  • A. Aho, J. Hopcroft, & J. Ullman, The Design and Analysis of Computer Algorithms, Addison Wesley, 1974
  • Baase & Gelder, Computer Algorithms: Introduction to Design and Analysis, 3nd ed., Addison Wesley, 2000
  • Gilles Brassard & Paul Bratley, Algorithmics, Prentice Hall, 1988
  • T. Cormen, C. Leiserson, & R. Rivest, Algorithms, MIT Press, 1990
  • Donald Knuth, The Art of Computer Programming (3 vols., various editions, 1973-81), Addison Wesley
  • Robert Kruse, Data Structures and Program Design , Prentice Hall, 1984
  • Udi Manber, Introduction to Algorithms, Addison Wesley, 1989
  • B. Moret & H. Shapiro, Algorithms from P to NP vol. 1: Design and Efficiency, Benjamin/Cummings, 1991
  • E. Reingold & W. Hansen, Data Structures in Pascal
  • Robert Sedgewick, Algorithms, 2nd ed.,Addison Wesley, 1988
  • Harry Smith, Data Structures: Form and Function
  • Jeffrey Smith, Design and Analysis of Algorithms, PWS-Kent, 1989

Topics

Implicit in a topic is the standard analysis of the relevant algorithms. We have omitted the traditional storage management material.

1. General concepts

  • Abstract data structure as an organization of data with specified properties
  • and operations
  • Time and space analysis of algorithms
  • Big oh and theta notations
  • Average, best and worst case analysis
  • Simple recurrence relations and use in algorithm analysis

2. Linear data structures

  • Arrays,lists, stacks, queues
  • Array and linked structure implementations of lists, stacks, queues
  • Array of nodes and dynamic pointer implementations of linked structures

3. Trees

  • General and binary trees
  • Representations and traversals
  • General trees as binary trees
  • Binary search trees
  • Applications
  • The concept of balancing and its advantages
  • Some balanced tree mechanism, eg. AVL trees, 2-3 trees, red-black trees, self-adjusting trees, ….

4. Algorithm design techniques

  • Greedy methods
  • Priority queue search
  • Exhaustive search
  • Divide and conquer
  • Dynamic programming
  • Recursion
  • Influence of data structure on algorithm performance

5. Hashing

  • Hash functions
  • Collision resolution
  • Expected behavior

6. Graphs and digraphs

  • Representions
  • Breadth and depth first searches
  • Connectivity algorithms
  • Shortest path
  • Minimal spanning tree
  • The union find problem
  • Hamiltonian path and travelling salesperson problems
  • Network flow
  • Matchings

7. Sorting

  • Elementary sorts: selection,insertion, bubblesort. Quicksort, mergesort, heapsort
  • Bucket sorting
  • External sorting
  • Worst case and average behavior
  • Lower bound for sorting using comparisons
  • Order statistics

8. NP vs. P

  • The spaces P and NP
  • Polynomial reduction
  • NP complete problems
  • Boolean satisfiability and Cook’s theorem
  • Binpacking, knapsack, Hamiltonian path, TSP, independent set, max clique, integer
  • linear programming, graph coloring
  • Approximation algorithms