COLLEGE OF ARTS AND SCIENCES

Department of Mathematics and Physics

§ I: MATH 1166 Discrete Mathematics for Computing

Syllabus

Catalog Description

Prerequisite: MATH 1108, CSCI 1110. A foundation course for computer science majors. Introduction to

fundamentals, including logic, sequences, sets, functions, recursion, induction, proof methods, counting tech-

niques, and Big-O notation. 3 credits. (This course is cross listed with CSCI 1166).

Required Textbook

Discrete Mathematics with Applications, Susanna S. Epp, Brooks-Cole, 4e, ISBN 9780495391326 (2011).

Course Objectives

The course, MATH 1166, provides an introduction to the basic structure of mathematics, emphasizing founda-

tional topics involving logic and proof; induction and recursion; combinatorics; and algorithmic development.

The emphasis is on connecting mathematical concepts with practical computer based applications that can

be applied to understanding problems that arise in computing theory. Underlying all of this is the need to

develop a strong foundation in symbolic reasoning which allows for a rigorous development of the mathe-

matical ideas that motivate the analysis of discrete structures. This culminates in a fuller understanding of

algorithms and their analysis.

The material is presented in a manner which ties theory with mathematical development, emphasizing

the need for precision in reasoning, and for developing an understanding of the sources of error in reasoning

(fallacies). The course emphasizes topics in computing and the curriculum is designed to provide the student

with an understanding of how to think and reason eﬀectively in a computing environment.

Student Learning Outcomes

After successfully completing this course the expectation is that students will be able to:

1. Work with symbolic logic and Boolean algebra;

2. Write elementary proofs, with rigor, conciseness and speciﬁcity. Recognizing fallacies and incorrect lines

of reasoning;

3. Explain the role of recursion in reasoning, proof, and computing;

4. Explain concepts in set theory and functions, and apply these to problems in computing and to com-

putability;

5. Enumerate set and using counting arguments; and,

6. Analyze algorithm design in terms of issues aﬀecting algorithmic eﬃciency and computability.

Required Curriculum Content

Key topics covered include:

1. Logical Forms: Emphasizing the foundations of determining the truth of a statement, including identify-

ing forms, statements, using logical connectives developing and using symbolic notation, logical equiv-

alence. Conditional Statements: Understanding the negation, converse, inverse and contrapositive,

biconditional statements and necessary and suﬃcient conditions.

2. Universal, conditional and existential statements. Understanding the logic of quantiﬁed statements,

including conditional statements containing the symbolic forms ∀, ∃, ∃!, ∧, ∨, and ∼, and manipulating

these forms.

1

3. Direct methods of proof and the development of counterexamples. These are applied using elementary

number theory.

4. Mathematical induction and sequences including development of techniques for dealing with summa-

tions and factorials. This introduces strong mathematical induction and the Principle of Well-Ordering.

5. Basic set theory, including properties of sets, unions, intersections, DeMorgan’s Laws, empty sets and

power sets.

6. Counting and probability. Trees and the multiplication rule, and counting disjoint sets and subsets.

7. Functions, including functions deﬁned on general sets, and injective, surjective and bijective mappings.

The composition of functions.

8. Relations on sets, including reﬂexivity, symmetry, and transitivity. Equivalence relations and partitions.

9. Counting arguments. The pigeonhole principle. Analysis of algorithms and algorithmic eﬃciency, includ-

ing big-O notation, and other comparative scales.

All sections of MATH 1166 Discrete Mathematics for Computing will cover, as a minimum, the material from

Discrete Mathematics with Applications, Susanna S. Epp, Brooks-Cole, 4e, ISBN 9780495391326 (2011), as listed:

Sec Textbook Topic

Chapter 1 – Speaking Mathematically

1.1 Variables

1.2 The Language of Sets

1.3 The Language of Relations and Functions

Chapter 2 – The Logic of Compound Statements

2.1 Logical Form and Logical Equivalence

2.2 Conditional Statements

2.3 Valid and Invalid Arguments

2.4 Applications: Digital Logic Circuits

Chapter 3 – The Logic of Quantiﬁed Statements

3.1 Predicates and Quantiﬁed Statements I

3.2 Predicates and Quantiﬁed Statements II

Chapter 4 – Elementary Number Theory and Methods of Proof

4.1 Direct Proof and Counterexample I: Introduction

4.2 Direct Proof and Counterexample II: Rational Numbers

4.3 Direct Proof and Counterexample III: Divisibility

4.4 Direct Proof and Counterexample IV: Division into Cases; Quotient-Remainder Theorem

4.5 Direct Proof and Counterexample V: Floor and Ceiling

4.6 Indirect Argument: Contradiction and Contraption

4.7 Indirect Argument: Two Classical Theorems

4.8 Application: Algorithms

Chapter 5 – Sequences, Mathematical Induction and Recursion

5.1 Sequences

5.2 Mathematical Induction I

5.3 Mathematical Induction II

5.4 Strong Mathematical Induction and the Well-Ordering Principle for the Integers

5.5 Application: Correctness of Algorithms

5.6 Deﬁning Sequences Recursively

Chapter 6 – Set Theory

6.1 Set Theory: Deﬁnitions and the Element Method of Proof

6.2 Properties of Sets

6.3 Disproofs, Algebraic Proofs, and Boolean Algebra

6.4 Boolean Algebras

Department Syllabus for MATH 1166, Spring 2019 Page 2 of 7 Rev. 1.0, January 28, 2019

Sec Textbook Topic

Chapter 7 – Functions

7.1 Functions Deﬁned on General Sets

7.2 One-to-one and Onto, Inverse Functions

7.3 Composition of Functions

7.4 Cardinality with Applications to Computability

Chapter 8 – Relations

8.1 Relations on Sets

8.2 Reﬂexivity, Symmetry, and Transitivity

8.3 Equivalence Relations

Chapter 9 – Counting and Probability

9.1 Introduction

9.2 Possibility Trees and the Multiplication Rule

9.3 Counting Elements of Disjoint Sets: The Addition Rule

9.4 The Pigeonhole Principle

9.7 Pascal’s Formula and the Binomial Theorem

Chapter 11 – Analyzing Algorithm Eﬃciency

11.1 Real-Valued Function of a Real Variable and their Graphs

11.2 Big O and Little Notations

Common Department Requirements for MATH 1166

While students in each section of MATH 1166 are assessed by the course instructor, there are general guide-

lines that apply to all sections of MATH 1166. These include:

• Calculators and other electronic devices are not allowed on any exams.

Department Syllabus for MATH 1166, Spring 2019 Page 3 of 7 Rev. 1.0, January 28, 2019

Department, College and University Expectations and Policies

It is important that students familiarize themselves with a range of policies and guidelines that have been es-

tablished by the Department of Mathematics and Physics, the College of Arts and Sciences, and the University

of New Haven. These are an integral part of the syllabus for this course.

Adding/Dropping a Class

The ﬁnal day to drop this course without it appearing on your transcript is discussed on the

Academic Schedules and Registration web page. After the ﬁrst week of class, self-service registration will

not be enabled for students to directly add or drop classes. Students should contact the Registrar’s oﬃce

directly or the Academic Success Center for assistance with adding and dropping courses during this time.

Attendance Regulations

University attendance policy guidelines require that:

Students are expected to attend regularly and promptly all their classes, appointments, and exercises. While the

university recognizes that some absences may occasionally be necessary, these should be held to a minimum.

A maximum of two weeks of absences will be permitted for illness and emergencies. The instructor has the

right to dismiss from class any student who has been absent more than the maximum allowed. A dismissed

student will receive a withdrawal (W) from the course if they are still eligible for a withdrawal per the university

Withdrawal from a Course policy, or a failure (F), if not. A student who is not oﬃcially registered in the course

is not permitted to attend classes or take part in any other course activities. Students absent from any class

meeting are responsible for making up missed assignments and examinations at the discretion of the instructor.

Students are to adhere to the policy attendance policy guidelines outlined in the University Catalog under the

heading, Attendance Regulations, found online in the Undergradaduate Catalog or alternatively found in the

Student Handbook on pp.4849.

Religious Observance Policy for Students

The University of New Haven respects the right of its students to observe religious holidays that may neces-

sitate their absence from class or from other required university-sponsored activities. Students who wish

to observe such holidays should not be penalized for their absence, although in academic courses they are

responsible for making up missed work. The College provides that,

Instructors should try to avoid scheduling exams or quizzes on religious holidays, but where such conﬂicts occur

should provide reasonable accommodations for missed assignment deadlines or exams. If a class, an assign-

ment due date, or exam interferes with the observance of such a religious holiday, it is the student’s responsibil-

ity to notify their instructor, preferably at the beginning of the term, but otherwise at least two weeks before the

holiday.

More information about religious observance policies can be found in the Student Handbook on pp.4849

under the heading, Attendance Policies: Religious Observance Policy for Students.

Withdrawal from a Course

Students wishing to withdraw must submit a request for an oﬃcial course withdrawal in writing using the on-

line Course Withdrawal Form, or alternatively complete and hand in the pdf based Course Withdrawal Form.

The ﬁnal date to request a withdrawal is listed in the Academic Calendar. This request must be submitted to

the Registrar’s Oﬃce and signed by the International Oﬃce if you are an international student. The grade of

W will be recorded, but the course will not aﬀect the GPA.

1

Incomplete Grade Policy

A grade of Incomplete (INC) is given only in special circumstances and indicates that the student has been

given permission by the instructor to complete required course work (with the same instructor) after the end

1

Please note that it is the responsibility of the student to assure that the required paperwork and documentation is completed by the deadline.

Department Syllabus for MATH 1166, Spring 2019 Page 4 of 7 Rev. 1.0, January 28, 2019

of the term. In the absence of the instructor a student should contact the Department Chair. Students need

to examine carefully the changed guidelines pertaining to INC grades, speciﬁcally:

To remove the INC grade, the student must complete all required course work in timely fashion as stipulated by

the instructor but no later than the end of the following term. Fall and intersession course incomplete grades

must be completed no later than the last day of the spring term. Spring and summer course incomplete grades

must be completed no later than the last day of the fall term.

If the course work is not submitted within the allotted time, the INC grade will be changed to an F shortly after

the deadline by the Oﬃce of the University Registrar. Students will be notiﬁed via campus email at least two

weeks prior to the change of grade process.

The University policy on incomplete grades is discussed in the Academic Catalog under the heading, Incom-

plete (INC) Grade Policy.

Academic Integrity Policy and Procedures

The University of New Haven expects its students to maintain the highest standards of academic conduct.

Academic dishonesty is not tolerated at the University. To know what it is expected, students are responsible

for reading and understanding the statement regarding academic honesty in the Student Handbook. Specif-

ically, students are required to adhere to the Academic Integrity Policies speciﬁed in the Student Handbook,

i.e., on pp.6673.

Please ask your instructor about their expectations regarding permissible or encouraged forms of student

collaboration if there is any confusion about this topic. The Department of Mathematics and Physics fully

adheres to the Academic Integrity Policy:

Academic integrity is a core university value that ensures respect for the academic reputation of the University,

its students, faculty and staﬀ, and the degrees it confers. The University expects that students will conduct

themselves in an honest and ethical manner and respect the intellectual work of others. Please be familiar with

the University’s policy on Academic Integrity. Please ask about expectations regarding permissible or encouraged

forms of student collaboration if they are unclear.

Coursework Expectations

This course will require signiﬁcant in-class and out-of-class commitment from each student. The University

estimates that a student should expect to spend two hours outside of class for each hour they are in a

class. For example, a three credit course would average six [6] hours of additional work outside of class.

2

Coursework expectations are detailed in the Academic Catalog under the heading, Course Work Expectations.

Please note, that MATH 1166 is a 3-credit course, and as such requires a total of 9 hours per week invested

in study and homework for the average student.

Commitment to Positive Learning Environment

The University adheres to the philosophy that all community members should enjoy an environment free of

any form of harassment, sexual misconduct, discrimination, or intimate partner violence. If you have been

the victim of sexual misconduct we encourage you to report this. If you report this to a faculty/staﬀ member,

they must notify our college’s Title IX coordinator about the basic facts of the incident (you may choose to

request conﬁdentiality from the University). If you encounter sexual harassment, sexual misconduct, sexual

assault, or discrimination based on race, color, religion, age, national origin, ancestry, sex, sexual orientation,

gender identity, or disability please contact the Title IX Coordinator, Caroline Koziatek at (203)-932-7479 or

CKoziatek@newhaven.edu. Further online information about is available at Title IX.

Reporting Bias Incidents

At the University of New Haven, there is an expectation that all community members are committed to cre-

ating and supporting a climate which promotes civility, mutual respect, and open-mindedness. There also

exists an understanding that with the freedom of expression comes the responsibility to support community

2

Please note that study guidelines are important, i.e., there is substantial evidence that shows that the pass rates for students in math courses decrease

dramatically as the time spent on outside study falls below 2 hours of homework per credit per week.

Department Syllabus for MATH 1166, Spring 2019 Page 5 of 7 Rev. 1.0, January 28, 2019

members’ right to live and work in an environment free from harassment and fear. It is expected that all mem-

bers of the University community will engage in anti-bias behavior and refrain from actions that intimidate,

humiliate, or demean persons or groups or that undermine their security or self-esteem.

If you have witnessed or are the target of a bias-motivated incident, please contact the Oﬃce of the Dean

of Students at 203-932-7432 or Campus Police at 203-932-7014. Further information about this and other

reporting options may be found at Report It.

University Support Services

The University recognizes students often can use some help outside of class and oﬀers academic assistance

through several oﬃces. In addition to discussing any academic issues you may have with your instructor,

advisor, or with the the courses or department coordinator or chair, the University provides these additional

resources for students:

The Center for Academic Success and Advising (CASA)

The Academic Success Center is located in Maxcy 208 for help with your academic studies, or call 203-932-

7234 to set up an appointment.

University Writing Center

The mission of the Writing Center (an expansion of the Writer to Writer peer-tutoring program) is to provide

high-quality tutoring to undergraduate and graduate students as they write for a wide range of purposes and

audiences. Tutors are undergraduate and graduate students and they work with students at any stage in the

writing process; Bring in your assignment, your ideas, and any writing done so far. To make an appointment,

register for an account at https://newhaven.mywconline.com.

The Math Zone

Please contact the Math Zone if you wish to challenge your Math Placement by taking a Math Challenge Exam

or by taking a Math Post Placement Exam. These are discussed more extensively at http://math.newhaven.

edu/mathphysics/placement_html. The Math Zone also provides a range of tutoring and classroom support

service for students taking development math classes.

The Center for Learning Resources (CLR)

The Center for Learning Resources located in Peterson Library, provides academic content support to the

students of the University of New Haven using metacognitive strategies that help students become aware

of and learn to apply optimal learning processes in the pursuit of creating independent learners CLR tutors

focus sessions on discussions of concepts and processes and typically use external examples to help students

grasp and apply the material.

Accessibility Resources Center

Students with disabilities are encouraged to share, in conﬁdence, information about needed speciﬁc course

accommodations. The Accessibility Resources Center (ARC) provides comprehensive services and sup-

port that serve to promote educational equity and ensure that students are able to participate in the oppor-

tunities available at the University of New Haven. Accommodations cannot be made without written docu-

mentation from the ARC. The ARC is located on the ground ﬂoor in the rear of Sheﬃeld Hall. Sheﬃeld Hall

is located in the Residential Quad area, and can be contacted at 203-932-7332. The ADA/Section 504 Com-

pliance Oﬃcer is Rebecca Johnson, RJohnson@newhaven.edu, and can be reached by phone at 203-932-7238.

Information on the ARC can be found at

Department Syllabus for MATH 1166, Spring 2019 Page 6 of 7 Rev. 1.0, January 28, 2019

Counseling and Psychological Services

The Counseling Center oﬀers a variety of services aimed at helping students resolve personal diﬃculties and

acquire the balance, skills, and knowledge that will enable them to take full advantage of their experience at

the University of New Haven. Information about the, Counseling and Psychological Services, is available

online.

Department Syllabus for MATH 1166, Spring 2019 Page 7 of 7 Rev. 1.0, January 28, 2019