CSCE 2100: Foundations of Computing - Spring 2021
Instructor: Paul Tarau, Professor - see my home page for contact info and office hours.
contact via Canvas
Midterm exam: Thursday, March 11, open net
Final exam: April 27, 10:30 a.m. - 12:30 p.m, cumulative, open net
Description and Objectives:
The course covers basic mathematical concepts and their computational equivalents, including propositional and predicate logic, induction, set theory, functions, and relations.
It introduces key concepts of discrete mathematics, probabilities, computability theory and complexity theory,
with emphasis on computational instantiations in terms of data structures and executable algorithms.
Intro to Python: sets, sequences, dictionaries, functions and generators
Propositional Logic, truth tables, satisfiability
Predicate logic, quantifiers, equivalent formulas
Peano's axioms for Natural Numbers
Intro to Computational Number Theory
Mathematical induction, big-Oh notation, recursion
Set theory, finite and infinite cardinals, ordinals, cartesian product, power set, bitstring representations
Functions: injections, surjections, and bijections
Relations: equivalence, partial order, total orders, similarities, distances
Elements of Probability Theory and Combinatorics
Trees, Graphs, matrix representations, algorithms
Transitive closure and matrix products
Intro to complexity classes, P, NP, Co-NP, PSPACE, EXP
Finite automata, regular expressions, context-free grammars
Decidable and recognizable languages, self-reference and undecidability, Universal Turing machines, Goedel's Theorem
Prerequisites: CSCE 1030
- 2 Individual Exams: 30%+30%
- Assignments (teams of up to 3): 40%
Recommended online resources:
Foundations of Computing Textbooks:
- Demonstrate a solid foundation in conceptual and formal models by describing loop structures in summation and/or product notation.
- Use abstraction in the design and implementation of algorithms.
- Design programming solutions to “simple” problems and implement those designs Python.
- Apply big-Oh notation to evaluate and compare algorithms and programs.
- Use combinatorics and conditional probability in solving real-world problems.
- Define the basic operations of sets, functions, relations, trees and graphs.
- Demonstrate an introductory knowledge of formal languages by using regular expressions, deterministic finite automata and non-deterministic finite automata to describe patterns in strings.