Computer Science 243, Discrete Structures
Spring 2018
Andreas Stathopoulos
Department of Computer Science
College of William and Mary
General Information 
Assignments 
Exams 
Course schedule
Course:

CS 243

Title:

Discrete Structures

Semester:

Spring 2018

Time/Place:

TR 2:003:20 pm in Morton Hall 203

Office hours:

TR 3:304:30 pm, in MS 104B
Wed 11:0012:00 pm, in MS 104B

TA:

Jeremy Myers

TA's office hours:

MW 1:002:00 pm at MS 001

Prerequisite:

CS 141  Computational Problem Solving

Textbook:

Kenneth H. Rosen, Discrete Mathematics and Its Applications, 7th edition, McGraw Hill, 2012

Course Webpage:

http://www.cs.wm.edu/~andreas/Teach/243

Syllabus in pdf:

http://www.cs.wm.edu/~andreas/Teach/243/Syl.pdf

Catalog Description:
Theoretical foundations of computer science, including sets, functions,
boolean algebra, first order predicate calculus, trees, graphs, and
discrete probability.
Why this course?
From bits, to integers, to enumerations, to sets, to the steps of a program,
discrete quantities play a central role in Computer Science.
To solve problems with computers, we use logic and mathematical reasoning
to create sequences of such discrete quantities (programs that manipulate
data) that when run on a computer produce the desired outcome.
But how do we know we have covered all possible cases? How do we know that the
structures we have created correspond to the problem we want to solve?
How do know that the method we have provided is possible, efficient,
or, most importantly, correct?
The goal of this course is to provide you with the necessary mathematical
background needed to start answering these questions.
Requirements
 There will be about twelve (12) written homework assignments,
assigned on a weekly basis, which account for 40% of your final grade.
These assignments do not involve any programming, and will help you
better understand the material taught in the class. For more information,
follow the link "Assignments" at the top of this page.
 There will be two midterm exams accounting for 30% of your final grade.
For more information, follow the "Exams" link at the top of this page.
 There will be a final exam accounting for 30% of your final grade.
For more information, follow the "Exams" link at the top of this page.
Grading policy
The Honor Code applies on all assignments, projects and exams.
Specifically:
 For the homework assignments you may talk about the problem with
fellow students, the TA, and the instructor, but
the writeup must be yours.
In particular, when discussing with fellow students you must strictly follow
the "empty hand policy": You cannot leave a discussion meeting with
any record of the discussion (hard copy or electronic). All scratch paper
must be torn and thrown away, and boards erased.
In your homework writeups, you should also give credit to your collaborators
for each problem.
Finally, you may neither consult students that have taken the course
previously, nor their completed work.

For the written assignments, you are allowed to consult
other books, papers, or published material. The Web is also considered
a publication media. However, you MUST reference all the sources
that helped you in the assignment.

You should not plagiarize. Therefore, you should write solutions in
your own words, even if the solutions exist in a publication that you reference.
In addition, the following grading policies apply:
 Homework assignments should be typeset in LaTeX.
For more information, follow the link "Assignments" at the top of this page.
 No late written assignments will be accepted.
All assignments are due at the beginning of the specified class period.
 There may be a curve of the final grades, although the lower
bounds of the standard scale are guaranteed,
i.e., you will get an A or A if your grade is 90 or above,
a B(/+) if it is 8089, etc.
Disabilities:
It is the policy of The College of William & Mary to accommodate students with disabilities and qualifying diagnosed conditions in accordance with federal and state laws. Any student who feels s/he may need an accommodation based on the impact of a learning, psychiatric, physical or chronic health diagnosis should be referred to Student Accessibility Services staff at 7572212509 or at
sas@wm.edu.
SAS staff will work with you to determine if accommodations are warranted, and if so, to help you obtain an official letter of accommodation. For more information please see www.wm.edu/sas.
Assignments
Homeworks will appear on Blackboard weekly.
You will upload a pdf of your solution onto Blackboard by the due date.
Graded homeworks will be returned through Blackboard.
Procedural
 Homework writeups are required to be produced with LaTeX, the
standard highquality typesetting program in our field and in technical
writing. LaTeX is a based on markup language (like HTML) as opposed to
"what you see is what you get" of wordprocessors.
As in all learning experiences, in the beginning it looks difficult and
tedious but it is very powerful.
You must pickup LaTeX skills by yourself. However, to make things
a little easier for you, Prof. W. Mao has written a brief introduction,
called LaTeX summary,
that contains a minimum set of things you need to know to produce
a homework writeup in LaTeX. Moreover, each homework assignment will
be posted both in PDF and in the source LaTeX.
 Homework writeups must contain for each problem both the
problem description and its solution.
 Remember each homework assignment is due at 02:00 pm (at the beginning
of class) on its due date.
You should upload onto Blackboard only the pdf document produced by your
latex file; not the latex file.
No late homework will be accepted unless
there is a medical reason (with doctor's note) or family emergency as
defined by the College.
 Always give yourself plenty of time to work on a problem set. Never
expect to be able to start and complete a problem set the night before
it is due.
 Since another goal of doing homework is to improve your technical
writing skills, it is important that you write in a comprehensive
and yet concise style. Points may be taken off for poorly written solutions.
Reiterating the Honor Code policy
 For the homework assignments you may talk about the problem with
fellow students, the TA, and the instructor, but
the writeup must be yours.
In particular, when discussing with fellow students you must strictly follow
the "empty hand policy": You cannot leave a discussion meeting with
any record of the discussion (hard copy or electronic). All scratch paper
must be torn and thrown away, and boards erased.
In your homework writeups, you should also give credit to your collaborators
for each problem.
Finally, you may neither consult students that have taken the course
previously, nor their completed work.

For the written assignments and the projects, you are allowed to consult
other books, papers, or published material. The Web is also considered
a publication media. However, you MUST reference all the sources
that helped you in the assignment.

You should not plagiarize. Therefore, you should write solutions in
your own words, even if the solutions exist in a publication that you reference.
In class exams
Two 50 minute midterm exams.
Opentextbook and opennotes. No calculators, computers, phones, etc.
Location: Morton 203
1st exam: the last 50 minutes of the class period on Thursday March 1, 02:00 pm.
Covers the course materials up until before the spring break
2nd exam: the last 50 minutes of the class period on Thursday April 19, 02:00 pm.
Covers the course materials up until before Trees
Final exam:
Opentextbook and opennotes. No calculators, computers, phones, etc.
Covers the course materials of the entire semester.
Location: Morton 203
When: Thursday, May 3, 2:005:00 pm.
Course schedule
Week 1 (01/18 and 01/23):
 Logic
Week 2 (01/25 and 01/30):
 Methods of proofs
Week 3 (2/1 and 2/6):
 Sets
Week 4 (2/8 and 2/13):
 Functions, sequences and sums
Week 5 (2/15 and 2/20):
 Asymptotic notation
Week 6 (2/22 and 2/27):
 Algorithms
Week 7 (3/1 and 3/13):
 Midterm exam on 3/1, discussion of midterm, and Complexity
Week 8 (3/15 and 3/20):
 Mathematical induction
Week 9 (3/22 and 3/27)
 Mathematical induction
Week 10 (3/29 and 4/3):
 Recursive definitions and algorithms
Week 11 (4/5 and 4/10):
 Counting
Week 12 (4/12 and 4/17):
 Discrete probability
Week 13 (4/19 and 4/24):
 Midterm on 4/19, Trees and some Graphs
Week 14 (4/26):
 Graphs and final review