 Course Information

Time  3:004:30 TR
3:003:50 F  Location  VZN 297 (TR) and VZN 151 (F) 
 Instructor  Chuck Cusack  Email  cusack@hope.edu  Office  VWF 233  Phone  3957271  Office Hours  by appointment 

Textbooks   (IDAA) Introduction to the Design and Analysis of Algorithms, 3rd edition, Anany Levitin, Perason, 2012.
 (AIDMA) An Active Introduction to Discrete Mathematics and Algorithms, Version 2.5, Charles Cusack and David Santos, 2015.
(PDF)

 Description  An introduction to the design and analysis of algorithms along with some of the discrete mathematical structures that are fundamental to the field of Computer Science. This course builds on the data structures topics from CSCI235 by exploring efficient ways of using them to solve problems. Algorithm analysis topics include best, worst, and average case analysis of iterative and recursive algorithms; asymptotic notation; and solving recurrence relations. Algorithm design techniques include brute force, greedy, divideandconquer, transformandconquer, dynamic programming, and space/time tradeoff. Discrete structures topics include propositional logic, proof techniques (especially induction), sets, matrices, sequences and summations, and basic combinatorics. 
 Topics 

Foundational
Discrete Structures
 Propositional Logic, Equivalences, Truth Tables
 Sets
 Sequences and Summations
 Matrices
 Basic Counting
 Permutations/Combinations
 Binomial Coefficients and Identities, including the Binomial Theorem
 Pigeonhole Principle

Proof Techniques
 Direct, Contraposition, Contradiction
 Proof by Induction

Basic Algorithm Analysis
 Big0, Omega, and Theta Notation
 Basic Algorithm Analysis (best/average/worst, time/space, wallclock/CPU/operations)
 Complexity Classes
 Recursive Definitions/Recurrence Relations
 Solving Recurrence Relations
 Analyzing Recursive Algorithms/Master Theorem
 P/NP/NPComplete

Algorithm Design Techniques
 Brute Force
 Greedy
 Divideandconquer
 DecreaseandConquer
 Transform and Conquer
 Dynamic Programming
 Space/Time Tradeoff
 Backtracking
 Branchandbound




