CMSC210 Syllabus

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

Instructor

Nobo Komagata, komagata@tcnj.edu, Holman Hall 229, Office hours: See the instructor's on-line weekly schedule

On-line Resources (required reading)

Web page: http://www.tcnj.edu/~komagata/cmsc210/03f

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)

Understand that computational problem solving begins with modeling real-world objects and phenomena.
Understand that this type of modeling can be done through formal representation involving mathematical structures, consisting of sets, relations, and/or functions.
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).
Understand that logical statements can specify certain mathematical structures.
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.
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.
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)

Model a variety of real-world phenomena as mathematical structures.
Analyze whether a mathematical structure satisfies a collection of logical statements.
Specify mathematical structures using logical statements.
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.
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.
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.

Take-home exercises: 35% (Module A: 5%, Module B: 10%, Module C: 10%, Module D: 10%)

Given at the end of most class meetings, and due at the beginning of the following class meeting.
Each take-home exercise will be "checked" by the instructor (not formally graded at this point) and will be returned to students with feedback. Students must respond to the instructor's feedback in writing by the end of the respective module.
By the beginning of the respective evaluation workshop, students will file a self-evaluation form (refer to the real form linked in the schedule below) including their exercises and responses to the instructor's feedback. Students propose and justify a grade between 0 and 10 for the entire set of take-home exercises for that module.
Students are also encouraged to provide constructive feedback regarding their learning experience with take-home exercises.
The final take-home exercise grades will be assigned by the instructor, after reviewing students' self-evaluation.

Comprehensive exercises: 60% (Module A: 5%, Module B: 15%, Module C: 15%, Final: 25%)

Given on-line at least 3 days before each module evaluation workshop and at least 1 week before the final evaluation workshop, and due at the beginning of the evaluation workshop. Midterm comprehensive exercises will contain (tentatively) 2 to 4 problems and the final comprehensive exercise will contain 5 to 8 problems.
During the corresponding evaluation workshop, students will form evaluation groups of 2-3 students (to be specified by the instructor for each exercise problem), discuss their work, and fill in a self-evaluation form (refer to the real form linked in the schedule below) for each exercise problem. Students propose and justify a grade between 0 and 10 for each exercise problem. Students must quote other student(s) in the group in support of their evaluation. If only some student in the group were able to respond to the exercise problem, students must exchange ideas regarding how to respond to the problem, still quoting other student(s). In case no one in the group were able to respond to the exercise problem, students must document their difficulty, again quoting other student(s). Students may refer to the course materials including lecture slides and the textbook. Students submit their self-evaluation forms as well as their comprehensive exercises at the end of the workshop.
Students are also encouraged to provide constructive feedback regarding their learning experience involving comprehensive exercises.
The final grades will be assigned by the instructor, after reviewing students' self-evaluation.

Mini project: 5% (Phase 1 at the end of Module B: 1%, Phase 2 at the end of Module C: 1%, Completion at the final evaluation: 3%)

Mini project is due at the end of the designated evaluation workshop. More details are described in the project page.

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%

Take-home exercises: 5%
Comprehensive exercise: 5%

Module B (during a regular class meeting): 26%

Take-home exercises: 10%
Comprehensive exercise: 15%
Mini Project Phase 1: 1%

Module C (during a regular class meeting): 26%

Take-home exercises: 10%
Comprehensive exercise: 15%
Mini Project Phase 2: 1%

Final including Module D (during the designated final exam period): 38%

Take-home exercises (Module D): 10%
Comprehensive exercise: 25%
Mini Project Completion: 3%

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

Discrete Mathematics, 2nd ed. by James L. Hein. Jones & Bartlett. 2003. ISBN: 0-7637-2210-3 [required; available at the TCNJ bookstore; on reserve in the library]

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

Wk	Date	Unit: Topic	Review reading (text sections, handouts)	Exercises
1	8/26	Introduction	Syllabus (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
Fin	12/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: comprehensive	CompEval

The schedule is subject to change.
Course materials will be linked from the underlined words of the on-line syllabus.

<End>