CMPS 3120 Algorithm Analysis (3 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.
Prerequisite: CMPS 2120 Discrete Structures and CMPS 2020 Programming
Concepts II with a grade of C- or better.
Big-oh notation, complexity, and data structures
3 semester units. 2 units lecture, 1 unit lab.
Required for Computer Science
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.
None.
Marc Thomas and Donna Meyers
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.
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.
| 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
|
| week 09 |
(6.2) Transform-and-conquer algorithms.
|
| week 10 |
(6.4) heapsort, (6.5) Horner's rule.
|
| week 11 |
(7.3) hash tables and big-oh(1) algorithms.
|
| week 12 |
(7.4) B-trees.
|
| week 13 |
(8.2) Distributed algorithms.
|
| week 14 |
(9.5) multi-threaded code.
|
| week 15 |
(10.2) P vs. NP. Contemporary issues surrounding
computational complexity.
|
A 93%
A- 90%
10 HW/Labs...10% B+ 87%
2 Midterms..60% B 83%
Final Exam...30% B- 80%
C+ 77%
C 70%
C- 65%
D+ 60%
D 50%
D- 40%
F below 40%
Fundamental Computing: 2 Credit Hours
Advanced Computing: 1 Credit Hour
Donna Meyers on June 1, 2014
Approved by CEE/CS Department on June 1, 2014.
Effective Fall 2014