Theoretical Foundations of Computer Science. Prerequisite:
CSc 2010 with grade C or higher. This course covers the basic
theoretical foundations required to study various sub-disciplines
in computer science. Topics include: propositional and predicate logic
with applications to logic programming, database querying, and
program verification; induction and its application in proving
correctness and termination of programs; recurrence relations,
combinatorics, and graph theory with applications to analysis of
algorithms; sets, relations, and functions and their applications
in databases, functional programming, and automata.
3.000 Credit Hours
Textbook
- Mathematical Structures for Computer Science (Sixth Edition),
by Judith L. Gersting, W.H. Freeman and Company, 2007.
- Additional may be provided in class.
Grading Policy: The grading will be based on the following components:
- Two exams worth 15% each
- Several in-class quizzes worth 20%
- Homework assignments worth 20%
- Final exam worth 30%.
Two different averages will be computed for each student:
one including the homework assignments and the second not including the
homework assignments. The final course average will be the smaller of the
two averages. This implies that the homework assignments can only hurt
your final grade.
The final letter grade will normally be determined based on the following
criteria unless the class averages dictate a curve to be used:
| A |
90 and above |
| B |
80 thru 89 |
| C |
65 thru 79 |
| D |
50 thru 64 |
| F |
less than 50 |
Detailed Course Syllabus
- Chapter 1: Formal Logic
- Propositional Logic
- Predicate Logic
- Application: Logic Programming (Prolog), Proof of Program Correctness
- Chapter 2: Proofs, Recursion and Analysis of Algorithms
- Proof Techniques
- Mathematical Induction
- Recursive definitions, Recurrence relations
- Analysis of Algorithms
- Chapter 3: Sets, Combinatorics, Probability, Number Theory
- Sets, Counting, Principle of inclusion and exclusion (pigeonhole)
- Permutations and Combinations
- Probability, Binomial Theorem
- Chapter 4: Relations, Functions, Matrices
- Relations, Topological Sort
- Relations and Databases
- Functions, mighty mod function
- Matrices
- Chapter 5,6: Graphs, Trees, Graph Algorithms
- Representations of graphs and trees, Decision trees.
- Huffman Codes
- Algorithms: shortest paths, reachability, traversals, minimum spanning
trees.
- Chapter 7: Boolean Algebra and Computer Logic
- Boolean algebraic structures
- Combinatorial circuits
- Minimization
- Chapter 8: Computation and Languages
- Finite state machines
- Turing machines
- Formal grammars
Last date to withdraw: 15 October, 2007 (Monday).
Academic Honesty Policy:
All work submitted for grading must be student's own work.
Plagiarism will result in a score of zero on the test
or assignment, or dismissal from the course.
NOTE:
This syllabus represents a general plan for the course and
deviations from this plan may be necessary during the duration
of the course.
Raj Sunderraman
08/20/2007