CSCE 222: Discrete Structures for Computing

Instructor: Dr. Dylan Shell.

Office	:	PETR 315
Phone	:	(979) 845-2369
Email	:	dshell@tamu.edu
Web	:	http://robots.cs.tamu.edu/dshell/cs222
Office hours	:	Walk-ins: Wednesdays, 2:00pm–3:00pm
		Otherwise by appointment via e-mail too.
		(See link below under "Resources" for TA Office Hours.)

Fall 2024

Lecture Time	:	Tue/Thr, 12:45pm–2:00pm.
Lecture Location	:	ZACH 244

Course Description

This course provides the mathematical foundations from discrete mathematics for analyzing computer algorithms, for both correctness and performance; introduction to models of computation, including finite state machines and Turing machines.

Prerequisites

Students must have completed MATH 151, or an equivalent course.

Learning Outcomes or Course Objectives

At the end of the course, students will understand the basic principles of logic, proofs and sets. Students will be able to apply results from discrete mathematics to the analysis of algorithms. Students will be able to produce proofs by induction and apply counting/enumeration techniques. Students will have a basic understanding of models of computation.
It is expected that successful participation in the course will allow the student to demonstrate:

• a basic understanding of logic and predicates;
• the application of basic techniques for formal proof;
• the ability to use these concepts in the analysis and design of algorithms;
• a basic understanding of classical models of computation.

Textbook

Discrete Mathematics and Its Applications by Kenneth Rosen, 8th Edition, McGrawHill, 2019.

Grading Policies

Grades will be based on: 30% : Comprehensive Final Exam (individual) 25% : Midterm Exam I 25% : Midterm Exam II 20% : Homework

The grading scale is: A 90-100 B 80-89 C 70-79 D 60-69 F 59 or below

This current page (i.e., the one you are reading now) will serve as the most up-to-date source of official information.

Resources

• The course syllabus.
• Here is the TA Office Hours Schedule.

Course Topics, Calendar of Activities, Major Assignment Dates

Week-by-week topic breakdown (timeline is approximate, and intended for guidance only)

Week	Topic	Textbook
1	Course Introduction. Propositional and Predicate Logic	1.1–1.5
2	Inference and Proofs	1.6–1.8
3	Sets, Functions	2.1–2.3
4	Algorithms and their complexity	3
5	Sequences and sums	2.4–2.5
6	Proof by Induction	5.1–5.2
7	Midterm I
8	Guest lecture
9	Recursive Functions	5.3–5.5
10	Combinatorics, counting, and enumeration	6
11	Midterm II
12	Recurrences and their solution	8.1–8.3
13	Relations	9
14	Grammars and Languages	13.1–13.4
15	Turing Machines	13.5

The following are major tests.

Due Date		Class Tests and Assignments	Weight
1 Oct.		Midterm I	25%
31 Oct.		Midterm II	25%
10 Dec.		Comprehensive Final Exam	30%

The following are homeworks.

Due Date		Class Tests and Assignments	Notes
6 Sep.		Homework I	Posted in canvas

Late work submission policy, absenteeism, etc.: Refer to the syllabus for details.

• Texas A&M University •