## CMPS 414 - Data and Algorithm Analysis

Data and Algorithm Analysis -  CMPS 414

Class Meeting: Tuesday 11:00 - 13:00

Catalog Description

A systematic study of algorithms and their complexity. Topics include techniques for designing efficient computer  algorithms, proving their correctness, analyzing their run-time complexity. Divide and Conquer algorithms, Greedy  algorithms, Dynamic Programming algorithms, Sorting and Searching algorithms (Binary search, Radix sort,  Bucket sort, Count Sort, Insertion sort, Merge sort, Quick sort and Heap sort), Order statistics, Graph algorithms  (Graph traversal, Minimum spanning trees and Shortest path problems).

Textbook

Introduction to Algorithms, Second Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest and Clifford Stein. The MIT Press © 2001

Course Objectives

The course aims to make the students be able to understand the fundamentals of algorithm analysis and design.  Upon the completion of this course, they will be able to analyze the asymptotic performance of algorithms,  demonstrate a familiarity with major algorithms and data structures, apply important algorithmic design  approaches and methods of analysis implement different algorithms and data structures and compare their runtimes.

Course Outcomes

1. Student will be able to understand and analyze the asymptotic run time of algorithms

2. Student will be able to understand and use the Master theorem and the substitution methods to derive closed form expressions for some runtime recurrence relations.

3. Student will be able to understand and apply the divide-and-Conquer design approach, Greedy algorithms and dynamic programming technique, and when to use each of them in solving problems

4. Student will be able to understand, analyze and prove the correctness of different comparisonbased sorting algorithms (such as insertion sort, heap sort, quick sort and merge sort)

5. Student will be able to understand, analyze and prove the correctness of different linear sorting algorithms (such as radix sort and count sort)

6. Student will be able to understand and analyze order statistics algorithms such as finding kth element and the mean of a list.

7. Student will be able to understand graph representations, basic graph algorithms and their analyses.

8. Students will be able to implement the studied algorithms with different tradeoffs in the design approach.