Course Syllabus

JOHN CABOT UNIVERSITY

COURSE CODE: "CS 200"
COURSE NAME: "Discrete Structures"
SEMESTER & YEAR: Spring 2026

SYLLABUS

INSTRUCTOR: Henry Foerster
EMAIL: [email protected]
HOURS: MW 3:00 PM 4:15 PM
TOTAL NO. OF CONTACT HOURS: 45
CREDITS: 3
PREREQUISITES: Prerequisites: Placement into MA 197 or completion of MA 100 or MA 101
OFFICE HOURS: by appointment

COURSE DESCRIPTION:
This course introduces the main elements of formal reasoning and its applications to the theory of computation. Starting from the definition of logic statements and elementary structures in discrete mathematics, such as numbers, sets, and graphs, the course discusses the formalization of real-life problems in mathematical and computer science terms.

Mathematical tools will be introduced to infer the validity of complex statements starting from elementary ones and different techniques for deriving formal proofs of theorems will be analyzed. Examples of algorithmic solutions to real-life problems exploiting their formalization will also be presented and discussed, both in terms of correctness and efficiency.

SUMMARY OF COURSE CONTENT:

The course will first introduce some notation and tools in the field of formal logic and deductive reasoning, such as truth tables, logic conjunctions, and implications. Then, it will explore how these tools can be exploited to establish the validity of certain statements and facts, discussing the proof techniques based on induction, on deduction and on contradiction.

The next goal will be to discuss certain structures in discrete mathematics that are heavily used in computer science and to study their combinatorial properties. This includes integer numbers, with their binary representation in a computer, permutations, sequences, and series, together with elements of set theory and of graph theory. Using these structures as training fields for various examples, another powerful proof technique, based on mathematical induction, will be introduced.

Finally, the course will overview some state-of-the-art algorithmic solutions for fundamental computer science problems, such as searching and sorting, and use the techniques learned in the course to formally prove their correctness. To further establish the efficiency of these solutions, basic principles of computational complexity will be presented, including recurrences, counting arguments, and asymptotic notation.

To provide students with a direct research experience, each of them will be assigned a theorem from a research paper, whose statement and proof will be presented and discussed in class.

LEARNING OUTCOMES:

Upon successful completion of this course, the student:

- will be able to formulate and understand a structured reasoning, according to logical conjunctions and implications,

- will be familiar with the use of logic and binary arithmetic in the functioning of computer machines,

- will be familiar with the main concepts and notions in discrete mathematics,

- will be able to formalize a real-life problem in mathematics and computer science terms,

- will be acquainted with various techniques to formally prove combinatorial and structural properties of the instances of different problems,

- will have developed basic skills to provide algorithmic solutions for problems occurring when handling discrete data and to analyze algorithmic solutions in terms of their correctness and efficiency.

TEXTBOOK:

NONE

REQUIRED RESERVED READING:

NONE

RECOMMENDED RESERVED READING:

Book Title	Author	Publisher	ISBN number	Library Call Number	Comments
Discrete Mathematics and Its Applications	Kenneth H. Rosen	McGraw Hill	978-1259676512
Discrete Mathematics with Applications	Thomas Koshy	Elsevier	0-12-421180-1

GRADING POLICY
-ASSESSMENT METHODS:

Assignment	Guidelines	Weight
Home Assignments	2 home-assignments. Assignments will be evaluated on the quality of the submitted solutions and on a subsequent discussion in class	20
In-Class Assignments	Two in-class assignments focused on specific topics.	30
Final Exam	Verification of the knowledge acquired by the student in the course	40
Participation and Attendance	Attendance and participation are fundamental, due to the creative and theoretical nature of the topics	10

-ASSESSMENT CRITERIA:
AWork of this quality directly addresses the questions or problems raised. Answers to questions are provided using coherent argumentation displaying an extensive knowledge of relevant information or content and practice in applying formal techniques covered in the class. This type of work demonstrates the ability to critically evaluate concepts and theory and solutions to questions and problems involve novel and original ideas. There is clear evidence of a significant study of the material beyond that required for the course.
BThis is highly competent level of performance and directly addresses the question or problem raised. There is a demonstration of some ability to critically evaluate theory and concepts and relate them to practice. Solutions for questions and problems reflect the student’s own arguments and are not simply a repetition of standard lecture and reference material. The work does not suffer from any major errors or omissions and provides evidence of study beyond the required assignments.
CThis is an acceptable level of performance and provides answers that are clear but limited, reflecting the information offered in the lectures and standard reference material.
DThis level of performances demonstrates that the student lacks a coherent grasp of the material. Important information is omitted and irrelevant points included. In effect, the student has barely done enough to persuade the instructor that s/he should not fail.
FThis work fails to show any knowledge or understanding of the issues raised in the question or problem. Most of the material in the answer is irrelevant.

-ATTENDANCE REQUIREMENTS:

ATTENDANCE REQUIREMENTS AND EXAMINATION POLICY

Attendance is to be considered mandatory and will be part of the final grade. Students will be granted 3 absences without penalty. Any other absences will only be excused with permission from the Dean's Office. Otherwise, they will affect the portion of the grade determined by attendance and participation.

You cannot make-up a major assessment without the permission of the Dean’s Office. Students who will be absent from a major assessment must notify the Dean’s Office prior to that assessment. Absences from class due to the observance of a religious holiday will normally be excused. Individual students who will have to miss class to observe a religious holiday should notify the instructor by the end of the Add/Drop period to make prior arrangements for making up any work that will be missed.

ACADEMIC HONESTY
As stated in the university catalog, any student who commits an act of academic dishonesty will receive a failing grade on the work in which the dishonesty occurred. In addition, acts of academic dishonesty, irrespective of the weight of the assignment, may result in the student receiving a failing grade in the course. Instances of academic dishonesty will be reported to the Dean of Academic Affairs. A student who is reported twice for academic dishonesty is subject to summary dismissal from the University. In such a case, the Academic Council will then make a recommendation to the President, who will make the final decision.

STUDENTS WITH LEARNING OR OTHER DISABILITIES
John Cabot University does not discriminate on the basis of disability or handicap. Students with approved accommodations must inform their professors at the beginning of the term. Please see the website for the complete policy.

SCHEDULE