Algorithms
|
This course extends the study of algorithms introduced in CS-2852. Topics covered include searching, sorting, selection, graph structures, traversal algorithms and P/NP complete problems. Applications such as data compression, optimization problems and database indexing are also discussed. Laboratory activities include the implementation and comparison of problem-specific algorithms.
Prerequisites: CS-2852 or CS-2851,and MA-230 .
Course structure: 3-2-4 (class hours/week, lab hours, credits).
|
Required Materials:
- Introduction to Algorithms, 3rd Ed. Cormen, Lieserson, Rivest, and Stein, McGraw-Hill, 2010
- Notebook computer required
|
Upon successful completion of this course, the student will:
- apply asymptotic time complexity analysis to choose among competing algorithms
- construct and solve recurrence equations describing the asymptotic time complexity of a given algorithm
- implement sorting algorithms such as heapsort and quicksort
- describe how graph and tree structures are implemented
- describe similarities and difference between breadth-first and depth-first search techniques
- compare and contrast at least two minimum spanning tree algorithms
- identify the use of dynamic programming techniques in algorithmic design
- describe the implications of demonstrating that a particular algorithm is NP complete
- list at least three engineering applications of algorithmic design and analysis
|
|