CS 350 Algorithms and Complexity

Credit Hours: 4
Course Coordinator: Bryant York
Course Description: Techniques for the design and analysis of algorithms. Case studies of existing algorithms (sorting, searching, graph algorithms, dynamic programming, matrix multiplication fast Fourier transformation). NP-completeness. Prerequisite: CS 311.
Prerequisites: Computational structures which covers finite automata, context-free languages, pushdown automata, Turing machines, Chomsky language hierarchy and Church's thesis.
Goals: To develop a group of useful algorithms which can be used to solve common problems. The development of tools and principles for analyzing the time and space used by these algorithms. The course will include case studies of existing algorithms (sorting, searching, graph algorithms, greedy programming, string alignment and approximation algorithms). An introduction to NP-complete sets and approximation algorithms for some languages in NP is given.

Upon the successful completion of this course students will be able to:

  1. Analyze the running time and space complexity of algorithms.
  2. Use the big Oh notation. (e.g., O(n lg n).)
  3. Describe how to prove the correctness of an algorithm.
  4. Use the mathematical techniques required to prove the time complexity of a program/algorithm. (e.g., limits and sums of series.)
  5. Perform inductive proofs.
  6. Prove and apply the Master Theorem.
  7. Describe the notions of P, NP, NPC, and NP-hard.
  8. Compare the rates of growth of functions.
  9. Apply algorithmic complexity principles in the design of programs.
  10. Design divide and conquer and dynamic programming algorithms.
Textbooks: Introduction to Algorithms (second addition), by T. Cormen, C. Leiserson and R. Rivest.
References: None.
Major Topics: -Optimal, worst case and average case complexity techniques, asymptotic notation. Recurrence equations and recursive algorithms.
-Study the design and analysis of a wide variety of algorithms: sorting, searching, graphs, dynamic programming, greedy algorithms, string alignment, etc.
-Classification of problems into the classes P and NP. NP-completeness, approximation algorithms for problems in NP.
Laboratory Exercises: Students are given assignments where they are asked to implement algorithms and compare the running time of their implementation to that predicted by formal analysis. In addition, assignments consisting of problems which require written solutions are given. Problems solutions usually require formal proofs.

CAC Category Credits Core Advanced
Data Structures 0.5
Algorithms 0.5 2.5
Software Design 0.5
Computer Architecture
Programming Languages

Oral and Written Communications: None.
Social and Ethical Issues: None.
Theoretical Content: About 10% of class time is spent on an introduction to complexity theory. Topics covered include: the classes P and NP; NP-completeness, many-one reducibilities between classes and approximation algorithms for some NP related problems.

About 20% of class time is spent on introduction to algorithms analysis including asymptotic notation and recurrence relations.

About 30% of class time is spent on divide and conquer algorithms including sorting, searching and graph algorithms.

About 40% of class time is spent on dynamic programming and greedy algorithms including search tree construction, and string alignment.

Problem Analysis: All Students learn methods that are used to predict the resources needed by an algorithm. Specific attention is paid to worst case running time. Average-case running time is also considered.
Solution Design: Techniques for the designing and analysis of algorithms are presented. Students will gain a sophistication in the use of data structures and choice of algorithms which will enable them to better implement solutions to problems in many areas of computer science.