UNT | University of North Texas

Search form

CSCE 2110: Computing Foundations II

Course Number: 
CSCE 2110
Course Name: 
Computing Foundations II

Continuation of Computing Foundations I. Further introduces students to both data structures and formalisms used in computer science, such as asymptotic behavior of algorithms. Data structures and formalisms used to both describe and evaluate those data structures simultaneously. By the end of the two-semester sequence of which this course is the second part, each student will have a solid foundation in conceptual and formal models, efficiency, and levels of abstraction as used in the field of computer science.

Start Date: 
Monday, May 3, 2010
Last Review Date: 
Thursday, April 2, 2015
Prerequisite (should have grade of C or better): 
Credit Hours (Including Labs): 
UNT Topics: 
  1.  The Set Data Model
    1. Set
    2. Empty set
    3. Atoms
    4. Multiset
    5. Set former expression
    6. Equality of sets
    7. Infinite sets
    8. Universal set
    9. Russell’s paradox
    10. Set operations
    11. Union
    12. Intersection
    13. Difference
    14. Equality
    15. Venn diagrams
    16. Properties of set union, intersection, and difference
    17. Subsets
    18. List implementation of sets
    19. Characteristic vector implementation of sets
    20. Array implementation of sets
    21. Hashing
    22. Hash table
    23. Hash function
    24. Relations and functions
    25. Tuple
    26. Cartesian product
    27. Binary relations
    28. Functions as data
    29. Implementing binary relations
    30. Properties of binary relations
    31. Infinite sets
  2. The Relational Data Model
    1. Relations
    2. Attribute
    3. Tuple
    4. Relations as sets
    5. Relations as tables
    6. Relation scheme
    7. Representing relations
    8. Databases
    9. Keys
    10. Storage structures for relations
    11. Secondary index
    12. Navigation among relations
    13. Relational algebra
    14. SQL and relational algebra
    15. Implementing relational algebra operations
    16. Algebraic laws for relations
  3. The Graph Data Model
    1. Directed graph
    2. Nodes and edges
    3. Paths
    4. Cycles
    5. Undirected graphs
    6. Indegree, Outdegree
    7. Implementation of graphs
    8. Connected components of undirected graph
    9. Minimal spanning trees
    10. Greedy algorithm
    11. Depth first search
    12. Dijkstra’s algorithm
    13. Floyd-Warshall Algorithm
    14. Complete graph
    15. Planar and Nonplanar graphs
    16. Graph coloring
    17. Bipartite graph
    18. Breadth first search
  4. Patterns, Automata, and Regular Expressions
    1. State machines and automata
    2. Deterministic and nondeterministic automata
    3. Regular Expressions
    4. UNIX extensions to regular expressions
    5. Algebraic laws for regular expressions
    6. From regular expressions to automata
    7. From automata to regular expressions
  5. Propositional logic
    1. Propositions
    2. Predicate logic
    3. Logical expressions
    4. Precedence of logical operators
    5. Evaluating logical expressions
    6. Truth tables
    7. Implication
    8. Venn diagrams
    9. Boolean functions to logical expresssions
    10. Minterm
    11. Literal
    12. Sum of products
    13. Product of sums
    14. Maxterm
    15. Karnaugh maps
    16. NP-complete
    17. NP-hard
    18. Algebraic laws for logical expressions
    19. Tautologies and methods of proof 
UNT Outcomes: 
  • Use of graph data structures in design of software.
  • Use of relational data structures in design of software.
  • Use of set data structures in design of software.
  • Use of C++ classes to implement graphs, sets and relational data structures.
  • Use of regular expressions to describe patterns.
  • The ability to describe assertions in propositional logic form.
Course Materials: 

online textbook Foundations of Computer Science by Alfred Aho and Jeffrey Ullman: http://infolab.stanford.edu/~ullman/focs.html

UNT Department: 
Computer Science and Engineering (CSE)
Course Level: 
Course Documents: