Table of Contents

• 1. Foundations of Computer Science (221)
• 2. Computer Science 221 - Fall 1997
  • 2.1. General Information
  • 2.2. My Curriculum Vitae
  • 2.3. Course Description
  • 2.4. Main Course Objectives
  • 2.5. Grading
  • 2.6. Other Things
• 3. COURSE OUTLINE:
• 4. Preliminaries
  • 4.1. Sets and Basic Set Operations
  • 4.2. Defining and denoting sets
  • 4.3. Identifiers
  • 4.4. Membership
  • 4.5. Three Fundamental Features of Sets
  • 4.6. Subset
  • 4.7. Basic Set Operations
  • 4.8. Exercises
  • 4.9. Basic Set Identities
  • 4.10. Exercises
• 5. Relations
  • 5.1. Domains and Ranges
  • 5.2. Some Operations on Relations
  • 5.3. Exercises
• 6. Graphs and Trees
  • 6.1. Paths and Reachability
  • 6.2. Other Representations of a Graph
  • 6.3. Computing Paths from a Matrix Representation
  • 6.4. An Example
  • 6.5. Traversing a Graph
  • 6.6. BFS
  • 6.7. DFS
  • 6.8. Dijkstra's Algorithm for Finding Minimum Paths
  • 6.9. Trees
  • 6.10. Recursions on Binary Trees
  • 6.11. Operations on Binary Search Trees
  • 6.12. Looking Up an Element in a BST
  • 6.13. Inserting an Element in a BST
  • 6.14. Deleting an Element from a BST
• 7. Induction and Recursion
  • 7.1. Natural Numbers
  • 7.2. Peano Axioms
  • 7.3. Mathematical Induction
  • 7.4. Recursion
  • 7.5. Tower of Hanoi
  • 7.6. Working out recursive solutions
  • 7.7. How to move n rings from peg A to peg C?
  • 7.8. Quicksort
  • 7.9. Backtracking
  • 7.10. The Eight Queens on a Chess Board Problem
  • 7.11. The Knapsack Problem
  • 7.12. Pit Falls
• 8. Machines and Grammars
  • 8.1. Pattern
  • 8.2. Finite State Machines
  • 8.3. Regular Expressions
  • 8.4. Values of Regular expressions
  • 8.5. Operators of Regular Expressions
  • 8.6. Union
  • 8.7. Precedence of Regular Expressions
  • 8.8. The UNIX Extensions to Regular Expressions
  • 8.9. Additional Operators
• 9. Context-Free Grammars, Parse Tree and Parser
  • 9.1. Context-Free Grammars
  • 9.2. A CFG for Arithmetic Expressions
  • 9.3. Generating Strings from a CFG
  • 9.4. CFGs with Epsilon Productions
  • 9.5. CFGs vs Regular Expressions
  • 9.6. Parse Trees
  • 9.7. Ambiguous Grammars
  • 9.8. The Problem of Ambiguous Grammars.
  • 9.9. Ambiguous Precedence
  • 9.10. An Unambiguous Grammar for Expressions
  • 9.11. Parsing
  • 9.12. Recursive-Descent Parsing
  • 9.13. A Real Parser: Yacc
  • 9.14. A few different Languages
  • 9.15. Textprocessing
  • 9.16. HTML
  • 9.17. Shellprogramming
  • 9.18. xc, the UIL for the X Window System
  • 9.19. Arguments
  • 9.20. Windows
  • 9.21. Events
  • 9.22. Events und FSM
• 10. Analysis of Algorithms
  • 10.1. Two major kinds of problems
  • 10.2. How will we solve these problems?
  • 10.3. A few Algorithms To Analyse
• 11. Touring Machines
  • 11.1. Who was Alan Turing
  • 11.2. Turing Machine
  • 11.3. The Halting Problem
  • 11.4. Goedel Theorem
  • 11.5. The Turing Test

Last modified 22/May/97