CS3304 Analysis of Algorithms

Syllabus

1. Review of Data Structures and Algorithms
2. Divide and Conquer Algorithms
3. Graphs (Part 1)
4. Graphs (Part 2)
5. Dynamic Programming
6. Linear Programming and Reductions
7. Limits to Computation (Part 1)
8. Limits to Computation (Part 2)

Resources

Task	Number	Percentage of Final Grade	Per Item
Discussions	8	20%	2.5%
Assignments	4	20%	5%
Journals	8	10%	1.25%
Graded Quiz	2	20%	10%
Final Exam	1	30%	30%

Objectives

1. Articulate the characteristics and design of fundamental patterns of algorithms
2. Implement algorithms using the Java programming language
3. Understand the characteristics of the different algorithm designs including:
   • Brute Force
   • Backtracking
   • Branch and Bound
   • Greedy
   • Divide and Conquer
   • Linear Programming
   • Dynamic Programming
4. Asymptotically analyze algorithms
5. Describe and discuss theoretical computer science concepts such as hard problems, NP completeness, and the halting problem.

Textbooks

• Schaffer, C.A. (2011). A Practical Introduction to Data Structures and Algorithms Analysis (3.1 ed.). Blacksburg, VA: Virginia Tech University, Department of Computer Science. Available at http://people.cs.vt.edu/~shaffer/Book/C++3e20100119.pdf
• Dasgupta, S., Papadimitriou, C.H., & Vazirani, U.V. (2006). Algorithms. Berkeley, CA: University of California Berkeley, Computer Science Division. Available at http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf