CS 206: Introduction to Discrete Structures II Summer Semester 2024

Prerequisite(s):  01:198:205  or  14:332:202;  01:640:152.  Credit  not  given  for  this  course  and  01:640:477  or 14:32:226.

❖ A grade below a "C" in a prerequisite course will not satisfy that prerequisite requirement.

Calculator: A simple/scientific calculator with no memory.

Course Description: This is an introductory course in combinatorics and probability theory, two branches of mathematics that are of fundamental importance in computer science. The topics covered during the course:

•     Set Theory: Symbols and Terminology, Venn Diagrams and subsets, Set operations

•    Counting: Binomial coefficients, Permutations, Combinations, Partitions

•    Recurrence relations and generating functions

•    Discrete probability:

o  Random experiments, sample spaces, events, probability measures

o  Conditional probability, Bayes' Theorem, Independence

o  Random Variables

o  Expectation, variance, standard deviation

o  Binomial, Bernoulli, Poisson and Geometric distributions; law of large numbers

•    Some Topics from Graph Theory: Paths, Components, Connectivity, Euler Paths, Hamiltonian Paths, Planar Graphs, Trees

For ALL EXAMS, please refer to the suggested practice problems file for Section numbers of above topics.

Textbooks & Materials:

   Mathematical Ideas; 13th  edition, By: Charles D. Miller, Heeren, Hornsby, and Heeren

   Statistics for Engineers and Scientists;4th  edition, By: William Navidi

   Discrete Mathematics and Its Applications, 7th  edition, By: K. Rosen

Other Recommended Books:

   Mathematics for Computer Science; 10th  edition By Lehman, Leighton, and Meyer

https://people.csail.mit.edu/meyer/mcs.pdf

   A First Course in Probability, 8th  edition By S. Ross

You don’t need to buy books in order to dowell in the course.

Learning Outcomes: Upon successful completion, Computer Science major’s students should:

•     be prepared to contribute to a rapidly changing field by acquiring a thorough grounding in the core principles and foundations of computer science (e.g., techniques of program design, creation, and   testing; key aspects of computer hardware; algorithmic principles).

•     acquire a deeper understanding on (elective) topics of more specialized interest, and be able to critically review, assess, and communicate current developments in the field.

•     be prepared for the next step in their careers; for example, by having done a research project (for those   headed to graduate school), aprogramming project (for those going into the software industry), or some sort of business plan (for those going into business).

Teaching Methods: Lecture and small group work

Presentation of Material: Each period will begin with answering students ’ questions over material previously covered and assigned, for about 10 minutes. Once all questions are answered, the new material will be introduced, and several examples will be given. If you have questions, please ask them as they occur to you. If you don't understand, most likely there are others who don't understand. So, please ask questions during the class period. At the end of each class period, the problem assignment and the reading assignment for the next class period will be given.

I highly suggest that you post questions on CanvasDiscussion folder. Either I, a TA, or other

students will respond to you there. Such a forum will benefit the entire class.

   There are recorded lecture and recitation from past years on Canvas  Files folder

Work Outside the Classroom: This is a key course, so large amounts of work outside of class are required. This includes extensive reading assignments and exercise sets. If you feel that you cannot devote around 6 hours (the actual time will vary, of course) outside the classroom to study/practice each week, then this course is not for you. You can get help from any of the various sources available to you including: your instructor (see contact information and office hours at the end of this document), your TA, your fellow students, the learning center and the tutoring center. If you have any questions or concerns about the amount of work, please speak tome directly.

Attendance Policy: This course is a key component of your academic journey, and attending classes is crucial for your success. While attendance will betaken, it won't directly impact your final grade. However, consistent unexcused absences or lateness may affect your overall score. Please note that emailing me about your absence won't alter the policy, and I won't respond to such emails.

Your presence in class is an invaluable opportunity to engage with the material, interact with fellow students, and grasp the concepts effectively. Missing class may result in a deduction from your final score, and an extensive number of absences might necessitate withdrawal from the course.

It's important to take responsibility for catching up on missed content by connecting with classmates, reviewing    class materials, and preparing for upcoming lectures. I'm here to assist during office hours, but I cannot replicate   missed lectures. Considering the challenging nature of mathematics, attending class is a fundamental step in your learning journey. Embrace the opportunity to actively participate, ask questions, and ensure you don't miss out on the collaborative and enriching learning experience that the classroom provides.

It is your responsibility to catch up on missed content from fellow students, covering what was discussed and

what is required for upcoming lectures, whether we announce them on Canvas or Not.

You must also attend all examinations. Please see “Missing an Examination” for valid excuse document requirements and submission procedures. DO NOT bring any excuse materials to me. (Apart from the privacy concern, there is a practical advantage in centralizing this decision: it makes it harder for the student to make up contradictory excuses for various classes, whose instructors are not otherwise communicating with each other.)

Missing a Class/Quiz/Examination: You must attend all quizzes/examinations. You must have a valid medical or personal emergency to miss an examination.

•    For one time class absence, email me with all necessary documents/notes forgetting approval for any make up. (Please read Canvas Syllabus)

•    For 2 or more consecutive absence, you must submit your excuse documentation (doctor reports, accident reports, related material for a valid excuse, etc.) as soon as possible to the Dean of Students Office. After the Dean of Students has confirmed your excuse paperwork, they will notify me. I will then decide if you're eligible to take a makeup quiz/exam or not. You MUST follow up with me or your TA. Except for the reasons explained above, there are no makeups or incompletes. Missing a test (without a valid reason) will result in an automatic zero for that test. (NOTE: Travel arrangements/a purchased airline ticket do NOT constitute a valid excuse to miss any examinations as well as the final exam at its appointed date/time, so no makeup exam will be granted under these circumstances. Also, it is school policy that no student be permitted to take a final exam early.)

Class Work/Participation Overview: Attendance alone, won’t guarantee success in this course, active participation is key. One important aspect of my teaching style is to have my students actively participating in class. I foster an interactive learning environment, emphasizing a two-way communication between students and myself. Your engagement is crucial for your learning process, and I create safe space for questions, comments, and responses period.

To accomplish this, I regularly pose questions to prompt your thoughts on the subject matter. Feel encouraged to

contribute by sharing your opinions, attempting questions, and collaborating with peers in small groups of 3-4. Your presence, punctuality, and thoughtful participation in discussions and activities matter. Even if your answers aren't perfect, the willingness to engage is valued.

For those who may find it challenging to speak up loudly due to shyness or anxiety, I encourage you to consider sitting in the front rows during our class sessions. This way, even if you choose to participate more quietly, I'll

still be able to see and hear you. Your engagement is essential to the learning environment, and I want to create a space where everyone feels comfortable expressing their thoughts.

Please note, coming to board is not necessary at all to get a full point on class participation.

In the virtual setting, participation can occur through speaking or chat interactions. If you encounter difficulties due to anxiety or other reasons, communicate this concern at the semester's start, allowing us to find an alternative participation method.

Your participation contributes to a 6-point segment of the final 100-point score. The most active students

receive the full 6 points, while others are evaluated based on their relative participation levels. Please note that the participation score is subjective, reflecting my assessment of your engagement throughout the semester, and is not open for discussion or negotiation.

*Being a volunteer to come to the board and show your work will give you an extra 0.5-1 point.

Negative, offensive, and disrespectful comments and actions can do serious damage to the learning atmosphere.

Such behavior will necessarily result in a substantially lower grade.

(Note: Throughout the semester, please let me know if there is any topic that you do not understand. I will be happy to explain it in more detail, either during the lecture or office hours. Also, please let me know if there are exercise problems with which you need help. Keeping up with the material will help you enjoy the class more. If you start falling behind for any reason, please come and see me as soon as possible.)

Virtual Mode: Your camera must be “on” during each class (unless you have a waiver) and facing you so that the lecturer is able to see you. The attendance policy is the same as stated in the “Attendance” section above (5- 14 minutes and more than 15 minutes) and will apply if your camera is offor the lecturer is not able to see you. If Zoom sessions are offered, I will record the session/class which you should have access to through Cloud. I will utilize the “reports” feature in Zoom to produce a “usage report” of everyone who logged into a particular Zoom session/class. It will be used to monitor attendance. If you are facing technical issues, it is your responsibility to inform the instructor and IT department.

*You must clothed properly for online class …Driving or sleeping/laying on bed, I will take you out of the virtual mode.

Homework  Guidelines:  I've  provided  some  suggested  practice  problems  for  each  section  under  Canvas File Course Documents. It's important to note that there are no officially assigned homework tasks for this course that will be collected or graded. However, sporadically throughout the semester, I may, during the lecture, select relevant problems from the textbook for all students to work on before the next class. This serves as a collective assignment to enhance your understanding of the material and will be counted as part of your class participation.

(Note: I’ve posted variety of extra practice problems, mostly with solutions, on Canvas Files Extra Practice Problems. I’ve organized them based on their relative topics to make it easy for you to find.)

Learning Mathematics/Statistics: Learning mathematics is somewhat different from other disciplines. You learn mathematics/statistics  by  reading  the  text,  by  doing  exercises,  and  by  emulating  the  instructor.  All  three components--reading, exercises, and learning from the instructor--are necessary. Anything less will not do. (For example, if you were taking a course in carpentry, you could not master the craft merely by watching a master carpenter at work. You would need to handle wood and tools, make mistakes, correct them, start over and keep at it in order to learn carpentry. The same is true in mathematics/statistics.) You cannot merely watch the instructor and take notes. You must also do assigned exercises and read the textbook until you master the concepts. When you do the exercises, you should check that they are right and if not, try them again, or seek help from the instructor or a tutor. Many problems will be done during the lectures (with full solutions posted in the lecture notes). A great way to learn mathematics or statistics is (after the lecture) to cover up the solution, then work as much of the problem as possible on your own, only glancing at the solution when you get stuck or complete it. If you get stuck, then redo the solution until you get it right. (For more ways to be successful in this course, see Helpful Hints at the end of this document.)

Show Your Work: Show your work on all quizzes/exams; otherwise, it is impossible forme to give partial credit if the final answer is wrong. There is no point in just giving the final answer.

Quiz Policy: Throughout the semester, you can expect both announced (during the class/ not on canvas) and unannounced quizzes on a weekly basis. Each quiz will last approximately fifteen to twenty minutes. It's crucial to demonstrate your problem-solving process rather than just providing answers. While I aim to give at least one lecture's notice before a quiz, I cannot guarantee it.

Please be prepared for quizzes at any time, ensuring you've reviewed the material regularly. As a helpful hint, anticipate a quiz as soon as we've covered a minimum of one, and at most, two sections. While some quizzes will be announced in advance, the element of surprise is intentional to encourage consistent preparation. Let's refer to them as “spontaneous assessments” rather than "pop-up quizzes" to better reflect their purpose.

Exams and Final Exam: During the semester there will be three in-class examinations which will be given during the regular lecture hour. At the end of the semester (during the Final Exam period) there will be a two-hour final comprehensive examination. Tests will be closed-book and closed-notes. Give complete answers--show your work. All electronic devices as well as mobile phones should be turned off and put away during class time, recitation meetings, quizzes, mid-term exams and the final exam. You are not allowed to use a  second device during exams/quizzes in any virtual examination. Please see “Attendance” and “Missing an Examination” sections regarding exam attendance policies.

In Virtual mode, for examinations, your camera must be set such that I can see both you and the desk that you’rewriting on… Best case is to set two cameras; one shows you and the other set toward your desk.

Examination Dates: Actual exam dates to be determined. Once the dates are announced, please MARK THE EXAM DATE(S) IN YOUR CALENDAR AND AVOID ANY CONFLICTS. Please see “Attendance” and “Missing an Examination” sections regarding exam attendance policies. (IMPORTANT NOTE: The exact date/time of the final exam is determined by the Registrar’s Office and will be posted around mid-semester. Students must be aware that travel plans/a purchased airline ticket is NOT a valid excuse to miss any examinations as well as the final exam, so no makeup exam will be granted under these circumstances; and it is school policy that no one be permitted to take the final exam early.) Failure to take the final exam will result in a grade of “0” for the final, regardless of other grades.

Exam 1                      On Monday; June 10th, includes Set Theory

Exam 2                      On Wednesday; June 27th, includes Counting & Probability-- Expected Value Exam 3                      On Wednesday; July 10th, Starting Distributions - End of July 8th  Lecture

Final Examination     On July 17th ; 2:00-4:00 PM via Zoom- Comprehensive, on all chapters

   Key to quizzes and exams, along with their partial points, will be posted on Canvas  File  Exam Key folder.

   You MUST pick up your graded examination papers from recitation or your TA during office hours.

   It’s your responsibility to check your graded paper and if there is any missing point/mistake, come to my office (during office hours) with your paper and let me go over it with you.

   Failure to take above action immediately (max. of a weeks after examination’s being poseted), will turn your missed grade into “0” and I will not accept any complaint/excuse.

   All makeup examinations must be done within a week of the original examination's date.

   The most effective approach to answering examination questions is to first write down the relevant formula or equation. Then, accurately substitute the provided values or information into the equation without the need to simplify or calculate unless the question specifically requires that value for other parts of the problem. This method ensures that you don't waste time on unnecessary calculations and helps you focus on providing the most precise and relevant information to earn full credit for your response.

Final Exam for this course is usually up to 2 hours.

There is NO Final Exam rescheduling.

Cheating: If you are caught cheating during an exam/quiz, you will get 0 on the exam/quiz. In addition, upon Department request, I must fill out an Academic Integrity form on you.

Grading Policies: Your final grade will be determined as follows:

Class work/participation: 6%

Exams I, II, and III: 42%

Quizzes: 20%

Final: 32%

Grading Questions: Questions regarding the grading of exams or homework must be brought to me outside of class. No such issues will be addressed during the regular lecture hour. If you have a question or concern, please see me during office hours or email me to make an appointment.

If your semester scores end on a 9, e.g., 59, 69, 79 or 89, I will round it up one point.

Grading Scale: The final course grade is determined using the following scale:

89.5- 100% = A                       79.5-84.49% = B                      69.5-74.49% = C                     0-59.49 % = F

84.5-89.49% = B+                  74.5-79.49% = C+                    59.5-69.49% = D

SPECIAL OFFER! I do NOT curve grades at the end of the semester. However, in order to motivate you to improve your grade throughout the semester, I am providing you with the following offers/opportunities:

   If you have:

•    90% or above out of all quizzes and exams during the semester by the last day of the classes,

•    No more than 2 absences (Lecture or Recitation) during the semester, and

•    90% or above on class participation

•    Completing the Rutgers SIRS survey for this course at the end of the semester.

No need to take the final exam, you will have earned your “A”.

The above offer is NOT combinable with any other offer/extra points.

OTHERWISE

   You can qualify for each of the following bonuses by

•    Extra Credit: Students who attend either my or a TA’s regular office hours will be able to obtain extra credit (up to 4%). You will receive 0.04% extra credit for each time you attend tutoring: up to 2% credit per 5 weeks and up to 4% per semester. No other extra credit will be available at the end of the semester.

You will be eligible for the above extra point if you bring a question on a relative problem to the concept of our course along with your work/thoughts on the problem (not forme to solve it for you). Once I question you on the concepts, you show me

you reviewed the materials for that.

•    For those students who work very well:

1.   I will drop your lowest grade quiz (excluding any zeros received for cheating).

2.   To improve your grade, the lowest exam’s grade (excluding any zeros received for cheating or missing the exam), let say Exam X, will be substituted with the percentage you get in Final on the problems of the same Chapters as Exam X, IF AND ONLY IF