CS317: Introduction to Design & Analysis of Algorithms

Course Catalog Description

Introduction to complexity analysis of algorithms; emphasis on searching, sorting, finding spanning trees and shortest paths in graphs. Design techniques such as divide & conquer, dynamic programming, and backtracking. Introduction to problem classification; i.e. $\mathsf{NP}$, intractable, and unsolvable.

Objectives

Upon completion of this course, the student will be able to:

• Understand asymptotic growth rate and analyze the time complexity of algorithms.
• Design algorithms to problems using basic algorithm design strategies, e.g., decrease/divide-and-conquer, greedy method, dynamic programming, etc.
• Verify and/or prove the correctness and complexity of algorithms using mathematical induction and/or deductive reasoning.
• Comprehend complexity classes such as $\mathsf{P}$ and $\mathsf{NP}$.
• Apply knowledge of computing and mathematics appropriate to the computer science discipline.
• 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.
• Understand the tradeoffs involved when developing algorithms that make decisions based on ethical practices.
• Apply computer science theory and software development fundamentals to produce computing-based solutions.
• Recognize the need for, and an ability to engage in, continuing professional development.

Course Topics

• Review important data structures, proof techniques, arithmetic series, as needed
• Algorithm analysis framework
• Asymptotic notation
• Mathematical analysis of non-recursive and recursive algorithms
• Brute force and exhaustive search, and other brute force algorithms
• Exhaustive search applied to traveling salesperson and knapsack problems
• Depth-first search, Breadth-first search
• Decrease-and-conquer algorithms, e.g., insertion sort, topological sort, binary search
• The master theorem
• Divide-and-conquer algorithms, e.g., mergesort and quicksort and closest pairs
• Review binary tree traversals
• Transform and conquer, such as presorting
• Space-Time tradeoffs, using hashing techniques
• Dynamic Programming, knapsack and memory functions
• Greedy Technique including Prim’s, Kruskal’s, and Djikstra’s algorithms
• Limitations of algorithm power, $\mathsf{NP}$, $\mathsf{NP}$-hard, $\mathsf{NP}$-complete
• Backtracking technique
• Branch and bound technique
• Professional continuing studies and professional ethics

Additional Optional Topics (if time permits)

• Additional sorts such as counting sort, shell sort, etc.
• Balancing search trees (at least one approach)
• B-trees
• Heaps and heapsort

Course Material

Introduction to the Design and Analysis of Algorithms by Anany Levitin (paid link)