| Course Information
|
Time | 3:00-4:30 TR
3:00-3:50 F | Location | VZN 297 (TR) and VZN 151 (F) |
| Instructor | Chuck Cusack | Email | cusack@hope.edu | Office | VWF 233 | Phone | 395-7271 | 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, divide-and-conquer, transform-and-conquer, 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
- Big-0, Omega, and Theta Notation
- Basic Algorithm Analysis (best/average/worst, time/space, wall-clock/CPU/operations)
- Complexity Classes
- Recursive Definitions/Recurrence Relations
- Solving Recurrence Relations
- Analyzing Recursive Algorithms/Master Theorem
- P/NP/NP-Complete
-
Algorithm Design Techniques
- Brute Force
- Greedy
- Divide-and-conquer
- Decrease-and-Conquer
- Transform and Conquer
- Dynamic Programming
- Space/Time Tradeoff
- Backtracking
- Branch-and-bound
|
|
|
|
|