Credits and Contact Hours

3 credits, 43 hours

Course Instructor Name

Dr. Ameer Mohammed, Prof. Tassos Dimitriou

Textbook

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 3rd Edition.

Catalog Description

Overview of algorithms and complexity. Basic algorithmic analysis. Models of computation. Classes of techniques for designing efficient algorithms including recursion, divide-and-conquer, randomization, greedy algorithms, and dynamic programming. Fundamental computing algorithms: sorting, searching, and graph algorithms. The classes of P, NP, and NP-complete problems.

Pre-requisite CpE-207

Specific Goals for the Course

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

Use different computational models (e.g., divide-and-conquer), order notation () and various complexity measures (e.g., running time, disk space) to analyze the complexity/performance of different algorithms. (Student outcomes: 1, 2)

Understand the difference between the lower and upper bounds of various problems and their importance in deciding the optimality of an algorithm. (Student outcomes: 1, 2)

Use various techniques for efficient algorithm design (divide-and-conquer, greedy, and dynamic algorithms) and be able to apply them while designing algorithms. (Student outcomes: 1, 2)

Differentiate between various algorithms for sorting (e.g., insertion, merge, quick-sort, and heap sort), searching (e.g., linear and binary search), and selection (e.g., min, max) and when to use them. (Student outcomes: 1, 2)

Augment various data structures (trees and arrays) to support specific applications. (Student outcomes: 1, 2)

Know various advanced design and analysis techniques such as greedy algorithms, dynamic programming. (Student outcomes: 2)

Able to understand the techniques used for designing fundamental graph (e.g., red-black tree) theory algorithms (e.g., breath-first and depth-first algorithms) and apply them to solve other related problems (e.g., single source shortest path as in Dijkstra's and Bellman-Ford algorithm, multiple source shortest path as in Floyd's Algorithm, minimum spanning trees as in Prim's and Kruskal's algorithms). (Student outcomes: 1, 2)

Know the concepts of tractable and intractable problems and the classes P, NP and NP-complete problems. (Student outcomes: 2)

Topics to Be Covered

Introduction to algorithms. The notion of complexity and order notation.

Divide and conquer and recurrences.

Sorting algorithms and lower bound techniques.

Order statistics

Algorithm design techniques (Dynamic programming, Greedy algorithms, Network flows)

Graph theoretic algorithms (Graph exploration, Minimum Spanning tree, Shortest paths).

Maximum Flow and Matchings.

Theory of NP-Completeness