CSCE 355: Foundations of Computation

 

Catalog Description:

355—Foundations of Computation. (3) (Prereq: CSCE 211, 212, 350) Basic theoretical principles of computing as modeled by formal languages, grammars, and machines; computability and computational complexity.  Major credit may not be received for both CSCE 355 and CSCE 551.

 

Prerequisite(s) By Topic:

Logic design and Boolean algebra

Computer architecture

Analysis of algorithms

 

Textbook(s) and Other Required Material:

Introduction to Languages and the Theory of Computation, (2nd ed.), John C. Martin, McGraw-Hill, New York, NY, 1997.

 

Computing Platform: Windows 2000

 

Course Objectives: {Assessment Methods Shown in Braces}

1.       Represent mappings as functions, sequences, and relations;

2.       Show the properties of relations using matrices, graphs and other tools;

3.       Analyze and design finite state acceptors, regular grammars, and regular expressions;

4.       Determine a push down automata for a context-free grammar and vice versa;

5.       Design a Turing machine to evaluate a function or accept a given language;

6.       Perform algorithm analysis with Big Oh.

 

Topics Covered:

1.       Review of logic, and sets.

2.       Functions, sequences, relations, recursive binary relations.

3.       POSET, QUOSET, Total Order, and Partitions.

4.       Strings and Languages.

5.       Formal grammars especially regular grammars and context-free grammars.  BNF.

6.       Regular Expressions.

7.       Mealy and Moore Finite State Machines.

8.       Deterministic and nondeterministic finite state acceptors.

9.       Pushdown Automata.

10.   Turing Machines

11.   Time Complexity

 

Laboratory Projects

none

 

Syllabus Flexibility: Low.  The Undergraduate Committee approves the choice of textbook and syllabus. 

 

Relationship of Course to Program Outcomes:

The contribution of each course objective to meeting the program outcomes is indicated with the scale: 
3 = major contributor, 2 = moderate contributor, 1 = minor contributor.  Blank if not related.








Course Objectives

Program Outcomes

1. Logic & Math

2. Computing Fundamentals

3. Apply Computing Principles

4. Work on teams

5. Communicate Effectively

6. Liberal arts & Soc. Sciences

7. Basic Science and Lab Procedures

8. Learn New Tools & Processes

9. Employed upon Graduation

10. Application Area

11. Electronics and Digital Sys Design

1. Represent mappings as functions, sequences, and relations

3

3

 

 

 

 

 

 

 

 

 

2. Show the properties of relations using matrices, graphs, and other tools

3

3

 

 

 

 

 

 

 

 

 

3. analyze & design finite state acceptors, regular grammars, and regular expression

 

3

 

 

 

 

 

 

 

 

 

4. determine a push down automata for a a context-free grammar and vice versa

 

3

 

 

 

 

 

 

 

 

 

5. design a Turing machine

 

3

 

 

 

 

 

 

 

 

 

6. algorithm analysis with Big Oh

 

3

3

 

 

 

 

 

 

 

1

Estimated CSAB Category Content:

Algorithms:                                                         2 hrs

Data Structures:                                                  0

Software Design:                                                0

Concepts of Programming Languages                  1

Organization and Architecture                             0

Oral and Written Communication: none

Social and Ethical Issues: none

Theoretical Content:

Finite State Machines, Transducers and Acceptors, etc., Logic, Sets, Functions, Sequences, Strings, Relations, Algebraic Structures—POSET, QUOSET, Partition, and Total Order, Languages, and Grammars, etc

Analysis and Design:

Finite State Machines, Transducers and Acceptors, etc.

Class/Laboratory Schedule:

Lecture:                3 periods of 50 minutes or 2 periods of 75 minutes per week

Recitation:             0 periods per week

Laboratory:            0 periods per week

Course Coordinator: Ronald D. Bonnell

Modification and Approval History:

Initial description, April 1999

Revised, May 2001