Skip to Main Content

Introduction to Discrete Structures

Computer Science Department

CS 205 – Introduction to Discrete Structures I 

Course Description

This course introduces student to the mathematical tools of logic and induction, and to the basic definitions and theorems concerning relations, functions, and sets. Later courses in the computer science curriculum build on the mathematical foundations covered here. Particular emphasis is placed on inductive definitions and proofs, with application to problems in computer science. Special topics such as proofs of partial program correctness, finite state automata and modula arithmetic will be discussed. The course covers 6 major topics. The order of the coverage may vary based on instructor preference. Please refer to canvas course page for more details.

Course Topics   

Topic 1 – The foundations Logic and Proofs

Propositional Logic
Applications of propositional logic
Propositional Equivalences
Predicates and Quantifiers
Nested Quantifiers
Introduction to Proofs

Topic 2 – Sets, Functions, Relations and Sequences

Sets
Set operations
Functions

Relations
Sequences and Summations
Cardinality of Sets

Topic 3 – Induction

Mathematical Induction
Strong induction and well-ordering 
Recursive algorithms
Program correctness*

Topic 4 – Modeling Computation

Languages and Grammar
Finite State Machines
Turing machines*

Topic 5 – Boolean Functions

Boolean Functions
Representations
Logic Gates*
Minimization of circuits*

Topic 6 – Number Theory

Divisibility and Modular Arithmetic
Integer representations and Algorithms
Primes and Greatest Common Divisor
Cryptography*

 Course Learning Goals

A. Prepare students to contribute to a rapidly changing field by acquiring a thorough grounding in the core principles and mathematical foundations of computer science (e.g., techniques of program analysis, proof techniques such as induction; basic foundations of theoretical computer science).

B. Students will acquire a deeper understanding on the abstract models of computing such as finite state automata, Turing machines and build programs based on these models of computing. Students will also acquire skills in reasoning about programs using loop invariants and contracts.

C. Students will be prepared for the upcoming theoretical computer science courses in the curriculum as well as explaining the ability to reason about programs, a key component in software validation. 

Lecture Sections

Sections 01, 02, 03, 04, 05 -M/W 5:40 PM- 7:00 PM  Busch Hill-114 – Prof. Sumegha Garg  
Sections 15, 16, 17 -T/Th 12:10 AM- 1:30 PM  BUsch PH-111 – Prof. Daniel Bittner
Sections 06, 07, 08,09,10 – M/W 2:00 PM- 3:20 PM  Busch Hill-114 – Prof. Andy Gunawardena

Textbook and Discussions 

Textbook: Discrete Mathematics and its applications, Kenneth Rosen, Rutgers Edition, 7th Edition, ISBN-978-1259-15215-4.  You can purchase a copy of the book from any vendor.

Discussions :   Some sections may have discussions on Piazza or on canvas. Please visit you section webpage for more information.

Supplemental CUbits Videos (not a replacement to lecture)

Supplemental Videos: A curated video collection is provided to you as an assistance to further understanding topics or catch up with missed lectures. Videos are recorded by Rutgers Instructors as well as other instructors. The videos also contain self-assessment quiz questions and you can post Q&A on each video.  There will be only one access code issued during the semester to encourage students to watch videos before or during a topic is covered. To access the videos, 

IMPORTANT. The videos are NOT a replacement to the lectures. They are supplemental and just that. Lecture attendance is required. However, if you miss the lecture or did not understand a specific concept, these cubits videos can help. Also, watching cubits videos, doing self-assessment quizzes and participating in Q&A  can allow you to earn bonus points for participation in some lectures (contact your instructor for more details). You can see your engagement statistics from the cubits dashboard to make sure you are able to earn points. Follow the steps below to get access to videos.

Step 1. Create a free account at cubits.ai – https://www.api.cubits.ai/accounts/signup/   (be sure to validate account. Check spam folder if needed). 

Use the Rutgers Email in the form: netID@rutgers.edu   You may not receive any participation credit if you use a different email format (eg. andy.guna@rutgers.edu). Proper use is adg133@rutgers.edu

Step 2. Login and Click on https://www.cubits.ai/collections/31/

Step 3: Apply the class code:  IaXwKm35  (there is only one code available to students to access videos before and during a topic is discussed. 

Mobile access:  After subscribing open https://cubits.ai on any mobile device.

CS205 meets SAS goals QQ or QR, ITR:

  • Formulate, evaluate, and communicate conclusions and inferences from quantitative information. [QQ]
  • Apply effective and efficient mathematical or other formal processes to reason and to solve problems. [QR]
  • Employ current technologies to access and evaluate information, to conduct research, and to communicate findings, and understand the principles that underlie information systems.[ITR]
5102AwbnX7L._SX374_BO1,204,203,200_

Textbook Discrete Mathematics and Its Applications, 2nd Edition, Kenneth Rosen,  (Rutgers Edition is Recommended, as it contains only the required chapters)

Academic Integrity

You are responsible for reading and understanding the DCS Academic Integrity Policy. Read the overview as well as the specific policies for exams. Instances of cheating will be punished by a zero grade, a failing grade for the course, and/or referral to your dean, at the discretion of the course staff.

All assignments and exams are individual but we encourage collaboration with course staff and classmates. However, you must be careful how you collaborate. Use the guidelines bellow for reference:

Course staff Classmates Other people
Discuss concepts with: Yes Yes Yes
Acknowledge collaboration with: Yes Yes Yes
Expose code/solutions to: Yes No No
Copy code/solutions from: No No No

Recitations

Recitations occur directly after each lecture.

Attend the recitation you are registered for 

Problem Sets/ Homework

Plan to submit your assignments on time, no late assignments are accepted.

Assignments are graded  Always read the feedback!

Plan to submit your work with at least one day in advance to avoid any submission issues. 

Grading

Written assignments and exams are graded by TAs in Gradescope/Canvas (depending on section) and you will receive your score about one week after the assignment due date or exam date.

Regrades

For written assignments, quizzes and exams, you have one week after the grades are released to ask for a regrade. Only ask for a regrade if you think there was a grading error, do not request a regrade simply because you think you deserve more partial credit.

Canvas

Canvas is a course management tool that will be used to keep students scores and send out announcements. Once registered to the course you will be automatically added to Canvas. Use your Rutgers credentials to login.

The course staff expects all students to read the announcements.

Discussions 

Please refer to your section canvas page for course discussions.

Exams

There will be 1 section midterm (25%) and 1 common final exam (25%) for all sections. 

  • All exams are given in-person
  • You can consult a cheat sheet during exams.
  • You will have 80 consecutive minutes to complete a midterm exam and 3 consecutive hours to complete the final exam. 

Refer to the Exams page for exam dates. You are required to be available online to take the quizzes, so DO NOT make arrangements for those days. 

There are NO makeup exams

Students that require accommodations, such as extra time, must contact ODS at least two weeks before the quiz date. Email your accommodations letter to the course instructor. Extra time will be added to your exam allowed time

Grading Criteria 

In general, your grade may depend on one or more of the 3 major indicators that are used in grading.

  • Product criteria
    • which is a demonstration of student learning through psets, quizzes and exams.
  • Process criteria
    • behaviors that enable learning – homework, classroom effort, participation, punctuality,
  • progress criteria
    • which focuses on how far students have progressed, sometimes referred to as improvement or value added grading.

Grading

Your grade is computed out of 100%. The donut chart to the right has the distribution of the 100% among problem sets/homework/quizzes/attendance/participation (50%), We assign at least 25% for problem sets and 20% for quizzes and 5% discretionary (this may vary from instructor to instructor). The midterm is assigned (25%) and final exam is assigned (25%).  Please consult your section instructor for more details about grading criteria.

To compute your grade sum up all the homework/problem sets/quizzes, midterm, final exam + bonus points

There is no curve: you must earn a minimum of 90% of the total points for an A, 85% for a B+, 80% for a B, 75% for a C+, 70% for a C, and 60% for a D. You will fail the course if you earn less than 60% points.

The cutoffs are strictly followed for each letter grade. A computed grade of 74.99% is a C not a C+.

There are no other extra credits activities for the course. No excepti