CS 395 Analysis of Algorithms

Total Credits: 3 cr

Course Coordinator: Robert Hiromoto

URL: http://www2.cs.uidaho.edu/~cs395/

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

Textbook: Anany Levitin, Introduction to the Design and Analysis of Algorithms or equivalent text.

References: None.

Course Goals: The student should gain the knowledge necessary to analyze a variety of algorithms and determine the best one for a given problem, or to design a new algorithm when necessary. The student should also be able to recognize when a problem is in the class of problems that cannot be solved efficiently.

Prerequisites by Topic:

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

Major Topics Covered in the Course: (duration) (CC2001 BOK reference)

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

Laboratory projects (specify number of weeks on each): There are no laboratory projects. Each student is expected to complete and submit a range of algorithm analysis homework assignments demonstrating his or her competence in the material studied.

Estimated Curriculum Category Content:

Area	Core	Advanced	Area	Core	Advanced
Algorithms		3 cr	Data Structures
Software Design			Prog. Languages
Computer Arch			Other

Oral and Written Communications: None.

Social and Ethical Issues: None.

Theoretical Content:

• Recurrences
• Asymptotic Notation
• Algorithm Design Techniques
• Probabilistic Algorithms
• Computational Complexity

Problem Analysis: Techniques for designing algorithms including:

• Divide-and-conquer
• Greedy
• Dynamic programming
• Backtracking
• Branch and Bound
• Probabilistic algorithms
• Approximation algorithms

Solution Design: When our algorithm analysis indicates that our algorithm or problems are infeasible, we implement a new, more efficient, algorithm (wrt. expected runtime). The emphasis is on responding to the awareness of inefficiency made possible thorough analysis, by using more advanced algorithms.

Course Outcomes: The following list documents the course outcomes and crossreferences them to the BSCS program outcomes. The letter at the beginning of each reference identifies the program outcome supported. The numbers sequentially identify the course outcome for this course. After completing CS 395 a student should know or be able to:

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