- Instructor: Justin Smith
- Office: Korman 276
- Telephone: (215) 895-1847
- Semester: Winter 2014/2015
- Office Hours: Monday, Wednesday , 2-3

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

- Logic (Chapter 4 of the book)
- Propositional logic, truth tables
- First order logic
- Quantifiers and de Morgan’s laws
- Database queries

- Set theory (chapter 1)
- Operations on sets
- Power-sets
- Mathematical induction

- Sections 3.1-3.3:
- Sets
- 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, 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