CMSC210 Discrete Structures of Computer Science (Fall 2003, Sections 1 & 2)

Instructor

On-line Resources (required reading)

Course Description

Concepts and structures fundamental to computer science. Declarative programming techniques will be used to explore discrete structures. Topics will include logic, relations, functions, word algebras, induction, and recursion.  [Prerequisite: MATH127 (Calculus 1)]

Learning Goals

The first step of computational problem solving is to transform a real-world problem into a computational problem.  This process requires an ability to identify and formally represent real-world objects and phenomena.  This course introduces tools and techniques to perform this process by way of achieving the following content and performance goals.

Content Goals (core concepts and other associated objectives)
  1. Understand that computational problem solving begins with modeling real-world objects and phenomena.
  2. Understand that this type of modeling can be done through formal representation involving mathematical structures, consisting of sets, relations, and/or functions.
  3. Understand that mathematical structures can be analyzed with respect to the choice of components (sets, relations, and functions) and the properties associated with the components (e.g., reflexivity for a relation, associativity for a certain binary function).
  4. Understand that logical statements can specify certain mathematical structures.
  5. Understand that the connection between logical statements and mathematical structures is not necessarily simple; in general, there are many ways to specify a certain mathematical structure, and many mathematical structures may satisfy a collection of logical statements.  This situation is inherent in mathematical modeling, which can make formal specification difficult.
  6. Identify and analyze certain commonly observed phenomena in Computer Science, e.g., operational structures, ordered structures and Boolean algebra, graphs/digraphs/trees, languages/automata, and discrete probability/counting.
  7. Understand the connection between informal reasoning and formal proofs, a systematic way of manipulating logical statements, consistent with the intended mathematical structures.
Performance Goals (expected outcomes and abilities to be observed as a result of successful learning)
  1. Model a variety of real-world phenomena as mathematical structures.
  2. Analyze whether a mathematical structure satisfies a collection of logical statements.
  3. Specify mathematical structures using logical statements.
  4. Analyze, distinguish, and relate mathematical structures, especially those commonly observed in Computer Science, with respect to their components and the properties associated with the components.
  5. Identify cases where (i) different set of logical statements satisfy the same mathematical structures, and (ii) a set of logical statements satisfies multiple mathematical structures including unintended ones.
  6. Convince others that the modeling process is logically sound, using proofs and informal methods of justification.

Course Modules

The main part of the learning goals involves many abstract concepts.  In order to become familiarized with these concepts, this course proceeds in four modules, where the degree of abstractness increases gradually.

A: Informal Analysis. This module is an informal overview of the course. We will touch upon many essential components of discrete math informally, i.e., with minimal use of mathematical symbols. By the end of this module, students must be able to state general ideas about modeling processes and the connection between the essential components of discrete math.

B: Formal Representation. Although intuitive understanding of the topics is more important than just being able to manipulate symbols, the informal approach has many limitations, including precision and conciseness. In order to overcome such shortcomings, this module introduces formal notation used in discrete math. At the end of this module, students must be able to state the ideas developed in Module A using mathematical notations.

C: Mathematical Structures. By this time, students will be able to communicate with other scientists/engineers using the language of discrete math. With the help of the formal notation, we will be able to discuss more easily a collection of mathematical structures that are commonly observed in Computer Science. By the end of this module, students must be able to see such mathematical structures in certain real-world phenomena.

D: Logical Reasoning. Another important aspect of modeling is that the process must be convincing. In this module, we will practice how to make logical arguments, which are relevant to modeling processes. As a result, students must be able to convince others about the logical soundness of such processes.

Assessment

This semester, we introduce self-evaluation as an integral part of the student assessment in this course.  There will be three in-class evaluation workshops for Modules A, B, and C, and the final evaluation workshop during the final exam period.  Three assessment components are described below.
At the end of each evaluation workshop, students will submit a collection of documents (may be called "portfolio") required for that module.  These documents must be bundled in an organized manner, e.g., in a manila folder or a large envelope.  All take-home and comprehensive exercises must be attached to the corresponding self-evaluation forms in an appropriate order.   The documents will be kept with the instructor, but students will have access to them as they wish.

In general, regular take-home and comprehensive exercises will be of a similar type.  Many of them will be set in a more or less realistic context.  Some problems will be open-ended, like many real-world problems.  The main difference between regular take-home exercises and comprehensive exercises is that the former is used more for practicing and the latter, more for evaluation.  Note that you are encouraged to discuss any of the above components, including comprehensive exercises, with other students and/or the instructor.  However, your writing must reflect your own understanding.  That is, you must not simply copy someone else' work with or without their consent (this is in violation of the academic integrity policy at TCNJ).  In addition, if you did not regularly submit take-home exercises and give a high self-evaluation, you will most likely be asked to support your self-evaluation in person.  For fair student assessment, the instructor reserves the right to verify students' accomplishments with respect to the performance goals at any point through oral examination and other means.  In fact, you will most likely be invited to the instructor's office for discussion at least once during the semester.

The assessment procedure can also be seen chronologically for each evaluation workshop as follows:

Module A (during a regular class meeting): 10%
Module B (during a regular class meeting): 26%
Module C (during a regular class meeting): 26%
Final including Module D (during the designated final exam period): 38%
After each evaluation workshop, students' grades will be posted for review.  For Modules A, B, and C, students will have a chance to discuss their self-evaluation and the instructor's evaluation as soon as the final grades are posted.  The course grades will be reported as soon as the final evaluation is complete.  Although  students' course grades will be reported to The College at that point, students are still encouraged to discuss the final evaluation.  If there is a need, grade change will be reported.

Overall course grades will be determined by adding the component scores according to the weight shown above.  The target cutoff points for A, B, C, and D/pass are 90, 80, 70, and 60%, respectively.  However, these cutoffs may be adjusted depending on the difficulty of the course materials. Each of the letter grades may be qualified with '+' and '-', tentatively the upper and the lower one third (where applicable) of a range, respectively (e.g., 93% for A, 90% for A-).  For more details about the course, consult the on-line course handbook and the instructor's information page for students.

Textbook

Schedule:  Lectures: Tue/Fri, Sec1 9:30-10:50 a.m./Sec2 12:30-1:50 p.m., both in HH253

WkDateUnit: TopicReview reading (text sections, handouts)Exercises
18/26
IntroductionSyllabus (this), Course Handbook
00


Module A: Informal Analysis
-
-
 8/29
A1: Mathematical Modeling (logic and structure)
lecture notes
A1
2
9/2
no class (Monday schedule)
-
-

9/5
A2: Sets, Relations, Functions (preview)
lecture notes
A2
3
9/9
A3: Structures (preview)
lecture notes
A3

9/12
A4: Logic (preview)
lecture notes, Project page, Module A Supplement
Comp, ExEval
4
9/16
Module A Evaluation Workshop
Scope: everything covered by this time
CompEval, B0


Module B: Formal Representation
-
-

9/19
Canceled due to power outage
-
-
5
9/23
B1: Sets
1.2-1.2.3
B1

9/26
B2: Relations
1.3-1.3.1, 1.3.4, p. 194 (properties)
B2
6 9/30
B3: Functions
2.1, 2.3-2.3.2
B3, supp
  10/3
B4: Structures
10.1
B4
7 10/7
B5: Propositional Logic
6.1, 6.2-6.2.2, (6.3.1-6.3.2), 1.1, supp
B5

 

10/10
B6: First-Order Logic
7.1-7.1.2, supp
B6, sol
8
10/14
B7: Logic and Structures
7.1-7.1.2, lecture notes, supplemental exercises w/sol
Comp, ExEval

10/17
Module B Evaluation Workshop
Scope: everything covered by this time
CompEval


Module C: Mathematical Structures
-
-
9
10/21
no class (fall break)
-
-
  10/24
C1: Operational/Relational Structures
1.3.2-1.3.3, 10.3-10.3.2, 4.1-4.1.1, 4.3-4.3.1
C1
10 10/28
C2: Boolean Algebra
10.2.1, (10.2.2)
C2

10/31
C3: Ordered Structures
4.3-4.3.1
C3
11
11/4
C4: Graphs/Trees
1.4-1.4.4
C4

11/7
C5: Languages/Automata
1.3.3, 3.3-3.3.3, lecture notes
C5, sol
12
11/11
C6: Counting/Probability
5.3, 2.3.3, lecture notes, supp
Comp, ExEval

11/14
Module C Evaluation Workshop
Scope: everything covered by this time
CompEval


Module D: Logical Reasoning
-
-
13
11/18
D1: Sets (including inductive definition)
1.2-1.2.3, 3.1-3.1.3
D1

11/21
D2: Relations (including equivalence relation)
1.3-1.3.1, 1.3.4, 4.2
D2, supp
14
11/25
D3: Functions (including recursion)
2.1, 2.2-2.2.1, 2.3-2.3.2, 3.2-3.2.3
D3

11/28
no class (Thanksgiving break)
-
-
15
12/2
D4: Logic (including mathematical induction)
4.4.1
D4, sol

12/5
ZZ: Review; Conclusion
lecture notes
Comp, ExEval
Fin12/12
Final Evaluation Workshop
Sec 1: 8:00-10:00 a.m. in HH253
Sec 2: 11:00 a.m.-1:00 p.m. in HH253
Scope: comprehensiveCompEval
<End>