Visual Syllabus as Concept Map

Course Information, Meeting Times, and Meeting Dates.

CPSC 350, section 1, Foundations of Computer Science. Meets at 1:25-2:15, MWF, in Daniel 408.

Be Absolutely Sure You Read

Specific Homework Assignments

This section will contain lists of homework and the due dates.

1. [9 Sep.] There are 14 problems on pages 35-36 of the handout. Do at least half.
2. [16 Sep.] 1-8 on page 86 of the handout.
3. [18 Sep.] Section 1.2, page 23. 8, 9 (any 3), 10, 11, 14
4. [20 Sep.] Section 1.3, page 36. 2, 3, 4, 6, 7.
5. [23 Sep.] Section 1.4, page 48. 1, 2, 3, 4, 5, 7, 9, 10.

As announced in class, the homework will no longer be due at a particular date. The homework is now due the class period after the material is discussed. This is to encourage you to do the homework exercises as part of your pre-study of the material.

1. [2.1;p 60] 1(a,c); 5; 8; 9.
2. [2.2;p 70] 3;5;10.
3. [2.3;p 89] 1(c);2(a);3;5;7;8;10(d);14;15.
4. [2.4;p 97] 3;4;8. (Note: 10 is seminal problem).
5. [2.5;p 113] 2;4;5;6;8.

Goals and Objectives.

• List the four classes of automata, grammars, and languages in the Chomsky hierarchy in `inclusion' order.
• Design finite state machines to accept "simple" regular languages.
• Design pushdown automata to accept "simple" context free languages.
• Prove the halting problem and understand its ramifications.
• Program recursive function solutions, in the student's choice of programming language, to "simple" problems.
• Have a fundamental understanding of proofs of correctness.
• Be able to name examples of various language types of the Chomsky hierarchy.
• Be able to use context free grammars to parse context free languages.
• Know what it means for a problem to be undecidable.
• Understand levels of computational complexity.

Topical Outline

Unit I. Fundamental Structures

This unit consists of Chapters 1, 2, and 3. Initially we will skim these chapters to remind you what sets are, and what functions and relations are. Section 1.4 will be covered in depth, especially the section on grammars.

We will cover Chapter 2 in depth since it introduces induction and recursion.

We will look at section 3.2 and 3.3. It is important that you understand what it means to be a proof and what it means to be a theory.

Unit II. Type I and Type II Systems

This unit consists of Chapters 5 and 6.

Chapter 5 deals with three separate descriptions of what turn out to be the same computational power. Finite State Machines are useful for describing computer hardware. Regular languages are particularly simple pattern sets that occur quite often. Regular Expressions are a particularly useful way of specifying pattern searches. We also get a chance to study an important class of processes known as non-deterministic. Nondeterminism is a form of parallel processing.

Chapter 6 deals with language and machine systems that work particularly well with compiler-implemented languages like C.

Unit III. Best of the Rest

This will consist of selected portions of Chapters 3, 4, 7, 8, and 9.

• 3.6 Program correctness and semantics of programming languages.
• 4.2 Prolog
• Chapter 7
• Chapter 8
• Chapter 9

Work Assignments

Portfolio

As an experiment, the Spring 1996 class did a portfolio. It was added late in the class. This Fall 1996 semester will again include a portfolio.

Nature of Group Project(s).

It is my experience that students do better in this course when they work in groups. Professor Ron Nowaczyk and I are working on some further considerations for forming these groups. As soon as practical, we will form groups. Until then, you should informally form you own groups of no more than 3 students.

Nature and grading of programs.

No programming projects are anticipated at this time.

Exact weights to tests, homework, lab, and finals.

• Two midterm exams are 20 percent each.
• Homework is 40 percent.
• Final is 20 percent.