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]