- Instructor: Justin Smith
- Office: Korman 276
- Telephone: (215) 895-1847
- Semester: Fall 2015/2016
- Office Hours: Monday, Wednesday , 1-2

- Text: Online Material
- Authors: Andrew Hicks and Justin Smith

- Logic
- Propositional logic, truth tables
- First order logic
- Quantifiers and de Morgan’s laws
- Database queries

- Mathematical Induction
- Ground step and induction step
- Examples of proof by induction

- Set Theory
- Notes on set theory
- Operations on sets
- The power set
- The Russell Paradox
- Counting
- Principal of Inclusion and Exclusion; Pigeonhole Principle

- Section 3.4:
- Permutations and Combinations

- Section 3.4-3.5: Combinations, Binomial Theorem
- Sections 4.1-4.3:
- Relations
- Topological Sorting
- Relations and Databases

- Section 4.4:
- Functions

- Sections 5.1-5.2:
- Representations of Graphs
- Representations of Trees

- Sections 5.3-5.4:
- Decision trees
- Huffman codes

- Sections 6.1-6.3:
- Directed graphs and binary relations
- Boolean adjacency matrices and reachability
- Warshall's algorithm
- Euler Path and Hamiltonian Circuit
- Shortest path and minimal spanning tree

- Section 8.2:
- Finite state machines

- Section 8.4
- Formal languages
- Review

- Students will learn basic logic, combinatorics and finite automata.
- Students will learn applications to computer science.

- Grades will be based on graded homework, three one-hour exams (given at the ends of weeks 3, 6, and 9), and the final.
- The final will count twice and the lowest of the resulting five grades will be dropped.
- Homeworks and quizzes will count as one tenth of an exam.

- Academic integrity, Plagiarism and Cheating Policy
- Academic Core Values
- Students with disabilities
- Course drop policy

Justin R. Smith