UNT | University of North Texas

Search form

CSCE 2100: Computing Foundations I

Course Number: 
CSCE 2100
Course Name: 
Computing Foundations I
Description: 

 Introduces students to both data structures and formalisms used in computer science, such as asymptotic behavior of algorithms. Data structures and the 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 first 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): 
3.00
UNT Topics: 
  1. Computer Science: The Mechanization of Abstraction
    1. Abstraction
    2. Exam scheduling
    3. Data models
    4. Data structures
    5. Algorithms
    6. Recursion
    7. Type system
    8. Data object
    9. Linked lists
    10. Modeling filesystems as trees
    11. Processes and pipes
    12. Text editors
    13. Logic gates
    14. Truth tables
    15. Overview of the C programming language
      1. Types 
      2. Structures
      3. Unions
      4. Typedefs
      5. Functions
      6. Object creation and disposal
      7. Data access and modification
      8. Arithmetic, logical, bitwise, comparison, and assignment operators
    16. Software development process
    17. Good rules for programming style
  2. Iteration, Induction, and Recursion
    1. Iterative programming
    2. Sorting
    3. Inductive Proofs
    4. Complete Induction
    5. Proving Properties of Programs
    6. Recursive Definitions
    7. Recursive Functions
    8. Profiling
    9. Mergesort as an example of Divide and Conquer
    10. Proving Properties of Recursive Programs
  3. The Running Time of Programs
    1. Characteristics of good algorithms
    2. Measuring running time
    3. Asymptotic Notation
    4. Simplifying Expressions
    5. Analyzing the Running Time of a Program
    6. Analyzing programs with function calls
    7. Analyzing programs with recursive calls
    8. Recurrence relations
  4. Combinatorics and Probability
    1. Counting Assignments
    2. Counting Permutations
    3. Ordered Selections
    4. Unordered selections
    5. Counting Combinations
    6. Orderings with Identical Items
    7. Distribution of Objects to Bins
    8. Combining Counting Rules
    9. Introduction to Probability Theory
    10. Conditional Probability
    11. Probabilistic Reasoning
    12. Expected Value Calculation
    13. Programming Applications of Probability
    14. Probability Distributions
  5. The List Data Model
    1. List Terms
    2. List Operations
    3. Linked lists
    4. Stacks
    5. Function Calls with Stacks
    6. Longest Common Subsequence as an Example of Dynamic Programming
    7. Representing Character Strings
  6. The Tree Data Model
    1. Node
    2. Edge
    3. Root
    4. Parent and child
    5. Recursive definition of tree
    6. Sibling
    7. Path length
    8. Ancestor and descendant
    9. Level
    10. Expression tree
    11. Data structures for trees
      1. Array of Pointers
      2. Leftmost Child Right Sibling
    12. Tree traversal
    13. Evaluating expression trees
    14. Postfix, Infix, Prefix
    15. Tree height
    16. Binary trees
    17. Binary search trees
    18. Priority queues
    19. Heaps
    20. Heapsort
UNT Outcomes: 
  • A solid foundation in conceptual and formal models.
  • The ability to use abstraction in the design and description of algorithms.
  • Use of C++ classes to implement trees, and lists.
  • Application of big-Oh notation to evaluating and comparing algorithms.
  • Use of tree, and list data structures in design of software.
  • An ability to apply combinatorics in solving real-world problems.
Course Materials: 

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: 
Undergraduate
Course Documents: