Purdue University - Department of Computer Science - CS 182: Foundations of Computer Science

CS 182: Foundations of Computer Science

Prerequisite:

CS 18000 (Problem Solving and Object-Oriented Programming)

Detailed Syllabus:

  1. Logic and Proofs: Propositional equivalences, predicates, quantifiers. Introduction to proofs.

  2. Sets, functions, relations, sequences and summations. Sets (finite, countable, uncountable, operations). Functions (properties, special classes). Relations (binary relations, composition, closure, equivalence relations). Sequences and sums. Uses and applications in computer science.

  3. Number representations. Number systems and representation of numbers. Floating point numbers and directed rounding. Arithmetic operations. Precision versus accuracy.

  4. Counting. Basics of Counting. Pigeon-hole principle. Permutations and combinations.

  5. Analysis of algorithm fundamentals. Growth and complexity of functions. Big-O notation and manipulations. Analyzing performance of algorithms.

  6. Graphs and trees. Basic properties of trees, directed, and undirected graphs. Traversal strategies for trees and graphs. Modeling problems using graphs and trees.

  7. Proof techniques. Proofs by contradiction, construction, and diagonalization. Include proofs related to properties of trees. Mathematical and structural induction.

  8. Recursion. Recursive definitions. Recurrence relations. Recursive programs: design and implementation. Pitfalls of recursion.

  9. Basic Number Theory, RSA Public Key Cryptosystems.

  10. Basic probability.

  11. Boolean Logic. Boolean logic and algebraic properties of Boolean functions. Logic circuits. Minimization of logic expressions.

  12. Finite state machines. Equivalence of regular languages and regular expressions. State minimization. Closure properties. Nondeterministic machines. Applications and uses in Computer Science.

  13. Pushdown automata. Languages and strings. Informal description of a PDA. Context-free languages. Introduction to parsing.

  14. Computability and undecidability. Limits of computation, Turing machines, Church-Turing thesis, Classes P and NP, Undecidability (Halting problem).

Last Updated: Apr 25, 2017 4:35 PM

Department of Computer Science, 305 N. University Street, West Lafayette, IN 47907

Phone:(765) 494-6010 • Fax: (765) 494-0739

Copyright © 2016 Purdue University | An equal access/equal opportunity university | Copyright Complaints

Trouble with this page? Disability-related accessibility issue? Please contact the College of Science.