Contents
Catalog Links
Share

CS3150 Design and Analysis of Algorithms

This course focuses on the design and analysis of efficient algorithms. Techniques for analyzing algorithms in order to measure their efficiency are presented. Control structure abstractions, such as divide and conquer, greedy, dynamic programming, backtrack (branch and bound), and local search methods are studied. The theory of NP-completeness is presented along with current approaches to NP-hard problems.

Prerequisite

CS3021 and MA2025

Lecture Hours

5

Lab Hours

0

Course Learning Outcomes

Upon completion of this course, students will be able to:

  • Formally prove asymptotic lower and upper bounds
  • Calculate the time and space resources utilized by a given non-recursive algorithm
  • Apply recursion trees and substitution method  to estimate and prove  time and space resources utilized by a recursive program.
  • Apply divide and conquer programming techniques to algorithm development.
  • Apply pivoting to sorting (quicksort) and to the randomized and deterministic)  k-median problem.
  • Apply Priority-queues as a live data-structure with O(log n) update cost.
  • Apply Red-Black trees and O(log(n)) live binary search tree.
  • Apply DFS and BFS to graph traversal problems. 
  • Apply topological sort to the problem of finding strongly connected components in directed graphs.
  • Prove the optimal substructure property holds for problems that can be solved using dynamic programming.
  • Apply  dynamic programming techniques to problems that enjoy the optimal substructure property.
  • Discover cycles in directed and undirected graphs.
  • Apply dynamic programming methods to path finding problems (Dijkstra and A* algorithms)
  • Apply Minimum Spanning tree Algorithms.
  • Prove properties of tree, graphs, and minimum spanning trees.
  • Perform reductions from well know NP-complete problems to another such problems, such as SAT to CLIQUE, or HAM to TSP.
  • Prove an NP problem in in class NP.
  • Prove an NP-hard problem is NP-hard using reductions to well known NP-hard problems.
  • Demonstrate understanding of the Pro's and Con's of using NP-complete problems for security vs the discrete-log problem.
  • Demonstrate understanding of Zero-Knowledge proof systems and their relationship to class NP.