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 no more than twelve (12) written homework assignments, assigned on a weekly basis, which account for 40% of your final grade. In the end, the homework with the lowest grade will be dropped. 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 in-class tests 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.

Honor Code
When you joined W&M you took the Honor Pledge:

As a member of the William & Mary community, I pledge on my honor not to lie, cheat, or steal, either in my academic or personal life. I understand that such acts violate the Honor Code and undermine the community of trust, of which we are all stewards.

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, boards erased, zoom meetings not recorded, etc. 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.

• 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 noon.
• 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.

Delivery

Pandemic preparedness

• Bookmark the recurring meeting link https://cwm.zoom.us/j/92149718275 in your browser. If you are not logged onto Zoom, the browser should direct you to a login interface which you can do through your institution (cwm.zoom.us).
• Log onto Zoom https://cwm.zoom.us/ , select "join meeting", and put in our meeting ID (921 4971 8275).
• Log onto Blackboard, go to the CSCI 243 page, and click the tab on the left: "Zoom link to live lectures".

• a Zoom link to live lectures,
• recorded class sessions are posted under "Recorded lecture videos",
• pdf of the class notes under "Lectures"
• a Zoom link to live Office Hours ,
• homeworks will be posted under Assignments,
• a forum will be created for course/homework discussions that don't violate the honor code,
• this syllabus.

Recording Consent
The class meetings will be recorded. Students who participate remotely and choose to switch their video on implicitly consent to be video recorded. Similarly, students who speak through Zoom or in class implicitly consent to be audio recorded.

Participation
Class attendance is strongly recommended but not mandatory. However, according to past experience, students that did not attend did not perform well and sometimes were not able to complete the course. The hope is that the availability of lectures in-person/live remote/video recordings will enable all students to attend in their preferred format.

Assignments

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 midnight on its due date. 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

Student Accessibility Services
William & Mary accommodates students with disabilities in accordance with federal laws and university policy. Students who feel they may need an accommodation based on the impact of a learning, psychiatric, physical, or chronic health diagnosis should contact Student Accessibility Services staff at 757-221-2512 or at sas@wm.edu to determine if accommodations are warranted and to obtain an official letter of accommodation. For more information, please see the www.wm.edu/sas .

Mental and Physical Well-Being
William & Mary recognizes that students juggle different responsibilities and can face challenges that make learning difficult. There are many resources available at W&M to help students navigate emotional/psychological, physical/medical, material/accessibility concerns. Asking for help is a sign of courage and strength. If you or someone you know is experiencing any of these challenges, we encourage you to reach out to the following offices:

• For psychological/emotional stress, please consider reaching out to the W&M Counseling Center ; or (757) 221-3620, 240 Gooch Dr., 2nd floor. Services are free and confidential.
• For physical/medical concerns, please consider reaching out to the W&M Health Center ; or (757) 221-4386, 240 Gooch Drive.
• For additional support or resources, please contact the Dean of Students by submitting a Care Report at https://www.wm.edu/offices/deanofstudents/services/caresupportservices/index.php ; or by calling 757-221-2510, or by emailing deanofstudents@wm.edu.
• For a list of many other resources available to students, see Health and Wellness Resources for Students.

Course schedule

Week 1 (01/25 and 01/27):

Logic

(Lectures 1-2)

Week 2 (01/30, 02/01, 02/03):

Methods of proofs

(Lectures 3-5)

Week 3 (02/06, 02/8, 02/10):

Proofs, Sets

(Lectures 6-7)

Week 4 (02/13, 02/15, 02/17):

Functions, sequences and sums

(Lecture 8)

Week 5 (02/20, 02/22, 02/24):

Asymptotic notation

(Lecture 9)

Week 6 (02/27, 03/01, 03/03):

Algorithms

(Lecture 10-11)

Week 7 (03/06, 03/08, 03/10):

Complexity

(Lecture 11) and Test 1 on 03/10

Spring Break 03/11-03/19

Week 8 (03/20, 03/22, 03/24):

Discussion of Test 1 and mathematical induction

(Lecture 12)

Week 9 (03/27, 03/29, 03/31):

Mathematical induction

(Lecture 12)

Week 10 (04/03, 04/05, 04/07):

Recursive definitions and algorithms

(Lectures 13-14)

Week 11 (04/10, 04/12, 04/14):

Counting

(Lectures 15-16)

Week 12 (04/17, 04/19, 04/21):

Discrete probability

(Lectures 16-17)

Week 13 (04/24, 04/26 04/28):

Trees and Test 2 on 04/28

Week 14 (05/01, 05/03, 05/05):

Test 2 on 11/28, Graphs and Test 2 review, final review

(Lectures 17-19)