 Course Information

Time  1:302:50pm Tuesday/Thursday 2:002:50pm Friday 
Location  Graves 203 

Instructor 
Chuck Cusack 
Email  cusack@hope.edu 
Office  VWF 233 
Phone  3957271 
Office Hours  23pm MW or by appointment 

Textbook 
The following two textbooks will be used:
 The Algorithm Design Manual, Second Edition (ADM), Steven Skiena, Springer, 2010.
 Introduction to Discrete Mathematics and Algorithms (IDMA), Charles Cusack and David Santos, 2013.
(The bookstore has copies. You need a hard copy for use during class, but it is
also available in PDF here)
Note: Whenever the resources column on the schedule has an entry for ADM or IDMA,
you are expected to read the given sections before class.


Important Links 


Resources 
 Answers in the back of your book
An Introduction to Discrete Mathematics and Algorithms has Exercise sections that
contain problems with solutions given in the next section.
 Me
See me during office hourse, before or after class, or make an appointment at another time.
 The Computer Science Help Center
Check the signs in the lab and classroom for hours. The Help Center Assistante should be able to help
you with the discrete mathematics topics. Depending on who is there, they may be able to help with
some of the algorithms material.


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



