Instructor Donald Braffitt Date 15-Sep-1981
---------- (603) 888-1311 Rivier X60 (Box 895) ----
Course No. CS501A/MA304E Title of Course Fundamentals of Computation
---------- CS501B/MA304G ---------------
Rivier College - Nashua, New Hampshire - Fall 1981
Tuesdays 5:30 PM to 7:30 PM or Tuesdays 7:45 PM to 9:45 PM
15-Sep-1981 to 22-Dec-1981 (final exam)
Course Berztiss, A. T. Data Structures Theory and Practice.
Textbooks Second Edition. New York: Academic Press, 1975.
--------- Ledgard, Henry and Michael Marcotty. The Programming Language
Landscape. Chicago: Science Research Associates, Inc., 1981.
Objectives
----------
This course will introduce some of the mathematical theory and techniques
underlying computer science. Topics include set theory, graph theory,
algebra, and combinatorics.
Teaching Strategies
-------------------
Class will usually include reviewing the solutions to the problems turned in
at the beginning of class. New material will usually be introduced that
corresponds to the problems due the following week.
Course Requirements
-------------------
The required work for the course consists of a weekly set of problems (13 in
all) and 5 exams. You are responsible for all material presented in class as
well as the appropriate textbook material. Attendance will be taken each
class period. Regular attendance is expected. The work you turn in on exams
must be entirely your own (all exams will be closed book and closed notes).
However, you are allowed to discuss the homework assignments with any other
member of the class. Each homework assignment should consist of 10 problems
(or the number available) that you select from the problems for that
assignment with at least 2 problems (or the number available) from each text
book section (the problems are marked by text book section). The problems
should be from those NOT solved in the back of the book. You should attempt
all the problems (most exam problems will be very similar to the textbook
problems). The best preparation for the exams should prove to be working out
solutions to the textbook problems. The final product on each homework
assignment must be substantially your own work. Homework must be handed in at
or prior to the beginning of class on the day it is due. The work you do
outside of class for this course (reviewing class notes, reading, homework
assignments, reviewing for exams) should average 4 to 8 hours per week.
Please keep all graded homework assignments and exams until the course is
over. The homework assignments and exams should generally be handed back
graded the following week.
Examinations Grading Weights
------------ ---------------
Chapter 1 exam 29-Sep [2nd half of 1st hour] 5%
Midterm exam (Chapters 1 and 2) 20-Oct [1st hour] 16%
Chapter 3 exam 10-Nov [2nd half of 1st hour] 5%
Chapter 4 exam 01-Dec [2nd half of 1st hour] 5%
Final exam (Chapters 1-4 and 6-7) 22-Dec [both hours] 30%
Homework - 13 problem sets @ 3% each 39%
Page 2
Course Outline
--------------
Chap 1 - Set Theory (2 weeks) Chap 7 - Digraphs of Programs
1a. Basic Definitions (1 week)
1b. Indexed Sets 7a. Flowchart Digraphs
1c. Complement of a Set 7b. Detection of Programming
1d. Algebra of Sets Errors
1e. Algebra of Sets as an Axiomatic Theory 7c. Segmentation of Programs
1f. Venn Diagrams 7d. Automatic Flowcharting
1g. The Ordered Pair and Related Concepts
1h. Permutation and Combinations Chap 4 - Algebras and Strings
(2 weeks)
Chap 2 - Functions and Relations (3 weeks) 4a. Algebraic Structures
2a. Functions 4b. Group Codes
2b. Boolean Functions and Forms 4c. Algebra of Strings
2c. Applications of Boolean Functions 4d. Markov Algorithms
2d. Relations 4e. Languages and Grammars
2e. The Equivalence Relation 4f. Languages and Automata
2f. Ordering Relations
2g. Lattices Chap 6 - Paths and Cycles in
2h. Abstract Algebras Diagraphs (2 weeks)
6a. Shortest Path Problems
Chap 3 - Graph Theory (3 weeks) 6b. Cycles
3a. Diagrams and Graphs 6c. A Scheduling Problem
3b. Basic Definitions in the Theory of 6d. Critical Path Scheduling
Digraphs
3c. Digraphs, Matrices, and Relations
3d. Connectedness in a Diagraph
3e. Trees
3f. Linear Formulas of Digraphs
3g. Isomorphism of Digraphs
3h. Planar Graphs
For a given week, the "Problems" are due at the beginning of class and "Text"
and "Sections" refer to the textbook material that should provide the best
preparation for the material covered in class.
Week Class Text Sections Problems Exams
---- ----- ---- -------- -------- -----
1 15-Sep 3-23 1a-1e
2 22-Sep 23-43 1f-1h 1.1-1.29
3 29-Sep 49-62 2a-2b 1.30-1.57 Chapter 1
4 06-Oct 63-82 2c 2.1-2.18
5 13-Oct 83-106 2d-2h 2.19-2.41
6 20-Oct 119-128 3a-3b 2.42-2.91 Midterm
7 27-Oct 129-146 3c-3e 3.1-3.13
8 03-Nov 146-164 3f-3h 3.14-3.38
9 10-Nov 315-326 7a-7d 3.39-3.54 Chapter 3
10 17-Nov 169-187 4a-4c 7.1-7.12
11 24-Nov 187-204 4d-4f 4.1-4.34
12 01-Dec 269-284 6a 4.35-4.58 Chapter 4
13 08-Dec 284-308 6b-6d 6.1-6.18
14 15-Dec Review Chapters 1-4 and 6-7 6.19-6.40
15 22-Dec Final
Page 3
Bibliography
------------
Tremblay, Jean-Paul and Ram P. Manohar. Discrete Mathematical Structures
with Applications to Computer Science. New York: McGraw-Hill, 1975. [set
theory, graph theory, algebra]
Stanat, Donald F. and David F. McAllister. Discrete Mathematics in Computer
Science. Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1977. [set
theory, graph theory, algebra]
Larson, Max D. Fundamental Concepts of Modern Mathematics. Reading,
Massachusetts: Addison-Wesley Publishing Company, 1970. [set theory,
algebra]
Wimbish, G. Joseph, Jr. Mathematics: A Humanistic Approach. Belmont,
California: Wadsworth Publishing Company, Inc., 1972. [set theory]
Bobrow, Leonard S. and Michael A. Arbib. Discrete Mathematics: Applied
Algebra for Computer and Information Science. Philadelphia: W. B. Saunders
Company, 1974. [set theory, graph theory, algebra]