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