Techniques for designing efficient algorithms; analysis of algorithms; lower bound arguments; and algorithms for sorting, selection, graphs, and string matching.

Upon completion, students will be able to:

• Express understanding of algorithm design techniques, including dynamic programming, divide and conquer, and greedy algorithms. Students will apply these paradigms to solve complex problems related to sorting, selection, graphs, and string matching.
• Analyze the asymptotic performance of algorithms, understanding their efficiency in terms of complexity. Students will evaluate worst-case running times using Big O notation and other asymptotic measures.
• Prove the validity of algorithms using inductive reasoning and invariants and will demonstrate that an algorithm produces the expected output for all possible inputs.
• Investigate graph theory, exploring algorithms for depth-first search, connected components, and shortest paths. They will model engineering problems using graphs and synthesize new graph algorithms.
• Express understanding of computational intractability and the theory of NP-completeness. They will explore lower bound arguments, recognizing limits on algorithmic efficiency for certain problems.

Grade Basis: L
Credit hours: 3.0
Lecture hours: 3.0