Introduction to Discrete
Structures I
Spring 2015
(CS 205)
Course Info
Instructor: Swastik
Kopparty (swastik.kopparty@gmail.com
: please include “CS205” in the subject
of your email)
Class Time and Place: Tuesdays
and Fridays, 8:40am - 10:00am, in SEC-118 (Busch Campus).
Office Hours: Wednesday 1:30pm –
2:30pm (Hill 432)
Prerequisites: CS 111, Math 152
Text book: Discrete Mathematics and its Applications, 7th
edition, by Kenneth Rosen.
There is a custom edition of this book for Rutgers (including
only the chapters we will cover)
available in the RU bookstore at a reduced price! (ISBN
1259152154).
Either
the full book, or the custom edition, will be okay for this class.
TAs: Abhishek Bhrushundi
( abhishek.bhr@cs.rutgers.edu
)
Office
Hours: Friday 1pm – 3pm (Hill 357)
John
Wiedenhoeft ( john.wiedenhoeft@cs.rutgers.edu
)
Office
Hours: Tuesday 2:30pm – 4:30pm (Hill 270)
Recitations:
Rec
1 Tuesday 10:35-11:30 ARC 206
Rec
2 Friday 10:35-11:30 SEC 212
Rec
4 Tuesday 12:15-1:10 TIL 207 (Livingston Campus)
Syllabus
This course is an introduction to
discrete mathematics for computer science.
The most important thing we will
learn is logic: how to make clear, precise statements, how to reason about
truth and falsehood of statements, how to recognize valid proofs and catch
invalid proofs, and also, techniques to come up with your own proofs.
We will then use this to study
some of the most basic objects that are useful throughout computer science:
sets, functions, relations, numbers and finite state machines.
Finally, we will see some neat
applications to modern topics like cryptography, circuit design, artificial
intelligence, and language.
|
Grading There will be
homework every 1-2 weeks. There will be a
quiz on the due date of each homework, covering the
material of the homework. There will be a
midterm and a final exam. The lowest
homework grade will be dropped. The lowest two
quiz grades will be dropped. Weightage: HW: 20%, quizzes:
20%, midterm: 20%, final: 40%, class participation: up to 10% bonus. |
Other class
policy No laptops,
tablets, phones, smartwatches etc. can be used
during class. You can discuss
homework problems with classmates, but the solutions You must list all
the people with whom you worked on the homework problems. You are not
allowed to use internet sources for the homework problems. There is zero
tolerance for cheating. On each day a homework is due, there will be a quiz at the beginning
of class. The homework and
quiz will then be collected together. Late homework
will not be accepted without a note from the dean. There will be no
makeup quizzes. |
Sakai Website
There is a sakai website for this course.
Please make sure you can access
this!
You can see your scores on the homeworks so far on the sakai website.
There is also a forum on the sakai website where you can ask
questions about the material, and answer questions asked by your fellow
students.
The TAs and the instructor will
answer questions on this forum once every 3-4 days.
For technical questions, please
use the forum and do not email the TAs or instructors.
You can also use the sakai website to ask your
classmates about what happened in a given class, in case you missed it.
Homework
·
HW1
(Due Jan 27
Jan 30, because of snowstorm. Quiz 1 also postponed to Jan 30.)
Sec 1.1: 12 (a,b,f), 14, 18, 28, 32
Sec 1.2: 2, 4
Sec 1.3: 8, 10
·
HW2
(Due Feb 10)
Sec 1.3: 22, 26
a)
Use
a truth table to show that 
is
a tautology.
b)
What
is the negation of the statement: if Jack goes up the hill, then Jill does not
go up the hill.
c)
Write
this statement formally using quantifiers and predicates: Every student in
CS205 likes both Pepsi and Coke.
Then write its negation formally using quantifiers and predicates.
d)
Write
this statement formally using quantifiers and predicates: Every student in
CS205 who likes Pepsi also likes Coke.
Then write its negation formally using quantifiers and predicates.
e)
Let
the universe of discourse be the integers ( …, -2, -1,
0, 1, 2, …). Are the following propositions true or false?
i.
ii.
·
HW3
(Due Feb 17)
a)
Let
the universe of discourse be students in CS205.
Let T(a, b) be the predicate “a and b are friends”.
Write the following sentences formally using quantifiers. Then use DeMorgan’s laws to find their negations.
i.
Everyone
has a friend.
ii.
There
is someone who is friends with everyone else.
iii.
Everyone
has at least two friends.
iv.
Every
two students have a common friend.
v.
There
are three students who are mutual friends.
vi.
Every
two friends have a common friend.
b)
If
I went to the library, then I borrowed a book. If I went to the store, then I
bought a banana. I went to either the library or the store. I did not buy a
banana.
Give an argument, clearly stating which rule of inference you use, which shows
that the above sentences lead
to the conclusion “I borrowed a book”.
c)
Everyone
in class took either Physics or Chemistry. Everyone who took Physics likes
Math. Someone in class does not like Math.
Give an argument, clearly stating which rule of inference you use, which shows
that the above sentences lead
to the conclusion “Someone in class took Chemistry”.
d)
Let
P(x) and Q(x) be predicates.
Let a be the proposition 
. Let b be the proposition
.
Give an argument,
clearly stating which rule of inference you use, to show that if a is
true, then b is true.
e)
Give
an argument, clearly stating which rules of inference you use, to show that if
are all true,
then 
is true.
Recommended (but do
not turn in): make sure you can do all the exercises at the end of section 1.7.
·
HW4
(Due Tuesday, March 3)
a)
We
are given 31 apples. Each of these apples is one of three kinds: Fuji, Gala,
and Honeycrisp.
Show that some 11 of these apples are all of the same kind. Hint: use a proof
by contradiction.
b)
Show
that for all integers n, if 
is
odd, then 
is
divisible by 4.
c)
Suppose
a, b, c, d, e are integers satisfying a + b + c + d + e = 16.
Show that 
).
d)
Show
that the following proposition is false: “the sum of any two irrational numbers
is irrational”.
e)
Show
that 
is irrational. You may use the fact that 
is
irrational.
f)
Let
and 
Find 
.
g)
Find
the power set of {1, 2, 4}.
h)
Find
the power set of { 1, 2, {1,2}}.
i)
In
each of the following parts, you have to give an example of a function f with
domain D = {a, b, c} and range R = {x, y, z} satisfying some conditions.
i.
f
is one-to-one
ii.
f
is not one-to-one
iii.
f
is onto
iv.
f
is not onto
v.
f
is both one-to-one and onto
vi.
f is not one-to-one and f is not onto.
j)
Find out where the Beck hall
auditorium is on Livingston campus. This is where your midterm will be on March
10.
- HW5 (Due Tuesday, March 10)
a)
There
are 131 students in CS 205. 100 like chocolate ice cream. 50 like vanilla ice
cream.
20 like both chocolate and vanilla ice cream. Draw a Venn diagram to represent
this. How many students
do not like either flavor of ice cream.
b)
There
are 131 students in CS 205. Everyone is either a CS major or CE major or Math
major (possibly more than one).
90 students major in CS only. 20 students major in CE only. 10 students major
in Math only. There are 6 students who major in CS and math (and possibly CE),
7 students who major in CS and CE (and possibly math), and 8 students who major
in CE and math (and possibly CS).
Draw a Venn diagram to represent this. Write the above statements in terms of
the sets S, E and M (the set of CS majors, CE Majors and
Math majors respectively). How many students are triple majors? How many CS
majors are there? How many Math majors are there? How many CE majors are there?
c)
There
are 131 students in CS2015. Let C be the set of students who like coffee. Let E
be the set of students who like espresso.
Let T be the set of students who like tea. Everyone who likes espresso also
likes coffee. Everyone who likes tea dislikes espresso.
50 students like espresso. 20 students like tea. 10 students like both tea and
coffee. 100 students like either tea or coffee.
Draw a Venn diagram to represent this. How many students dislike all three
drinks? How many students like coffee? How many students like coffee
only? How many students like tea only? How many students like two out of the
three drinks?
d)
Give
a bijection between the positive even integers and
the negative odd integers.
e)
Give
a bijection between the even natural numbers and the
set of perfect squares.
·
HW6
(Due Friday, April 3)
a)
Prove,
by induction, that the following formulas hold for all n:
i.
ii.
iii.
b)
Prove
that for all 
c)
Define
a sequence 
as follows:
Compute the next 3 elements of the
sequence. Guess a formula for 
, and then prove that it is correct using
induction.
d)
Prove,
by induction, that for every odd
natural number , the number is
divisible by 8.
e)
Prove,
by strong induction, that every positive integer can be expressed as a sum of distinct Fibonacci numbers.
Hint: given a positive integer k, let 
be
the largest Fibonacci number which satisfies 
. Try to express k as a sum of and other Fibonacci numbers.
f)
Show
that for every real number x 
-1, and every positive integer n:
g)
Highly
recommended, but do not turn in: do problems 3-8 from Section 5.1 of the text
book, and problems 1-4, 25, 27 of Section 5.2
·
HW7
(Due Tuesday, April 21)
a)
Determine
which of the properties (reflexive, symmetric, transitive, anti-symmetric,
equivalence) the following relations on the set of positive integers have:
a.
b.
c.
d.
e.
f.
g.
h.
i.
j.
b)
Suppose
P(n) is a predicate, and we are trying to prove the
statement 
by
induction.
First we prove the base case P(0).
Next we show: “Suppose for all 
, P(k) is true. Then for all k
, P(k+1) is
true.”
Does this imply that P(n) is true for all n 
? Why or why not?
c)
Suppose
R is a relation on the natural numbers which is reflexive, symmetric and
transitive. Suppose R has the property that for all k
we have that k R (k+1) (i.e., k and k+1
are related by R). Show that for all natural numbers m, n, mRn.
d)
Let
R be the relation on students in the class, given by R = { (a,b) s.t. a
and b have the same birthday}. Show that R is an equivalence relation.
e)
Let
R be the relation on students in the class, given by R= { (a,b) s.t. (a is at least as old as
b)}. Show that R is a partial order.
f)
Let
R be the relation on students in the class, given by R= { (a,b) s.t. (a is at least as old
as b) AND (a is at least as tall as b)}. Show that R is a partial order.
g)
Let
S be the set of all strings made out of the letters a-z. Let R be the relation
on S, given by
R = { 
s.t. 
is
a substring of 
}. Show that R is a partial order.
h)
Let
S be the set of all strings made out of the letters a-z. Let R be the relation
on S, given by
R = { s.t. is
the same as written backwards}. Which of the properties
reflexive, symmetric, transitive, antisymmetric, does R have?
i)
Let
S be the set of all strings made out of the letters a-z. Let R be the relation
on S, given by
R = { s.t. the length of equals the length of }. Show that R is an equivalence
relation.
j)
Write
the numbers 
in
bases 2, 8 and 16. Show your work.
k)
Write
the numbers 
in
bases 2, 8, 10. Add them in base 2. Multiply them in base 16. Show your work.
l)
Find
the GCD of 85 and 289 using Euclid’s algorithm. Show your work.
·
HW8
(Due Friday, May 1)
a)
Draw
a logical circuit for the Boolean function that takes in 3 input bits, X, Y, Z,
and outputs 1 if and only if X = Y = Z.
b)
Draw
a logical circuit for the Boolean function that takes in 4 input bits, and
outputs 1 if and only if exactly one of the bits is 1.
c)
Draw
a finite state machine that takes in a string of 0's and 1's, and accepts if
and only if there are at least two 1's in the string.
d)
Draw
a finite state machine that takes in a string of A's, B's and C's and accepts
if and only if there is no occurrence of "ABC" as a substring.
e)
Draw
a finite state machine that takes in a string of A's, B's and C's, and accepts
if and only if there is no occurrence of "ABAC" as a substring.
f)
Draw
a finite state machine that takes in a string of 0's and 1's, and accepts if
and only if there are an odd number of 0's.
g)
Draw
a finite state machine that takes in a string of A's, B's and C's, and accepts
if and only if the string contains at least one of each letter A, B and C.
h)
Design
a finite state machine that takes in a string of 0’s and 1’s, and accepts if
and only if the string starts with 0 and ends with 1.
i)
Describe
in English the language 0(0
1)*1.
j)
Describe
in English the language ((ab)*a(ab)*).
k)
Describe
in English the language (0*10*10*)*.
l)
Describe
in English the language given by the grammar: S à aaSbb |
m)
Describe
in English the language given by the grammar: S à aSa | bSb | | a
| b
n)
Describe
in English the language given by the grammar: S à aSbS | bSaS |
o)
Describe
in English the language given by the grammar: S à aT | a, TàbS | b
p)
Prove
that if 
and 
then 
.
q)
Prove
that if and then 
.
r)
Prove,
by induction on k, that if , then 
.
Lecture Schedule
|
Date |
Topic |
Reading |
|
January
20 |
class
overview, propositional logic |
1.1-1.2 |
|
January
23 |
more
propositional logic |
1.3 |
|
January 27 |
CLASS CANCELLED
(snowstorm) |
|
|
January
30 |
more
propositional logic, predicates, quantifiers |
1.4 |
|
February
3 |
more
predicates and quantifiers |
1.4-1.5 |
|
February
6 |
nested
quantifiers, reasoning and deducing |
1.5-1.6 |
|
February
10 |
reasoning,
proofs |
1.6 |
|
February
13 |
Proofs |
1.7 |
|
February
17 |
more
proofs |
1.7-1.8 |
|
February
20 |
some
interesting proofs of famous classical theorems |
1.7-1.8 |
|
February
24 |
sets,
operations on sets, functions |
2.1-2.2 |
|
February
27 |
Functions |
2.3 |
|
March
3 |
Cardinality |
2.5 |
|
March
6 |
Infinity |
2.5 |
|
March 10 |
MIDTERM BECK HALL
AUDITORIUM (http://rumaps.rutgers.edu/location/beck-hall) LIVINGSTON CAMPUS |
|
|
March
13 |
proof
by induction |
5.1 |
|
March 17 |
NO CLASS (SPRING
BREAK) |
|
|
March 20 |
NO CLASS (SPRING
BREAK) |
|
|
March
24 |
more
induction |
5.1 |
|
March
27 |
strong
induction |
5.2 |
|
March
31 |
more
induction |
5.1-5.3 |
|
April
3 |
relations,
properties of relations |
9.1 |
|
April
7 |
more
properties of relations, equivalence relations |
9.1,9.3 |
|
April
10 |
division,
divisibility, congruences |
4.1 |
|
April
14 |
base
q representations |
4.2 |
|
April
17 |
prime
factorization |
4.3 |
|
April
21 |
Boolean
circuits |
12.2,
12.3 |
|
April
24 |
Boolean
circuits, finite state machines |
13.3 |
|
April
28 |
finite
state machines, grammars |
13.1 |
|
May 1 |
asymptotics + what comes next |
|
|
May 12 8am-11am |
FINAL EXAM |
|