CSCE 222: Discrete Structures for Computing
Instructor: Dr. Dylan Shell.
Office | : | PETR 315 |
Phone | : | (979) 845-2369 |
: | 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. |
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:
|
The grading scale is:
|
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.
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 | | ||
8 | Guest lecture | ||
9 | Recursive Functions | 5.3–5.5 | |
10 | Combinatorics, counting, and enumeration | 6 | |
11 | | ||
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.