CSCI 255 Fall 2013
Introduction to Algorithms and Discrete Structures
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Homework

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

Course Information


Time 1:30-2:50pm Tuesday/Thursday
2:00-2:50pm Friday
LocationGraves 203

Instructor Chuck Cusack
E-mail cusack@hope.edu
OfficeVWF 233
Phone 395-7271
Office Hours       2-3pm 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, 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
  1. Foundational Discrete Structures
    1. Propositional Logic, Equivalences, Truth Tables
    2. Sets
    3. Sequences and Summations
    4. Matrices
    5. Basic Counting
    6. Permutations/Combinations
    7. Binomial Coefficients and Identities, including the Binomial Theorem
    8. Pigeonhole Principle
  2. Proof Techniques
    1. Direct, Contraposition, Contradiction
    2. Proof by Induction
  3. Basic Algorithm Analysis
    1. Big-0, Omega, and Theta Notation
    2. Basic Algorithm Analysis (best/average/worst, time/space, wall-clock/CPU/operations)
    3. Complexity Classes
    4. Recursive Definitions/Recurrence Relations
    5. Solving Recurrence Relations
    6. Analyzing Recursive Algorithms/Master Theorem
    7. P/NP/NP-Complete
  4. Algorithm Design Techniques
    1. Brute Force
    2. Greedy
    3. Divide-and-conquer
    4. Decrease-and-Conquer
    5. Transform and Conquer
    6. Dynamic Programming
    7. Space/Time Tradeoff
    8. Backtracking
    9. Branch-and-bound