## 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: 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

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 write-up 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 write-ups, 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.
• 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 80-89, 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 757-221-2509 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 write-ups are required to be produced with LaTeX, the standard high-quality typesetting program in our field and in technical writing. LaTeX is a based on mark-up language (like HTML) as opposed to "what you see is what you get" of word-processors. As in all learning experiences, in the beginning it looks difficult and tedious but it is very powerful.
You must pick-up 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 write-up in LaTeX. Moreover, each homework assignment will be posted both in PDF and in the source LaTeX.
• Homework write-ups 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 write-up 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 write-ups, 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.
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):
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