Spring'23: Introduction to Discrete Structures I (CS 205)
Wednesday: 17:40-19:00
HILL building - Room 114
Instructor: Karthik C. S. (Office hours on Zoom: Tuesday, 20:00-21:00; link available on Canvas)
Recitations: Evgenia Chroni, Sharath Punna, Prince Rawal, Adarsh Srinivasan, Hengyi Wang, Gagan Gowda Madaiah.
Topics and Schedule
The tentative syllabus can be found here.
| Lecture # | When | Topic |
| Lecture 1 | 01/18 | Propositional Logic (Chapter 3; Sections 3.1, 3.2, 3.4.1) |
| Lecture 2 | 01/23 | More Propositional Logic (Chapter 3; Sections 3.1, 3.2, 3.4.1) |
| Lecture 3 | 01/25 | Propositional Equivalence (Chapter 3; Sections 3.3 and 3.4.2) |
| Lecture 4 | 01/30 | Predicates and Quantifiers (Chapter 3; Section 3.6) |
| Lecture 5 | 02/01 | Introduction to Proofs (Chapter 1; Sections 1.4, 1.5, and 1.8) |
| Lecture 6 | 02/06 | Proof methods and strategies (Chapter 1; Sections 1.5, 1.6, 1.7, 1.8 and 1.9) |
| Lecture 7 | 02/08 | More proof methods (Chapter 1; Sections 1.5, 1.6, 1.7, 1.8 and 1.9) |
| Lecture 8 | 02/13 | Sets (Chapter 0; Section 0.3) and Relations (Chapter 4; Sections 4.4) |
| Lecture 9 | 02/15 | Functions (Chapter 0; Section 0.4) |
| Lecture 10 | 02/20 | More Functions (Chapter 0; Section 0.4) and Infinite sets (Chapter 8; Section 8.1) |
| Lecture 11 | 02/22 | Sequences and Recurrences (Chapter 2; Section 2.1) |
| Lecture 12 | 02/27 | Induction (Chapter 5; Section 5.1) |
| Lecture 13 | 03/01 | Strong Induction (Chapter 5; Sections 5.2 and 5.3) and Well Ordering Principle (Chapter 2; Sections 2.1 and 2.2) |
| 03/06 | Midterm Exam | |
| Lecture 14 | 03/08 | Recursive functions (Chapter 7; Section 7.3) |
| Lecture 15 | 03/20 | General Induction (Chapter 5; Section 5.3) |
| Lecture 16 | 03/22 | More Induction Proofs (Chapter 2; Section 2.5) |
| Lecture 17 | 03/27 | Languages and Grammar (Chapters 2 and 11) |
| Lecture 18 | 03/29 | Finite State Machines (Chapter 5) |
| No Lecture | 04/03 | |
| Lecture 19 | 04/05 | Finite State Automata (Chapter 5) |
| Lecture 20 | 04/10 | Non-deterministic Finite State Automata and Regular Expressions (Chapters 5 and 6) |
| Lecture 21 | 04/12 | Turing Machines (Chapter 17) |
| Lecture 23 | 04/17 | Divisibility (Chapter 9) |
| Lecture 24 | 04/19 | RSA Cryptographic System (Chapter 9) |
| Lecture 25 | 04/24 | Homework 4 Help Session |
| Lecture 26 | 04/26 | Miscellaneous Content |
| Lecture 27 | 05/01 | Quizzes Help Session |
Grading
As mentioned in the syllabus, the grading is as described in here. In particular, there is no curve based grading!Your grade is computed out of 1000 points or 100%. You can accumulate at most 300 points (30%) from homework and at most 200 points (20%) from quizzes. The midterm is assigned 250 points (25%) and final exam is assigned 250 points (25%).
To compute your grade sum up all the homework, quizzes, midterm, and final exam.
There is no curve: you must earn a minimum of 90% of the total points for an A (900 points), 85% for a B+ (850 points), 80% for a B (800 points), 75% for a C+ (750 points), 70% for a C (700 points), and 60% for a D (600 points). You will fail the course if you earn less than 60% points (600 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 exceptions.
There will be 4 homeworks each assigned 75 points that you may accumulate. There will be weekly quizzes (about 11 or 12 quizzes throughout the course). Each quiz is assigned 20 points (you may accumulate at most 200 points through quizzes; if you obtain more than 200 points then it will be capped to exactly 200 points).
All quizzes will be released on Monday nights on Canvas and you have until the Sunday night on the same week to complete the quiz. If you are familiar with the material covered in class, then you should be able to complete each quiz in well under 10 minutes. That said you will be allowed 20 minutes to complete the quiz (once you begin).
Open and Affordable Textbooks Program
This course has received an Open and Affordable Textbooks Program Award from the Rutgers University Libraries. The OAT Program supports textbook affordability at Rutgers by encouraging courses to adopt educational materials that are freely available, available at a low cost (compared to similar courses), or part of the Rutgers University Libraries' electronic collections, and thereby free of charge to Rutgers University students. As a student in this course, you will be asked to provide feedback on this initiative at the end of the semester.