CS 395

From CS Wiki
Jump to: navigation, search

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, 2nd Ed., Addison Wesley, 2006, 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

  1. Models of computations: Recurrence relations (3 hours)
  2. Models of computations: Average case analysis (2 hours)
  3. Models of computations: Amortized case analysis (2 hours)
  4. Models of computations: Adaptive data structures (2 hours)
  5. Design of efficient algorithms: Recursion (4 hours)
  6. Design of efficient algorithms and data structures: Graphs (4 hours)
  7. Design of efficient algorithms and data structures: Trees (4 hours)
  8. Design of efficient algorithms and data structures: Divide-and-conquer (5 hours)
  9. Design of efficient algorithms and data structures: Backtracking algorithms (2 hours)
  10. Design of efficient algorithms and data structures: Dynamic programming (3 hours)
  11. Design of efficient algorithms and data structures: Branch and bound ( 2 hours)
  12. Design of efficient algorithms and data structures: Probabilistic algorithms ( 3 hours)
  13. Design of efficient algorithms and data structures: Approximation algorithms ( 2 hours)
  14. Design of efficient algorithms and data structures: NP-Complete problems (3 hours)

Course Outcomes

  1. Understand the importance of the different algorithmic design techniques. (a)
  2. Determine the time and space complexity (order of growth) to expect from algorithms designed and implemented in practical computational applications. (a)
  3. 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)
  4. Prove mathematically the correctness of algorithms such as greatest common divisor and matrix multiplication. (a)
  5. Design, evaluate and implement algorithms presented in this course on computer systems. (c)
  6. Logically explain the algorithmic steps required in a program implementation. (f)
  7. Explain the steps used and results obtained when developing new or more optimal algorithms. (f)