CMPS 312 Algorithm Analysis and Design
Catalog Description
CMPS 312 Algorithm Analysis and Design (5 units)
Algorithm analysis, asymptotic notation, hashing, hash tables, scatter tables, and AVL and Btrees, brute-force and greedy algorithms, divide-and-conquer algorithms, dynamic programming, randomized algorithms, graphs and graph algorithms, and distributed algorithms. Each week lecture meets for 200 minutes and lab meets for 150 minutes. Prerequisite: CMPS 295/300 and CMPS 223.
Prerequisites by Topic
Discrete structures and data structures
Units and Contact Hours
5 quarter units. 4 units lecture (200 minutes), 1 unit lab (150 minutes).
Required for Computer Science
Required Textbook
Introduction to the Design and Analysis of Algorithms, 3rd edition, Anany Levitin, Pearson, 2012, ISBN-10: 0-13-231681-1; ISBN-13: 978-0-13-231681-1.
Recommended Textbook and Other Supplemental Materials
Marc Thomas and Donna Meyers
Student Learning Outcomes
This course covers the following ACM/IEEE Body of Knowledge student learning outcomes:

(CC-AL1) Basic algorithmic analysis.
(CC-AL2) Algorithmic strategies.
(CC-AL3) Fundamental computing algorithms.
(CC-AL4) An introduction to distributed algorithms.
(CE-ALG5) Algorithmic complexity.

ABET Outcome Coverage
This course maps to the following performance indicators for Computer Science (CAC/ABET):

(CAC PIa1): 3a. An ability to apply knowledge of computing and mathematics appropriate to the discipline:
PIa1. Apply and perform the correct mathematical analysis. Laboratory/homework assignments and questions on the midterms and final require direct applications of the mathematical theory of algorithms pertinent to computer science.
(CAC PIb1): 3b. An ability to analyze a problem, and identify and define the computing requirements and specifications appropriate to its solution:
PIb1. Identify key components and algorithms necessary for a solution. Implementation on actual hardware and the ability to analyze performance (e.g. the roles of caches, virtual memory, use of multi-threaded code) will be required for successful completion of laboratory/homework assignements and will be tested on the exams.
(CAC PIj1): 3j. An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices:
PIj1. Understand performance and cost as these relate to software/firmware-based and hardware-based implementations. Implementation and performance analysis of different algorithms (e.g. direct, recursive, etc.) which solve the same problem will be required for successful completion of laboratory and homework assignments and will be tested on the exams.

Lecture Topics and Rough Schedule
week 01 (1.1-1.4 and Appendix A) introduction, basic issues with examples, useful formulas, important problem types, and review of data structures.
week 02 (2.1-2.3) input size, order of growth and big-O notation, analysis and examples of non-recursive algorithms.
week 03 (2.4, Appendix B, and 3.1-3.2) analysis and examples of recursive algorithms, searching, sorting, and string matching.
week 04 (3.3-3.4) closest-pair, convex hull problems, and exhaustive search (traveling salesman, knapsack).
week 05 (4.1) insertion sort, (4.2) topological sorting, and (4.3) combinatorial considerations.
week 06 (4.4) binary search, (4.5) Lomuto partitioning, (5.1) mergesort, and (5.2) quicksort.
week 07 (5.3-5.4) binary tree traversals. (6.2) Gaussian elimination.
week 08 (6.3) AVL and 2-3 search trees and (6.4) heapsort.
week 09 (6.5) Horner's rule, (7.3) hashing, and (7.4) B-trees.
week 10 Additional topics (e.g. P and NP, multi-threaded code, and distributed algorithms).

Grading Policy
                                    A   93%
                                    A-  90%
    10 HW/Labs...10%                B+  87%
    10 Quizzes...60%                B   83%
    Final Exam...30%                B-  80%
                                    C+  77%
                                    C   70%
                                    C-  65%
                                    D+  60%
                                    D   50%
                                    D-  40%
                                    F  below 40% 
Estimated ABET Category Content
Math and Basic Sciences: 1 Credit Hour
Fundamental Computing: 2 Credit Hours
Advanced Computing 1 Credit Hour
Prepared By
Donna Meyers on June 1, 2014
Approved by CEE/CS Department on June 1, 2014.
Effective Fall 2014