CS 205: Introduction to Discrete Structures I Fall 2022

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 205: Introduction to Discrete Structures I

Fall 2022

Overview

This is a first of a two-semester s eries on discrete m athematics. D iscrete mathematics is at the intersection of a number of areas of mathematics and is especially relevant in computer science. We will cover logic and proofs, set theory, functions and relations, induction, basic number theory, and languages and automata.  We’ll make use of the the Lean theorem

prover.

Textbook

We’ll primarily refer to these textbooks:

• Logic and Proof (Avigad, Lewis, and van Doorn)

• Discrete Mathematics and Its Applications (Rosen, any recent edition).

Another useful resource is Mathematics for Computer Scienceby Eric Lehman, F. Thom- son Leighton, and Albert Meyer.

Grading

Grades will be weighted as follows:

Homework    60%

Quizzes        40%

Any regrading request must be raised within one week of grades being returned, after which they are considered final.

 

Quizzes

There will be roughly biweekly quizzes, hosted on Canvas. They will primarily focus on the content for recent weeks, but may contain anything from prior weeks as well.

Quizzes are open-book and open-note, but you may not use other resources or discuss problems with other students. All work must be your own.

Homework

There will be roughly biweekly homework assignments.  You are welcome to discuss these problems with other students, but the actual write-up of the solutions must be your own.

You can resubmit homeworks any number of times.  Grading will be based on the last submission.  You may submit homework up to 24 hours late with a penalty of 1 point per hour.

Homework must be submitted on Canvas; emailed submissions are not accepted.  You are responsible for ensuring the submitted files are correct.

Tentative schedule of topics

Logic and Proof    Rosen (7th ed)

1

Intro, Propositional logic

1 – 3

1.1 – 1.3

2

Logic, proofs

2 – 6

1.7 – 1.8

3

Predicate logic

7 – 10

1.4 – 1.6

4

Predicate logic

7 – 10

1.7 – 1.8

5

Sets

11 – 12

2.1 – 2.2

6

Relations

13 – 14

9

7

Functions

15 – 16

2.3

8

Cardinality and infinity

22

2.5

9

Induction

17 – 18

5.1 – 5.2

10

Induction

17 – 18

5.3 – 5.5

11

Number theory

19

4.1 – 4.3

12

Boolean algebra

n/a

12.1 – 12.3

13

Languages and automata

n/a

13

14

Languages and automata

n/a

13

Academic integrity

Rutgers University takes academic dishonesty very seriously.  By enrolling in this course, you assume responsibility for familiarizing yourself with the Academic Integrity Policy and the possible penalties (including suspension and expulsion) for violating the policy. As per the policy, all suspected violations will be reported to the Office of Student Conduct. Please review the Academic Integrity Policy at: https://nbacademicintegrity.rutgers.edu/.

Accomodations

Rutgers University welcomes students with disabilities into all of the University’s educational programs. In order to receive consideration for reasonable accommodations, a student with a disability must contact the appropriate disability services office at the campus where you are officially enrolled, participate in an intake interview, and provide documentation: https://ods.rutgers.edu/students/documentation-guidelines.

If the documentation supports your request for reasonable accommodations, your cam- pus’s disability services office will provide you with a Letter of Accommodations.  Please share this letter with your instructors and discuss the accommodations with them as early in your courses as possible.

To begin this process, please complete the registration form (https://webapps.rutgers. edu/student-ods/forms/registration).














2022-09-18