Table of Contents

• 1. Foundations of Computer Science -- CSC 221 -- Sping 1998
• 2. General Information
  • 2.1. My Curriculum Vitae
  • 2.2. Course Description
  • 2.3. Main Course Objectives
  • 2.4. Grading
  • 2.5. 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. Introduction into Nassi Shneidermann Diagrams
  • 6.1. Functions and Recursion
  • 6.2. Tower of Hanoi
  • 6.3. Problem
• 7. Graphs and Trees
  • 7.1. Paths and Reachability
  • 7.2. Other Representations of a Graph
  • 7.3. Computing Paths from a Matrix Representation
  • 7.4. An Example
  • 7.5. Traversing a Graph
  • 7.6. BFS
  • 7.7. DFS
  • 7.8. Dijkstra's Algorithm for Finding Minimum Paths
  • 7.9. Trees
  • 7.10. Recursions on Binary Trees
  • 7.11. Operations on Binary Search Trees
  • 7.12. Looking Up an Element in a BST
  • 7.13. Inserting an Element in a BST
  • 7.14. Deleting an Element from a BST
• 8. Induction and Recursion
  • 8.1. Natural Numbers
  • 8.2. Peano Axioms
  • 8.3. Mathematical Induction
  • 8.4. Recursion
  • 8.5. Tower of Hanoi
  • 8.6. Working out recursive solutions
  • 8.7. How to move n rings from peg A to peg C?
  • 8.8. Quicksort
  • 8.9. Backtracking
  • 8.10. The Eight Queens on a Chess Board Problem
  • 8.11. The Knapsack Problem
  • 8.12. Pit Falls
• 9. Machines and Grammars
  • 9.1. Pattern
  • 9.2. Finite State Machines
  • 9.3. Regular Expressions
  • 9.4. Values of Regular expressions
  • 9.5. Operators of Regular Expressions
  • 9.6. Union
  • 9.7. Precedence of Regular Expressions
  • 9.8. The UNIX Extensions to Regular Expressions
  • 9.9. Additional Operators
• 10. Context-Free Grammars, Parse Tree and Parser
  • 10.1. Context-Free Grammars
  • 10.2. A CFG for Arithmetic Expressions
  • 10.3. Generating Strings from a CFG
  • 10.4. CFGs with Epsilon Productions
  • 10.5. CFGs vs Regular Expressions
  • 10.6. Parse Trees
  • 10.7. Ambiguous Grammars
  • 10.8. The Problem of Ambiguous Grammars.
  • 10.9. Ambiguous Precedence
  • 10.10. An Unambiguous Grammar for Expressions
  • 10.11. Parsing
  • 10.12. Recursive-Descent Parsing
  • 10.13. A Real Parser: Yacc
  • 10.14. A few different Languages
  • 10.15. Textprocessing
  • 10.16. HTML
  • 10.17. Shellprogramming
  • 10.18. xc, the UIL for the X Window System
  • 10.19. Arguments
  • 10.20. Windows
  • 10.21. Events
  • 10.22. Events und FSM
• 11. Java Studio: Java For the Rest of Us!
  • 11.1. The Java Studio Architecture
  • 11.2. Layout und Functionality
  • 11.3. Example
  • 11.4. Layout
  • 11.5. Functionality
  • 11.6. A Celcius Fahrenheit Converter
  • 11.7. Fahrenheit Converter: Layout
  • 11.8. Fahrenheit Converter: Functionallity
  • 11.9. A Real Converter
  • 11.10. A Minimum Maximum Thermometer
  • 11.11. First Idea
  • 11.12. Conclusion
  • 11.13. Problems
  • 11.14. Misc
  • 11.15. Requirements
  • 11.16. Addresses
• 12. Analysis of Algorithms
  • 12.1. Two major kinds of problems
  • 12.2. How will we solve these problems?
  • 12.3. A few Algorithms To Analyse
• 13. Touring Machines
  • 13.1. Who was Alan Turing?
  • 13.2. Turing Machine
  • 13.3. The Halting Problem
  • 13.4. Goedel Theorem
  • 13.5. The Turing Test

Last modified 27/July/98