CSE 215 Section 2 (Spring 2020)
Foundations of Computer Science

General Information | Schedule | Resources | Requirements

General Information

Course description:
Introduction to the logical and mathematical foundations of computer science. Topics include functions, relations, and sets; recursion; elementary logic; and mathematical induction and other proof techniques. Prerequisites: AMS 151 or MAT 125 or MAT 131. Credits: 4.

Major topics covered in course:
1. Logic (compound statements, quantifiers, etc.).
2. Proof methods.
3. Mathematical induction and recursion.
4. Set theory.
5. Functions (at least: one-to-one, onto, composition).

Course outcomes:
1. An ability to define and use discrete structures such as functions and sets.
2. To understand recursion as a computing paradigm.
3. An ability to use logic and basic proof techniques, such as mathematical induction.

Source for items above: https://www.cs.stonybrook.edu/students/Undergraduate-Studies/courses/CSE215

Instructor: Annie Liu. Office hours: Mon 9-9:30am, 12:40-1pm, 2:20-3pm, 4:20-5pm, Thu 4:20-5pm, Fri 9-9:30am, 12:40-1pm, 2:20-3pm
Office: New Computer Science Building, Room 237. Phone: 631-632-8463. Email: liu@cs.stonybrook.edu

Teaching assistants:
Dibyendu Das. Lead: REC 6, REC 10, HW 4 grading. Office hours: Wed 1-2:30 pm, Thu 3-4:30 pm. Email: dibyendu.das@stonybrook.edu
Vivian Lam. Lead: REC 7. Office hours: Mon 9-10 am, Wed 10-11 am, 12-1 pm. Email: vivian.lam@stonybrook.edu
Regina Wong. Lead: REC 4. Office hours: Wed Fri 9-10 am, Tue 2:30-3:30 pm. Email: regina.wong@stonybrook.edu
Ruyi Lian. Lead: Exercise grading, HW 5 grading, gradebook keeping. Office hours: Tue Thu 1-2:30 pm. Email: ruyi.lian@stonybrook.edu
Billy Wong. Lead: Extra-credit programming grading. Office hours: Mon 10-11 am, Fri 3-5 pm. Email: billy.wong@stonybrook.edu
Shraddhan Jain. Lead: HW1 grading. Email: shraddhan.jain@stonybrook.edu
Krishna Patel. Lead: HW2 grading. Email: krishnaamit.patel@stonybrook.edu
Shubham Rathore. Lead: HW3 grading. Email: shubham.rathore@stonybrook.edu
Yueqi Hu. Lead: HW6 grading. Email: yueqi.hu@stonybrook.edu
Karthik Natarajan. Lead: HW7 grading. Email: karthik.natarajan@stonybrook.edu

Section 2: Mon and Fri 1-2:20 PM, Engineering 145

Section 7: Mon 11-11:53 AM, CS 2129 (TA: Vivian Lam, Billy Wong)
Section 4: Wed 11-11:53 AM, CS 2129 (TA: Regina Wong, Vivian Lam)
Section 10: Fri 10-10:53 AM, CS 2114 (TA: Dibyendu Das, Regina Wong)
Section 6: Fri 11-11:53 AM, CS 2114 (TA: Dibyendu Das, Billy Wong)

Office hours: TA office hours will be held in CS 2217, except in NCS 230 for Dibyendu.
Monday Tuesday Wednesday Thursday Friday
9-9:30 am Annie, Vivian Regina Annie, Regina
9:30-10 am Vivian Regina Regina
10-10:53 am Billy (-11:00) Vivian (-11:00) REC 10: D, R
11-11:53 am REC 07: V, B REC 04: R, V REC 06: D, B
12-1 pm Annie (12:40-) Vivian Annie (12:40-)
1-2:20 pm LECTURE Ruyi (-2:30) Dibyendu (-2:30) Ruyi (-2:30) LECTURE
2:20-3 pm Annie Regina (2:30-) Annie
3-4:20 pm Regina (-3:30) Dibyendu (-4:30) Billy
4:20-5 pm Annie Annie Billy

Susanna Epp, An introduction to Mathematical Reasoning, Brief edition, 1st edition, Brooks/Cole Cengage Learning, 2011, ISBN: 9780495826170 (at Amazon)

Lecture critique: 2%
In-class exercises: 8%
Homework assignments: 20%
Midterm exams: 40% (20% each)
Final exam: 30%
Grade cutoffs: A [93-100], A- [90-93), B+ [87-90), B [83-87), B- [80-83), C+ [77-80), C [73-77), C- [70-73), D+ [67-70), D [63-67), F [0-63)
Special rule: If all your grades for the three exams are above the respective class averages, you are guaranteed to receive a grade of C or higher.
Extra credits: There will be extra credit problems as a part of in-class exercises and homework assignments, which counts no more than 5% in the final grade.

Course homepage: http://www.cs.stonybrook.edu/~liu/cse215

Schedule (With updates for extended break and moving online)

Week Date Lectures/Notes Readings/Notes Homework
1 1/27 Introduction; speaking mathematically Ch.1, Introduction to LaTeX Create an Overleaf account. Try out Detexify
1/31 The Logic of compound statements: logical forms and truth values; logical arguments; digital circuits Ch.2.1-2 Homework 1
2 2/3 Ch.2.3
2/7 4PM Last day to add, swap, and drop without a "W" Stony Brook Academic Calendars
3 2/10 The Logic of quantified statements: predicates and quantified forms; nested quantifiers; arguments with quantified forms Ch.3.1-2 Homework 2 (Hw 1 due before class)
2/14 Ch.3.3
4 2/17 Ch.3.4
2/21 Elementary number theory; methods of proof: even/odd, prime/composite, divisibility; proving existential/universal: direct, counterexample, by cases, by contradiction; algorithms div/gcd Ch.4.1-2 Homework 3 (Hw 2 due before class)
5 2/24 Ch.4.3-4
2/28 Ch.4.5-6
6 3/2 Midterm review 1 (Hw 3 due before class)
3/6 Midterm exam 1
7 3/9 sequences; mathematical induction; recursion: sequences, sum, product; induction, strong induction; Ch.5.1, 5.4.int base 2 Homework 4
3/13 Ch.5.2-4
8-9 3/16-22
Spring break Stony Brook Academic Calendars
910 3/233/30 recursion; correctness of algorithms Ch.5.5-6
3/274/3 Set theory: set membership and operations; Ch.6.1 Homework 5 (Hw 4 due before class)
3/274/3 4PM Last day to drop with a "W" Stony Brook Academic Calendars
1011 3/304/5 set properties and proofs; Boolean algebra and Russel's paradox Ch.6.2-4
4/34/10 Functions: definition and terminology; one-one and onto, inverse functions; function composition; cardinality and sizes of infinity Ch.7.1 Homework 6
1112 4/64/13 Ch.7.2
4/104/17 Ch.7.3-4
1213 4/134/20 Midterm review 2 period start (Hw 6 due before class)
4/174/24 Midterm exam 2 period end
13 4/20
14 4/244/27 Relations: definition, relational DB; properties, transitive closure; equivalence relations, congruence modulo; partial order relations, topological sort Ch.8.1-2 Homework 7
14 4/275/1 Ch.8.3, overview of 8.4-5
15 5/15/4 Ch.8.5 of complete edition
15 5/4
5/8 Final review (Hw 7 due before class)
Final 5/18 Final exam: Monday, May 18, 2020, 2:15-5PM Registrar Final Exam Schedule

Other Resources

Google Classroom of this class, for students in the class

Computer Science Department Computing Labs

Resources by the textbook author: Discrete Mathematics Animations Etc., Errata, and a few other documents

Just about any topic can be studied further:
..:: wu : riddles ::..
An explanation of knight/knave/spy puzzles, with a complete list of valid puzzles of the form.

Free Tutoring Services:
The College of Engineering and Applied Sciences (CEAS) offers a range of free tutoring services for students in CSE, AMS and other courses. See the CEAS Undergraduate Student Office website for more information. For small group and one-on-one tutoring please inquire also at the Academic Success and Tutoring Center.


Learn all information on the course homepage. Check the homepage periodically for announcements and other dynamic contents.

Attend all lectures, recitations, and take good notes. This is the most efficient way to learn the course materials, because we will both distill and elaborate textbook materials and discuss important related materials. We will start promptly on time. We will have every student participate in solving problems and presenting solutions in class.

Do all course work. The readings are to help you preview and review the materials discussed in the lectures. The assignments are to provide concrete experiences with the basic concepts and methods covered in the lectures. The exercises and quizzes are to help check that you are keeping up with the lectures and the assignments. The exams will be comprehensive.

Your work:

Your handins, whether in electronic form or on paper, should include the following information at the top: your name, student id, course number, assignment number, and due date, and should be submitted in a neat and organized fashion.

Your approach to solving problems is as important as your final solutions; you need to show how you arrived at your solutions and include appropriate explanations.

Each student's homework submission must be his or her own work. You are not permitted to share, borrow, or even look at another student's work while completing your own homework. Likewise, copying material from any source other than the textbook or from the instructor's handouts will constitute cheating. Any evidence that answers have been copied, shared, or transmitted in any way, including the use of answers downloaded from the Internet or written by others in previous semesters, will be regarded as evidence of academic dishonesty. The College of Engineering and Applied Sciences (CEAS) regards academic dishonesty as a very serious matter and provides for substantial penalties in such cases, such as receiving an 'F' grade and/or expulsion from the University. Those involved in academically dishonest behavior will be prosecuted to the fullest extent permitted by the University and College laws. For more information, you can obtain a copy of the CEAS guidelines on academic dishonesty from the CEAS office.

All examinations will be closed-notes and closed-book. No electronic devices of any kind will be permitted to be used during exams. All cell phones must be silenced or turned off during exams. Any use of electronic devices, textbooks, notes or any other materials will constitute cheating.


Neither extensions nor late submissions will be approved under normal circumstances. If some sort of emergency or other circumstances truly beyond your control prevent you from submitting your assignment on time, supply the instructor with suitable documentation and notification prior to the assignment deadline. The instructor will also refer you to the Dean of Students for follow-up consultation.

Homework assignments must be completed in the LaTeX language that can be compiled into a PDF. Students will largely be responsible for learning LaTeX on their own, but the instructor will spend some time during the first week of the course teaching the basics. A submission that is not in LaTeX and that cannot be compiled into a viewable PDF will earn a grade of zero.

Homework assignments in both LaTeX and PDF formats must be submitted to Google Classroom before class on the due date. Name you main latex file "main.tex". Please zip your LaTeX source code files and compiled PDF into a single zipfile. Name your file exactly as "First_Last_ID_HWx.zip", where First is your first name, Last is your last name, ID is your Stony Brook student ID, and x is the homework number. Submit the single zip file in Google classroom, and add no other files or comments.

Students are urged to plan ahead to avoid problems such as computer failures at the last minute. If your assignment is incomplete before it is due, turn in whatever you have. Note due to limited resources for grading, assignments that cannot be compiled into a PDF will not be graded. Students who take this course are often surprised by just how much time this course requires of them. You are advised to budget your time wisely and to start working on an assignment the day it is posted.

Grading issues:

The final grade you receive in this class will reflect, as far as possible, the extent to which you have mastered the concepts and their applications. How much someone needs a grade, or how close they are to the next higher grade, will have no effect on grade. As the instructor, I want everyone to do well in this course, and will make every reasonable effort to help you understand the material taught. However, the grades provided at the end of the semester are final, except for rare situations involving grading errors. They will not be altered for any reason, so please do not ask me to do so.

If you feel your grade was assigned incorrectly, please meet with the person (instructor or TA) responsible for the grading. Please arrange a re-grading within one week of receiving the graded work; later requests will not be entertained.

To promote consistency of grading, issues about work graded by a TA should be addressed first to the TA and then, if the issues are not resolved, to the instructor. You are welcome to contact the TA by email or come the TA's office hour. If you would like to speak with the TA in person, and have a schedule conflict with the TA's office hours, you are welcome to make an appointment to meet the TA at another time.

Source for items below: https://www.stonybrook.edu/commcms/provost/faculty/handbook/academic_policies/syllabus_statement.php

Academic Integrity:
Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Faculty is required to report any suspected instances of academic dishonesty to the Academic Judiciary. Faculty in the Health Sciences Center (School of Health Technology & Management, Nursing, Social Welfare, Dental Medicine) and School of Medicine are required to follow their school-specific procedures. For more comprehensive information on academic integrity, including categories of academic dishonesty please refer to the academic judiciary website at: http://www.stonybrook.edu/commcms/academic_integrity/index.html

Student Accessibility Support Center:
If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Student Accessibility Support Center, ECC (Educational Communications Center) Building, Room 128, (631)632-6748. They will determine with you what accommodations, if any, are necessary and appropriate. All information and documentation is confidential.
Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Student Accessibility Support Center. For procedures and information go to the following website: http://www.stonybrook.edu/ehs/fire/disabilities

Critical Incident Management:
Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of University Community Standards any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Faculty in the HSC Schools and the School of Medicine are required to follow their school-specific procedures. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook.

Credits: Many materials in this course are based on materials that other faculty have prepared in previous years. Special thanks to Paul Fodor, Pramod Ganapathi, and Kevin McDonnell.