# CS 395

### CS 395: Analysis of Algorithms

**Catalog Description:** Measures of efficiency; standard methods and examples in the design and analysis of algorithms. Same as Math 395.

**Type:** Required for all CS majors.

**Total Credits:** 3

**Contact Hours:** 3 lecture hours per week.

**Course Coordinator**: Robert Hiromoto

**URL:** http://www.webpages.uidaho.edu/~markn/395/ (Spring 2014)

http://marvin.cs.uidaho.edu/Teaching/CS395/index.html (Spring 2013)

**Prereq:** Pass Math 175 with a C or better.

**Textbook:** Andy Levitin, *Introduction to the Design and Analysis of Algorithms*, 3rd Ed., Addison Wesley, 2011, or equivalent text.

**Textbook URL:** http://www.pearsonhighered.com/educator/product/Introduction-to-the-Design-and-Analysis-of-Algorithms/9780132316811.page

**Prerequisites by Topic**:

- Graphs, trees, linked lists, searching & sorting algorithms (CS 121)
- Counting, induction , Boolean algebra, series (Math 175 & Math 176)

## Major Topics Covered

- Models of computations: Recurrence relations (3 hours)
- Models of computations: Average case analysis (2 hours)
- Models of computations: Amortized case analysis (2 hours)
- Models of computations: Adaptive data structures (2 hours)
- Design of efficient algorithms: Recursion (4 hours)
- Design of efficient algorithms and data structures: Graphs (4 hours)
- Design of efficient algorithms and data structures: Trees (4 hours)
- Design of efficient algorithms and data structures: Divide-and-conquer (5 hours)
- Design of efficient algorithms and data structures: Backtracking algorithms (2 hours)
- Design of efficient algorithms and data structures: Dynamic programming (3 hours)
- Design of efficient algorithms and data structures: Branch and bound ( 2 hours)
- Design of efficient algorithms and data structures: Probabilistic algorithms ( 3 hours)
- Design of efficient algorithms and data structures: Approximation algorithms ( 2 hours)
- Design of efficient algorithms and data structures: NP-Complete problems (3 hours)

## Course Outcomes

**Note:** The primary Student Outcomes addressed in this course is (a), which is Emphasized and (j) is Reinforced.

- Understand the importance of the different algorithmic design techniques. (a)
- Determine the time and space complexity (order of growth) to expect from algorithms designed and implemented in practical computational applications. (a)
- Design, analyze, and determine when to use algorithmic approaches such as: brute-force, divide-and-conquer, graph and tree techniques, dynamic programming, backtracking, probabilistic, approximation, branch and bound, numerical and sorting techniques. (a)
- Prove mathematically the correctness of algorithms such as greatest common divisor and matrix multiplication. (a)
- Design, evaluate and implement algorithms presented in this course on computer systems. (c)
- Logically explain the algorithmic steps required in a program implementation. (f)
- Explain the steps used and results obtained when developing new or more optimal algorithms. (f)