Cs 3304 Analysis Of Algorithms

CS 3304: Analysis of Algorithms

Course Description:

This course builds on knowledge of elementary algorithm analysis gained in CS 3303: Data Structures, and introduces more advanced algorithms. Implementation strategies for algorithms including Brute Force, Branch and Bound, Divide and Conquer, Greedy, Linear Programming and Dynamic programming as well as techniques to analyze and evaluate the complexity of algorithms are taught. Finally the concepts of NP-complete, hard problems, impossible problems, and the halting problem will be explored.

Required Textbook and Materials:

The main required textbooks for this course are listed below, and can be readily accessed using the provided links. There may be additional required/recommended readings, supplemental materials, or other resources and websites necessary for lessons; these will be provided for you in the course’s General Information and Forums area, and throughout the term via the weekly course Unit areas and the Learning Guides.

This course makes use of two main textbooks (below) and various other assigned readings. In some cases, the material presented in each textbook is redundant or repeated. However, both resources have been provided in this case because each textbook provides a unique perspective on the topic and those differences in perspective can be helpful in learning and understanding the material.

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://www.cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf

Software Requirements/Installation:

Analysis of algorithms is a course that is steeped in theory. The focus in this course is not on the development of programs but rather understanding basic computer science concepts and as such this course will not require a lot of development with a programming language. This course does, however, present the implementation of data structures and basic algorithms through the use of pseudo code and java code. Several examples of algorithms will be implemented using Java programming. Although you can use any java compiler and IDE to develop your code, a good option that does not require any local installation of software is the Cloud9 IDE (Integrated Development Environment) which can be accessed .

Learning Objectives and Outcomes:

By the end of this course students will be able to:

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
4. Asymptotically analyze algorithms
5. Describe and discuss theoretical computer science concepts such as hard problems, NP completeness, and the halting problem

Course Schedule and Topics:

This course will cover the following topics in eight learning sessions, with one Unit per week. The Final Exam will take place during Week/Unit 9.

Week 1: Unit 1 – Review of Data Structures and Algorithms

Week 2: Unit 2 – Divide and Conquer Algorithms

Week 3: Unit 3 – Graphs (Part 1)

Week 4: Unit 4 – Graphs (Part 2)

Week 5: Unit 5 – Dynamic Programming

Week 6: Unit 6 – Linear Programming and Reductions

Week 7: Unit 7 – Limits to Computation (Part 1)

Week 8: Unit 8 – Limits to Computation (Part 2)

Week 9: Unit 9 – Review and Final Exam