CSE 260

Discrete Structures in Computer Science

Introduction

Dr. Borzoo Bonakdarpour


Department of Computer Science & Engineering


General Information

Instructor: Dr. Borzoo Bonakdapour

   [email protected]

•   https://www/cse/msu.edu/borzoo

•   Twitter: @TheBorzoo

Lecture time: MWF, 3 – 4:20pm

Office hours: Tue 3 – 4pm (or by appointment)

Office: 2138 EB


General Information – Teaching Assistants

   Ritam Guha

•   Email: [email protected]

•   Office hour: Thu 4 – 5pm

   Tzu-Han Hsu

•   Email: [email protected]

•   Office hour: Tue 11am – 12pm

   Vincent Ragusa

•   Email: [email protected]

•   Office hour: Mon 11am – 12pm

   Anik Momtaz

•   [email protected]

•   Office hours: Thu 12 – 1pm


General Information – ULAs

   Adam Kasumovic

•   Email: [email protected]

•   Office hour: Sat 2 – 3pm

   Aaron Jonckheere

•   Email: [email protected]

•   Office hours: Fri 12 – 1pm

   Puyu Cai

•   Email: [email protected]

•   Office hour: Wed 5 – 6pm


Course Description

   CSE 260: Discrete Structures in Computer Science

   Prerequisite: One of the following:

•   MTH 126 (Survey of Calculus II)

•   MTH 133 (Calculus II)

•   MTH 153H (Honors Calculus II)

•   LBS 119 (Calculus II)

   Description: Propositional and first order logic. Equivalence, inference and method of proof. Mathematical induction, diagonalization principle. Basic counting. Set operations, relations, functions. Grammars and finite state automata. Boolean algebra. Truth tables and minimization of Boolean expressions. Applications to computer science and engineering.


Continuous vs. Discrete Mathematics

   Continuous Math

•   Math based on the real numbers

•   Use topology to study the idea of shape, closeness, etc

•   Use differential equations to study how things change

   Discrete Math

•   Distinct values

•   Use graph theory to study relations between objects

•   Use recurrence relations to study how things change


Course Motivation & Objectives

   Motivation

•   The role of discrete mathematics in the study of computer science is analogous to the role that calculus plays in physics or in the engineering disciplines

•   It allows us to defifine, describe, and reason about complex systems.

   Objectives

•   Expose you to the mathematical concepts that form the basis for much of Computer Science.

•   Train you to analyze problems; think in a logical fashion; and communicate your reasoning in a clear and unambiguous manner.


Motivation

   Consider the following simple program:

1   if (x < 5) y = 2

2   else

3         if (x > 7) y = 3

4         else

5               if (x > 2) y = 4

6               else y = 3

   Can ever be set to 4?

•   is set to 4 if

    ∗ ≥ 5

    ∗ x ≤ 7, and

    ∗ x > 2


Applications of Discrete Math

•   Algorithm Design

•   Programming Languages Design

•   Compiler Design

•   Software Engineering & Formal Methods

•   Data Structures

•   Relational Database Theory

•   Complexity Theory

•   Security


Course Topics – Weeks

•   Propositional and predicate Logics, Proof Methods (3)

•   Set Theory (2)

•   Relations and their representations (1)

•   Algorithms (1)

•   Induction and recursion (2)

•   Number Theory (2)

•   Combinatorics (2)

•   Languages and grammars (if time permits)


Course Outcome (ABET)

•   Students will be skilled in propositional logic, including modeling English descriptions with propositions and connectives and doing truth table analysis.

•   Students will be conversant in predicate logic.

•   Students will be able to use various methods of proof, such as direct, proof by contradiction, and mathematical induction.

•   Students will be conversant in the concepts of sets and their refinements as relations and functions.

•   Students will be able to solve basic counting and combinatoric problems.


Source of Information

   Piazza

•   Most announcements will be posted on Piazza:

     ∗   https://piazza.com/class/kj4o9zd6we61yd

•   You should have received a notification that you are added to the class. If you have not, please contact me after class.

•   Visit piazza, including pinned notes on Piazza regularly. It is your responsibility to keep yourself updated.

   D2L

•   This will contain all videos, quizzes, exams, assignments, etc.

•   All grades will be posted on here.


Online Teaching Information

   These are not normal times. The most important thing to me is your health and safety. If you have any questions, concerns, issues, etc, you should always feel free to talk to me.

   No part of the course will require physical presence on campus. All lectures, meetings, office hours, exams, etc will be online.

   All lectures and office hours will be conducted over Zoom. You will receive a Zoom link before the first day of classes. If you don’t receive it for any reason, please send me an email:

•   https://msu.zoom.us/j/99982192117?from=addon

•   Meeting ID: 999 8219 2117

•   Passcode: 046088

   All lectures will be synchronous will also be posted online.

   I like to have interactive lectures and I to participate in lectures and office hours with open camera.


Class Structure

   Lectures MW 3 – 4:20pm

   on Fridays, alternatively, there will be

•   group homework assignment with TAs help, and

•   Q & A and sample problem solving by TAs.

•   Individual homework assignments

•   Announced and unannounced quizzes

•   Two mid-term and final exams

•   For honnors option, email me. 


Grading & Course Structure

•   Artendence: 5%

   Quizes (10%)

•   One announced and one unannounced quiz per module

•   90%+ average on all the quizzes will result in full credit

   Homework assignments (25%)

•   Each module will have an in-class group assignment (on Fridays) and an individual homework assignment.

   Exams (60%)

•   Mid-term 1 (20%) – Feb 22

•   Mid-term 2 (20%) – March 22

•   Final (20%) – April 28

•   All exams will be closed-book and noncumulative.

•   Any grading issues should be resolved by one week.


Grading Scale

93 – 100%
4.0
85 – 93%
3.5
80 – 84%
3.0
75 – 79%
2.5
70 – 74%
2.0
65 – 69%
1.5
60 – 64%
1.0

•   Curving may be applied based on the distribution of exams.

•   Homework assignments and quizzes will not be curved.


Class Etiquette

•   When attending the class, we ask you to observe a few simple rules which are meant to create a better learning environment.

•   Come to class at least 5-10 minutes early.

•   Once class begins, we expect students to pay attention and not read emails, texts, or talk, etc. Set your cell phones on silent.

•   Use your laptops only for Zoom. Do not multi-task.

•   At the end of every class, we will have a brief chat with one of the groups about difficulties for modules to be discussed in next class.


Textbook

•   Discrete Mathematics and its Applications

•   Kenneth H. Rosen

•   McGraw Hill

•   You should get this book only via Connect.

•   Online access is required. Physical copy is optional.


Textbook

•   Chapter 1: Logic and proofs

•   Sections 1.1 – 1.8

•   Chapter 2: Set, Functions, sequences, ...

•   Sections 2.1 – 2.5

•   Chapter 3: Algorithms

•   Sections 3.1 – 3.3

•   Chapter 4: Number theory

•   Sections 4.1 – 4.6

•   Chapter 5: Induction, Recursion

•   Sections 5.1– 5.5, 8.1 – 8.2

•   Chapter 6: Counting

•   Sections 6.1 – 6.4

•   Chapter 9: Relations

•   Sections 9.1 – 9.6

•   Chapter 13: Languages and Grammars (maybe)

•   Sections 13.1 – 13.3


Few Important Notes

•   Education is a joint activity. It needs work from us (Instructors, TAs) AND from you.

•   You need to

•   Attend the lectures

•   Read the textbook

     ∗   Use the smartbook features. Many past students have found it to be very useful

•   Ask questions when something is not clear

•   This needs to be done on a regular basis and not just before the exam.

•   Some students do find this class challenging

•   Some students think that because it does not involve programming, it is easy. This is not the case.

•   If you think this class will be easy, remember this is a math class.


Few Important Notes

•   A key requirement for this course is PRACTICE

•   Solve many many many problems

     ∗   At least all the relevant problems from the textbook where the solution exists

•   Solve practice exams to know what to expect.

•   In some cases, solutions are provided.

•   However, in some cases, we want you to come up with the solution and check with the TA

•   Note that we are human beings and can make mistakes. If you feel a solution is incorrect, please check with the TA

•   Some of the TA hours will be designated as ‘problem-solving’ sessions.

•   Some TA hours will be designated for 1-1 discussion only. Use these to deal with questions associated with grading etc.


Few Important Notes

•   You (alone) are responsible for keeping track of announcements, deadlines and the module number being covered in class

•   Create a system that works for you to keep track of it

•   Make sure to include any relevant information gathered through any source (e.g., email, piazza, in-class, etc)


Cheating Issues

•   Do not cheat

•   If you observe cheating, you are encouraged to report it to one of the instructors

•   If we suspect someone of cheating

•   We will file an ADR

     ∗   The ADR will stay on your record unless we are convinced of your explanation

•   If you have cheated and you take responsibility within a week of notification

     ∗   Your grade will be reduced by 0.5

•   If you do not take responsibility and we are convinced that that your explanation is invalid,

     ∗   Your grade will be 0.0

•   You can avail yourself of the formal grievance procedure if you disagree with our decision.


Academic Honesty

•   Article 2.3.3 of the Academic Freedom Report states that “The student shares with the faculty the responsibility for maintaining the integrity of scholarship, grades, and professional standards.”

•   In addition, the College of Engineering adheres to the policies on academic honesty as specified in General Student Regulations 1.0, Protection of Scholarship and Grades; the all-University Policy on Integrity of Scholarship and Grades; and Ordinance 17.00, Examinations. (See Spartan Life: Student Handbook and Resource Guide and/or the MSU Web site: www.msu.edu.)

•   Therefore, unless authorized by your instructor, you are expected to complete all course assignments, including homework, quizzes and exams, without assistance from any source.


Academic Honesty

•   You are expected to develop original work for this course; therefore, you may not submit course work you completed for another courses to satisfy the requirements for this course.

•   Also, you are not authorized to use sites such as the http://www.allmsu.com to complete any course work in CSE 260.

•   Students who violate MSU rules may receive a penalty grade, including–but not limited to–a failing grade on the assignment or in the course.

•   Contact your instructor if you are unsure about the appropriateness of your course work.


Academic Integrity

•   Academic Integrity is very important in this class and in this university.

•   It is important that students do their work on their own without help from anyone except the instructor or the teaching assistant.

•   Students are permitted to discuss the homework problems with each other. However, the work they turn in must be completely their own.

•   Obviously, no cooperation is permitted during examinations. Students violating this will be dealt with according to the university policy.


Spartan Code of Honor academic pledge

•   “As a Spartan, I will strive to uphold values of the highest ethical standard. I will practice honesty in my work, foster honesty in my peers, and take pride in knowing that honor is worth more than grades. I will carry these values beyond my time as a student at Michigan State University, continuing the endeavor to build personal integrity in all that I do.”

•   https://honorcode.msu.edu


To succeed in this course

•   Read the material and/or watch videos before class

•   Answer the questions posted about the given video

•   Read textbook ahead of the class

•   Do the homework

•   Ask questions in class, piazza, ...

•   Answer questions