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:00-3:20 pm in Morton Hall 203
Office hours: TR 3:30-4:30 pm, in MS 104B
Wed 11:00-12:00 pm, in MS 104B
TA: Jeremy Myers
TA's office hours: MW 1:00-2: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:
Syllabus in 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.


Grading policy The Honor Code applies on all assignments, projects and exams. Specifically:

In addition, the following grading policies apply:

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 757-221-2509 or at 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


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.


Reiterating the Honor Code policy

In class exams

Two 50 minute midterm exams.
Open-textbook and open-notes. 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:
Open-textbook and open-notes. No calculators, computers, phones, etc. Covers the course materials of the entire semester.
Location: Morton 203
When: Thursday, May 3, 2:00-5:00 pm.

Course schedule

Week 1 (01/18 and 01/23):
Week 2 (01/25 and 01/30):
Methods of proofs
Week 3 (2/1 and 2/6):
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):
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):
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