Description
This course extends the study of algorithms introduced in CS-2851. 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
Materials
Required:- Introduction to Algorithms, 3rd Ed. Cormen, Lieserson, Rivest, and Stein, McGraw-Hill, 2010
- Notebook computer required
Program Outcomes Containing CS 3851
Course Learning Outcomes
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
Course Topics
- Exam (1 class)
- Introduction (1 class)
- Independent research presentation (5 classes)
- Algorithmic analysis (3 classes)
- Mathematic tools (2 classes)
- Sorting (4 classes)
- Order statistics (1 class)
- Greedy algorithms (2 classes)
- Graphing algorithms (4 classes)
- Dynamic programming (2 classes)
- NP complete (3 classes)
- Review (2 classes)
Prerequisites by topic
- Algorithmic analysis
- Java programming
- Set theory
- Recursion
- Methods of proof
- Graphs
- Trees
Laboratory topics
- Algorithm implementation (2 sessions)
- Algorithm analysis (3 sessions)
- Data compression algorithm (2 sessions)
- Algorithm design (2 sessions)
Course topics by day
ACCE content
| General Education |
Math & Science |
Business & Mgmt. |
Construction | Construction Science |
|---|
| 0 | 0 | 0 | 0 | 0 |
ABET/EAC content
| Engineering topics |
Design |
General education |
Math/Science | Other |
|---|
| 2 | No |
0 | 2 | 0 |
ABET/TAC content
| Communications |
Math & Science |
HU/SS |
Tech Content | Other |
|---|
| 0 | 0 | 0 | 0 | 0 |
Coordinator
Christopher Taylor, Associate Professor
Last review
Christopher Taylor, Associate Professor
on Sep 24, 2007
Last update
Christopher Taylor, Associate Professor
on Sep 24, 2007
