JCU Logo
JOHN CABOT UNIVERSITY

COURSE CODE: "CS 200"
COURSE NAME: "Elements of Formal Reasoning and Computation"
SEMESTER & YEAR: Spring 2023
SYLLABUS

INSTRUCTOR: Patrizio Angelini
EMAIL: [email protected]
 HOURS: MW 11:30-12:45 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: Office hours: regular on Tuesday, 11:30-12:30. Available in other time slots 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 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 have improved their ability to formulate and understand a structured reasoning, according to logical conjunctions and implications,

- 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 these problems,

- will have developed basic skills to provide algorithmic solutions for these problems, to analyze them in terms of their correctness, and to evaluate their efficiency.
TEXTBOOK:
Book TitleAuthorPublisherISBN numberLibrary Call NumberCommentsFormatLocal BookstoreOnline Purchase
Discrete Mathematics with ApplicationsThomas Koshy Elsevier Science & Technologyprint:9780124211803, ebook:9780080477343.  Ebook  
REQUIRED RESERVED READING:
NONE

RECOMMENDED RESERVED READING:
NONE
GRADING POLICY
-ASSESSMENT METHODS:
AssignmentGuidelinesWeight
Assignments2 home-assignments and 1 midterm evaluation. Assignments will be evaluated on the quality of the submitted solutions and on a subsequent discussion in class30
Paper discussionA theorem from a research paper on one of the studied topics will be assigned to each student and discussed in class.20
Final examVerification of the knowledge acquired by the student in the course40
Participation and attendanceAttendance and participation are fundamental, due to the creative and theoretical nature of the topics10

-ASSESSMENT CRITERIA:
AWork of this quality directly addresses the question or problem raised and provides a coherent argument displaying an extensive knowledge of relevant information or content. This type of work demonstrates the ability to critically evaluate concepts and theory and has an element of novelty and originality. There is clear evidence of a significant amount of reading 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 evaluatetheory and concepts and relate them to practice. Discussions reflect the student’s own arguments and are not simply a repetition of standard lecture andreference material. The work does not suffer from any major errors or omissions and provides evidence of reading 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 reference readings.
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. 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.

Examination policy

A major exam (midterm or final) cannot be made up without the permission of the Dean’s Office. The Dean’s Office will grant such permission only when the absence was caused by a serious impediment, such as a documented illness, hospitalization or death in the immediate family (in which you must attend the funeral) or other situations of similar gravity. Absences due to other meaningful conflicts, such as job interviews, family celebrations, travel difficulties, student misunderstandings or personal convenience, will not be excused. Students who will be absent from a major exam must notify the Dean’s Office prior to that exam. 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

Week 1

The role of Math in Computer Science

Logic: Truth tables

Week 2

Logic: Equivalence, Implications, Paradoxes

Week 3

Proof by deduction and contradiction

Assignment 1

Week 4

Introduction to Number Theory

Representing numbers in computers

Week 5

Combinatorics: Permutations, sequences, series

Week 6

Set theory and pigeonhole principle

 

Week 7

Proof by induction

Mid-term

Week 8

Graphs and combinatorics

Week 19

Induction on graphs

Assignment 2

Week 10

Principles of algorithm analysis

Week 11

Searching and sorting

Week 12

Recurrences

Week 13

Research paper discussion

Discussion

Week 14

Research paper discussion and final considerations

Discussion