CISC-1100-C01
is CRN (course reference number) 42250,
for 3 credits.
The home page for this course is
https://markmeretzky.com/fordham/1100/
None.
This course surveys the branches of Discrete Mathematics used in Computer Science:
Now what do these topics have in common? Discrete Math is the Math that can be pictured by drawing dots, possibly enclosed in circles or rectangles, and possibly connected with straight lines or arrows. Discrete Math thus includes subjects like Set Theory and Graph Theory (including, for example, tree structures and the algorithms that traverse them). On the other hand, Discrete Math excludes continuous curves, derivatives, and Trigonometry and Calculus in general. A typical Discrete Math question would have an answer that is a whole number (“how many?” or “which one?” or “in what order?”) rather than a number with a fraction (“how much?”).
This course fulfills the Mathematical/Computational Reasoning requirement of the Core Curriculum.
Mark Meretzky
has no office or office hours.
But you can Zoom him, or email him at
mmeretzky@fordham.edu.
Please contact him when you need help;
he wants to hear your story.
If the students desire,
the instructor can arrive on the Lincoln Center campus an hour before class
to offer individual help.
We’ll talk about this once the course begins.
According to the Lincoln Center calendar, we meet on 14 Monday evenings and 1 Tuesday evening:
2025
January February March
Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa
1 2 3 4 1 1
5 6 7 8 9 10 11 2 3 4 5 6 7 8 2 3 4 5 6 7 8
12 13 14 15 16 17 18 9 10 11 12 13 14 15 9 10 11 12 13 14 15
19 20 21 22 23 24 25 16 17 18 19 20 21 22 16 17 18 19 20 21 22
26 27 28 29 30 31 23 24 25 26 27 28 23 24 25 26 27 28 29
30 31
April May June
Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa
1 2 3 4 5 1 2 3 1 2 3 4 5 6 7
6 7 8 9 10 11 12 4 5 6 7 8 9 10 8 9 10 11 12 13 14
13 14 15 16 17 18 19 11 12 13 14 15 16 17 15 16 17 18 19 20 21
20 21 22 23 24 25 26 18 19 20 21 22 23 24 22 23 24 25 26 27 28
27 28 29 30 25 26 27 28 29 30 31 29 30
CISC-1100-C01 meets from 6:00 to 8:45 pm, with a 10-minute intermission exactly in the middle (7:17 to 7:27 pm).
Room 602 in the Leon Lowenstein Center at the Lincoln Center Campus of Fordham. Take the A, B, C, D, or 1 subway to Columbus Circle and walk one block west towards the Hudson River. Enter the campus at the northwest corner of Columbus Avenue and West 60th Street.
Fundamentals of Discrete Structures, 2nd edition by Damian M. Lyons, Christina Papadakis-Kanaris, Gary M. Weiss, Arthur G. Werschulz. ISBN 978-1256389217.
The midterm examination will be on Monday, March 10, 2025, because that’s the middle of the course. The final examination will be on Monday, May 12, 2025, because that date is during Finals Week. These two examinations will be answered on paper, because the University wants to see a written record.
Most of the homework assignments will be exercises from the textbook. Hand them in on paper on the Monday after they’re assigned. Assume that the homework will take about three hours per week.
If the student has done their own homework reasonably successfully all semester, they will have no trouble with the midterm or final: it will just be more of the same. But if the student has plagiarized their homework all semester, or has been massively late or absent, they will fail the midterm and final. That’s obvious, isn’t it? Read the Fordham policy on lateness, absences and plagiarism.
Your grade CISC-1100-C01 will be taken
50% from the homeworks
25% from the midterm exam
25% from the final exam
In practice,
a student’s grade for the homeworks and the grade for the final exam
will almost always be very similar.
If you’ve been doing your work all semester,
it will show on the final.
“Academic integrity is the pursuit of scholarly activity in an honest, truthful and responsible manner. Fordham students are expected to accept the responsibility to be honest and to respect ethical standards in completing their academic assignments, assessments, and other requirements. Students are expected to adhere to academic integrity by completing all assignments and other requirements on their own without assistance from external resources (including any artificial intelligence or machine-learning tools) unless directly authorized by the instructor. It is the student’s responsibility to give credit to any quotation, idea, or data used from an outside source. Students who fail to meet the responsibility for academic integrity subject themselves to sanctions ranging from a reduction in grade, course failure in the assignment, or expulsion from the University.”
Some members of the Fordham community are known by a name
other than their legal name.
Students who wish to be identified by a chosen name can
email the instructor at
mmeretzky@fordham.edu
to request that their chosen name and pronoun be used.
Here are links to the
Fordham Emergency
Medical Services
Fordham Counseling and Psychological Services
Fordham
Office of Disability Services
We have 14 × 2.75 = 38.5 classroom hours to explore the following topics, in the following order.
All branches of Mathematics study objects that are defined using Set Theory. For example, the object in the following chapters are just fancy sets. For this reason, we start the course with the foundational definitions and operations of Set Theory.
A set is a thing that doesn’t do anything except contain other things. From this parsimonious beginning, we will construct functions, graphs, and all the rest of Mathematics.
Here is a classic example of a problem involving the sum of a sequence of numbers:
How much is 1 + 2 + 3 + … + 98 + 99 + 100?
The above sequence contained only 100 numbers. We will also see sequences that contain an infinite number of numbers.
A proposition is a statement; it can be either true or false. (See Abraham Lincoln’s Gettysburg Address.) We can combine propositions to produce conclusions similarly to how we combine numbers to produce sums and products. The classic example is Aristotle’s syllogism:
Instead of using arithetic operators such as addition and multiplication
to combine numbers,
we will use
logical operators
such as “and” and “or”
to combine propositions.
For example, analogously to
a × (b + c)
=
(a × b) +
(a × c)
(where a, b, c are numbers)
we will write
P and (Q or R)
=
(P and Q) or
(P and R)
(where P, Q, R are propositions)
Let’s start with the relation of “equals” and some
numbers.
If a = b and b = c
then I’m sure we can all agree that
a = c.
Ditto for the relation of “less than”:
If a < b and b < c
then
a < c.
But if a is fairly close to b,
and b is fairly close to c,
can we conclude that a must be fairly close to c?
Not all relations work the same way. And not all relations are relationships betwen a pair of numbers, such as the ones in the above example. There are also relations between a pair of sets, or a pair of functions (see below), or a pair of relations.
Let’s say that every boy has a girl. Does this mean that every girl has a boy? (In mathematical language, is the function surjective?) On the other hand, could there be a girl who has more than one boy? (In mathematical language, is the function injective?)
A function is the sort of thing that matches up each boy with a girl. Picture the function as a set of arrows, each one pointing from a boy to his girl. The set of boys is the domain of this function, and the set of girls is the range of this function. These are some of the definitions we will introduce in this chapter. (As you see, functions [and in fact all of Mathematics] can be defined in terms of sets.)
In other branches of Mathematics, we study functions whose domain and range are sets of numbers. In Discrete Math, we study functions whose domain and range are sets of other objects, maybe even sets of functions, or sets of sets.
In how many different orders could we arrange a set of three objects?
Could you answer the same question for a set of four objects, without actually listing all the orders?
Another example. We have a committee of 10 people. How many different subcommittees could we appoint? Note that a subcommittee might consist of only a single person (“a committee of one”), or might consist of everybody (“a committee of the whole”). Could you attack this problem by breaking it down into a series of smaller problems?
A graph is a diagram made of dots connected by lines or arrows. The dots are cities. The lines represent two-way roads, and the arrows represent one-way roads.
Suppose you wanted to travel from the New York dot to the San Francisco dot, and there were many possible paths. How could you find the path that visits the fewest possible cities along the way? Or suppose you wanted to visit every city in the country exactly once, without visiting the same city twice. How could you design such a tour, assuming you have no helicopter?
A different kind of problem assumes that there are no roads yet, only cities. You are given a table showing the distance between each pair of cities, and must design a network of highways that will make it possible to drive from any city to any city, although not necesarily directly. What would be the cheapest (i.e., lowest mileage) spanning tree of highways that would accomplish this?
These are some of the problems we study in graph theory. The network doesn’t have to be a map of cities; it could be an electrical circuit, or a person’s circulatory system.