Scribd
Upload
26 views3 pages

Dynamichandout Sep17

Gffthfeyhg

Uploaded by

jainil200512
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
26 views3 pages

Dynamichandout Sep17

Gffthfeyhg

Uploaded by

jainil200512
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

CS F222: Discrete Structures for Computer Science

Dynamic Handout - SEM I, 2024-25


(Last Updated: Sep 17, 2024)

Instructors: Prof. Bharat M. Deshpande, Prof. Siddharth Gupta (IC)


Email: bmd@goa.bits-pilani.ac.in , siddharthg@goa.bits-pilani.ac.in
Lecture Timings: 4:00 pm - 4:50 pm (Mon, Wed); 10:00 am - 10:50 am (Fri) [LT2]
Tutorial Timing: 3:00 pm - 3:50 pm (Thu) [LT2]
Office Hours: Walk-in (Drop an email first to make sure we are in the office)

Course Description
Sets & operation on sets; relations & equivalence relations; number theory; weak & strong form of mathe-
matical induction; principle of inclusion & exclusion, pigeonhole principle; recurrence relations & generating
functions; digraphs & graphs, graph isomorphism & sub-graphs, spanning trees, Euler & Hamiltonian graphs,
planar graphs, chromatic numbers & graph coloring; groups; Lagrange theorem finite groups; Rings & Fields.

Course Objectives
• Understand the notion of mathematical thinking, mathematical proofs, and algorithmic thinking and
be able to apply them in problem-solving.
• Use algebraic techniques to analyze basic discrete structures and algorithms effectively.
• Understand asymptotic notation and its significance and be able to use it to analyze asymptotic
performance for some basic algorithmic examples.

• Understand some basic properties of graphs and related discrete structures and be able to relate these
to practical examples.

Course Outline

Topics Main Subtopics No. of


lectures
Overview Course Organization & Overview 1
Methods of Proofs Exhaustion, Counterexample, Direct, Contrapositive, Contradic- 2
tion (Indirect), Cases
Set Theory Sets, Subsets, Power Sets, Set Operations, Set Identities, Cardi- 5
nality
Relations Relations and their properties, Equivalence Relations, Partial, 6
Well and Total Orderings
Induction & Recursion Weak and Strong Induction, Recursion, Pigeonhole Principle 4
Recurrence Relation Recurrence Relations and Modeling with Recurrence Relations, 6
Solving Linear Recurrence Relations with constant coefficients,
Generating Functions
Graphs Graphs and their representations, Isomorphism, Connectivity, 8
Planar Graphs. Graph Coloring
Group Theory Groups and Examples of Groups, Cyclic Groups, Subgroups, 8
Rings and Fields, Finite Fields and Latin Squares

1
Textbook & Reference Book
T: Kenneth H. Rosen: “Discrete Mathematics and Its Applications”, Seventh Edition, Tata McGraw Hill
Education Private Limited.
R: Norman L. Biggs: “Discrete Mathematics”, Oxford University Press.

Lecture Schedule
Date Lecture Topic Reference
Aug 2 1 Overview: Organization & Overview NA
Aug 5 2 Methods of Proofs: Exhaustion, Counterexample, Direct, Con- T: 1.7, 1.8
trapositive, Contradiction (Indirect)
Aug 7 3 Methods of Proofs: Contrapositive, Contradiction (Indirect) T: 1.8
Aug 9 4 Methods of Proofs: Cases; T: 1.8, 2.1
Set Theory: Set Notations, Universal Set, Venn Diagram
Aug 12 5 Set Theory: Subsets, Power Sets, Set Operations, Set Identities T: 2.1, 2.2
Aug 14 6 Set Theory: Finite and Infinite Sets, Cardinality, Functions T: 2.3, 2.5
Aug 16 7 Set Theory: Cardinality, Countable Set T: 2.5
Aug 21 8 Set Theory: Countable and Uncountable Sets T: 2.5
Aug 23 9 Relations: Relations and Their Properties T: 9.1
Aug 28 10 Relations: Relations and Their Properties T: 9.1
Sep 2, 4, 6, 9 11 - 14 Relations: Representing Relations Using Matrices, Equivalence T: 9.3, 9.5,
Relations, Partial Orderings (except Lattices) 9.6
Sep 11 15 Induction & Recursion: Mathematical Induction T: 5.1
Sep 13 16 Induction & Recursion: Strong Induction T: 5.2

Grading Policy
• Midsem: 30% - Closed Book - October 8, 2024 (9:30 am - 11:00 am)
• Compre: 35% - Open Book - December 11, 2024 (10 am - 1 pm)
• Weekly Homeworks: 10%
– Submission Format - Handwritten (maximum of 2 A4 sheets).
– Marks for Submitting all the homeworks - 3%.
– One homework chosen at random will be graded for everyone. (Maximum marks - 7%)
• Quizzes: 25% - Closed Book (Best 3 out of 4)
– Q1 - Aug 24, 2024 (Saturday) (10:00 am - 11:00 am) - LT2
– Q2 - Sept 21, 2024 (Saturday) (9:30 am - 10:30 am) - LT2
– Q3 - Oct 26, 2024 (Saturday) (5:00 pm - 6:00 pm) - CC [MCQ]
– Q4 - Nov 23, 2024 (Saturday) (10:00 am - 11:00 am) - CC [MCQ]

Makeup Policy
• Quizzes - No makeup.
• Midterm - Only in genuine and exceptional cases of absence.
• Comprehensive - Contact Associate Dean AUGSD.

2
Malpractice Policy
The course has a strict policy against any form of academic dishonesty during the examinations and as-
sessments. Any student found guilty of such misconduct will face disciplinary action, including receiving
negative marks equivalent to the weightage of that assessment/exam.

You might also like