CSC/ISC 221 - Foundations of Computer Science

---

I. COURSE NUMBER AND CREDIT:

		 CSC/ISC 221 - 3 S.H.

II. COURSE TITLE:

        Foundations of Computer Science

III. COURSE DESCRIPTION:

        This course will provide students with a broad
        perspective of computer science and will acquaint
        them with various formal systems on which modern
        computer science is based.  Students will study the
        structure and interpretation of four classes of
        abstract computing machine

IV. PREREQUISITES:

        CSC 212 - Principles of Computing

V. JUSTIFICATION:

        There is a need to provide students with a broad
        perspective of computer science, which they do not
        derive from any other single computer science course.
        There is a need to acquaint students with various
        formal systems on which modern computer science is
        based.  One section of this class will be taught each
        semester to classes of size thirty-two.  This course 
       is required for CS majors.

VI. COURSE OBJECTIVES:

        As a result of this course, students will be able to:
        1.  Understand concepts needed for Functional
            programming, Imperative programming, and Object
            Oriented programming.
        2.  Understand recursion.
        3.  Read syntax diagrams.

VII. COURSE OUTLINE:

        A.  Foundations of Functional Programming
            1.  Sets:  subsets; power sets; Cartesian
                products; basic algebra of sets.
            2.  Functions:  definitions; examples with
                interesting domains and co-domains;
                injections, surjections, bijections;
                composition; inverse functions.
            3.  Induction and recursion.
            4.  Syntax and semantics of a simple strongly
                typed functional programming language
                (FPL).
            5.  Programming in the FPL (simple, rich
                examples).
            6.  Close examination of function application
                in the FPL context.  Argument passing,
                return of values; composition, evaluation
                strategies. 
            7.  Induction and recursion in the FPL context.
            8.  Formal specification; verification.
        B.  Foundations of Imperative Programming
            1.  Alphabets; strings of alphabetic symbols;
                languages (sets of strings).
            2.  Phrase-Structure Grammars.
            3.  Regular Languages and Finite-State Automata
            4.  Regular Sets
            5.  More general languages (including context
                free) and machines (including Turing
                machines).
            6.  Applications:  Programming language
                definition (token level and statement level);
                programming language interpretation;
                combinational networks; augmented transition
                networks and natural language understanding,
                computability.
        C.  Foundations of Object Oriented Programming
            1.  Objects and Operators (imaginative
                examples).
            2.  Algebraic System Fundamentals and
                Examples.
            3.  Examples from Mathematics.
                a.  Abstract Examples:  Groups; Rings.
                b.  Concrete Examples:  Boolean Algebras;
                    Matrix Algebras.
            4.  Abstract Data Types
                a.  Formal specification.
                b.  Realization in, say, the FPL of I.
                c.  Application to software construction.
            5.  Modeling and Inheritance:
                a.  Definition of relations isa and
                    partof.
                b.  Recursive processing of isa and
                    partof.
                c.  Application to data modeling and

                    and artificial intelligence.

VIII. METHODS OF INSTRUCTION:

        Lectures, discussion, and classroom demonstration.

IX. COURSE REQUIREMENTS:

        Assigned readings, papers, and projects.

X. MEANS OF EVALUATION:

        Problem sets and examinations.

XI. RESOURCES:

        No additional resources needed.

XII. BIBLIOGRAPHY:

        Aho, A. & Ullman J. (1992). Foundations of Computer
        Science, New York, Computer Science.
        Graham R. & Knuth D. & Patashnick O. (1989). Concrete
        Mathematics, Reading, MA, Addison-Wesley.
        Henderson, P (1980). Functional Programming,
        Englewood Cliffs, N.J., Prentice-Hall.
        Davis, D. and Weyuker, E (1983). Computability,
        Complexity, and Languages, New York, Academic Press.
        Wos, L., Overbeek, R., Lusk, E., and Boyle, J (1984).
        Automated Reasoning. Englewood Cliffs, N.J.,
        Prentice-Hall.