CSN-106 Discrete Structures
Spring 2021-22
Instructor: Balasubramanian Raman
Office: S-227, CSE Building
Class Meeting Time: Mondays, Tuesdays and Thursdays (05:05-06:00 pm).
Class Room: LHC 104 and Microsoft Teams (first 5 classes)
Office Hours: Wednesdays, Fridays 11:00 a.m. - 1:00 p.m. and by appointment
TAs: N. Kishor Babu, Anshul Pundhir, Nitin Tyagi (PhD students), Preeti and Pushpamanjari Ramesh
Jupudi (M.Tech students)
Email: first four letters of first name at cs dot ac dot in
Announcements
July 11, 2022: Grades have been displayed.
July 01, 2022: End Term Examinations (ETE).
June 23, 2022: Quiz 2.
June 14, 2022: Assignment 7 has been posted.
May 30, 2022: Assignment 6 has been posted.
May 23, 2022: MTE marks have been displayed.
May 21, 2022: Quiz 1.
May 11, 2022: Mid-Term Examinations (MTE).
May 02, 2022: Assignments 4 and 5 have been posted.
April 27, 2022: Assignment 3 has been posted.
April 12, 2022: Assignment 2 has been posted.
April 05, 2022: Assignment 1 has been posted.
March 24, 2022: Classes have begun.
Course Objectives, Learning Outcomes and Prerequisites
To understand the basic concepts of Set Theory, Graph Thory, Logic, Abstract Algebra and Number Theory.
To analyze logical propositions via truth tables.
To prove mathematical theorems using mathematical induction.
To understand sets and perform operations and algebra on sets.
To determine properties of relations, identify equivalence and partial order relations, sketch relations.
To Identify functions and determine their properties.
To Define graphs, digraphs and trees, and identify their main properties.
To evaluate combinations and permutations on sets.
Prerequisites: NIL.
Evaluation Components
- Term tests/quizzes (10%)
- Assignments (10%)
- Class participation (5%)
- Mid-Term Examination (25%)
- End Term Examination (50%)
Lecture Notes
01. Introduction to Linear Graphs and Applications (24/03/2022)
02. Incidence, Adjacent, Degree and Graph Isomorphism (28/03/2022)
03. Subgraph, Walk, Paths, Circuits, Connected & Disconnected Graphs and Components (29/03/2022)
04. Components and related theorems (31/03/2022)
05. Euler Graphs, Representation of Graphs, Eigenvalues of a graph, Bipartite Graphs (02/04/2022)
06. Complete Bipartite Graphs, Operations on Graphs and Arbitrary Traceable Vertices (04/04/2022)
07. Eulerian, Hamiltonian graphs and related theorems (06/04/2022)
08. Trees and Related Theorems (07/04/2022)
09. Distance and Centers in a Tree, Rooted and Binary Trees (18/04/2022)
10. Height of the Binary Tree, Spanning Tree, Directed Graph and Shortest Path Problem (19/04/2022)
11. Kruskal's Algo', Prim's Algo. and DFS (21/04/2022)
12. BFS and Set Theory: Functions (25/04/2022, Extra Class- 9:00 - 10:00 am)
13. Countable Sets: Theorems (25/04/2022)
14. Countable and Uncountable Sets (26/04/2022)
15. Metric Space (28/04/2022)
16. Bounded Set, Infimum & Supremum and Open ball (Open Sphere) in a Metric Space (30/04/2022)
17. Problems in Open ball (Open Sphere) in a Metric Space (02/05/2022)
18. Open Sets (17/05/2022)
19. Examples of Open Set, Introduction to interior of a Set and Closed Set (19/05/2022)
20. Surprise Quiz and Solution, Closed ball and Closed Set (21/05/2022)
21. Number Theory: Division Algorithm (23/05/2022)
22. Theorems on Divisibility, Congruences and related theorems (24/05/2022)
23. Some more theorems on Congruences (26/05/2022)
24. Euler's phi function, Fermat's theorem (28/05/2022)
25. Chinese Remainder theorem (30/05/2022)
26. Groups (31/05/2022)
27. Theorems on Groups and Semi-groups (06/06/2022)
28. Monoid and Subgroups (09/06/2022)
29. More on Centre of a Group and Cyclic Group (13/06/2022, Extra Class- 10:00 - 11:00 am)
30. Rings (13/06/2022)
31. Vector Spaces, Introduction to Logic and Propositional Logic (14/06/2022)
32. Predicate Logic (16/06/2022)
33. Negation of Quantified Propositions and Propositions with Multiple Quantifiers (20/06/2022)
34. Quiz 2 (23/06/2022)
Assignments
01. Assignment 1 (Posted on 05/04/2022, due on 21/04/2022)
02. Assignment 2 (Posted on 12/04/2022, due on 26/04/2022)
03. Assignment 3 (Posted on 27/04/2022, due on 20/05/2022)
04. Assignment 4 (Posted on 02/05/2022, due on 27/05/2022)
05. Assignment 5 (Posted on 02/05/2022, due on 03/06/2022)
06. Assignment 6 (Posted on 30/05/2022)
07. Assignment 7 (Posted on 14/06/2022)
- There will be five to eight assignments.
- Late assignments will be accepted, with a 10% penalty per day, up to five days.
- Submission procedure and other requirements will be stated in individual assignments.
- Students are responsible for backing up and protecting their work.
Examinations
01. Mid Term Examination (Held on 11/05/2022, 09:00 to 10:30 am), Solution (12/05/2022)
02. Quiz 2 (23/06/2022, 5-6 pm)
03. End Term Examination (Held on 01/07/2022, 09:00 am to 12:00 noon), Solution (06/07/2022)
Recommended Study Material
The following will be used as a reference/text book for this course:
1. Herstein, I., Abstract Algebra, Pearson Education. 2005.
2. Harary, F., Graph Theory, Narosa Publishing House. 2001.
3. Huth, M. and Ryan, M., Logic in Computer Science: Modeling and
Reasoning About Systems, Cambridge University Press. 2005.
4. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, 1979.
Instructor: Balasubramanian Raman
Office: S-227, CSE Building
Class Meeting Time: Mondays, Tuesdays and Thursdays (05:05-06:00 pm).
Class Room: LHC 104 and Microsoft Teams (first 5 classes)
Office Hours: Wednesdays, Fridays 11:00 a.m. - 1:00 p.m. and by appointment
TAs: N. Kishor Babu, Anshul Pundhir, Nitin Tyagi (PhD students), Preeti and Pushpamanjari Ramesh Jupudi (M.Tech students)
Email: first four letters of first name at cs dot ac dot in
Office: S-227, CSE Building
Class Meeting Time: Mondays, Tuesdays and Thursdays (05:05-06:00 pm).
Class Room: LHC 104 and Microsoft Teams (first 5 classes)
Office Hours: Wednesdays, Fridays 11:00 a.m. - 1:00 p.m. and by appointment
TAs: N. Kishor Babu, Anshul Pundhir, Nitin Tyagi (PhD students), Preeti and Pushpamanjari Ramesh Jupudi (M.Tech students)
Email: first four letters of first name at cs dot ac dot in
Announcements
July 11, 2022: Grades have been displayed.July 01, 2022: End Term Examinations (ETE).
June 23, 2022: Quiz 2.
June 14, 2022: Assignment 7 has been posted.
May 30, 2022: Assignment 6 has been posted.
May 23, 2022: MTE marks have been displayed.
May 21, 2022: Quiz 1.
May 11, 2022: Mid-Term Examinations (MTE).
May 02, 2022: Assignments 4 and 5 have been posted.
April 27, 2022: Assignment 3 has been posted.
April 12, 2022: Assignment 2 has been posted.
April 05, 2022: Assignment 1 has been posted.
March 24, 2022: Classes have begun.
Course Objectives, Learning Outcomes and Prerequisites
To understand the basic concepts of Set Theory, Graph Thory, Logic, Abstract Algebra and Number Theory.
To analyze logical propositions via truth tables.
To prove mathematical theorems using mathematical induction.
To understand sets and perform operations and algebra on sets.
To determine properties of relations, identify equivalence and partial order relations, sketch relations.
To Identify functions and determine their properties.
To Define graphs, digraphs and trees, and identify their main properties.
To evaluate combinations and permutations on sets.
Prerequisites: NIL.
To analyze logical propositions via truth tables.
To prove mathematical theorems using mathematical induction.
To understand sets and perform operations and algebra on sets.
To determine properties of relations, identify equivalence and partial order relations, sketch relations.
To Identify functions and determine their properties.
To Define graphs, digraphs and trees, and identify their main properties.
To evaluate combinations and permutations on sets.
Prerequisites: NIL.
Evaluation Components
- Term tests/quizzes (10%)
- Assignments (10%)
- Class participation (5%)
- Mid-Term Examination (25%)
- End Term Examination (50%)
Lecture Notes
01. Introduction to Linear Graphs and Applications (24/03/2022)02. Incidence, Adjacent, Degree and Graph Isomorphism (28/03/2022)
03. Subgraph, Walk, Paths, Circuits, Connected & Disconnected Graphs and Components (29/03/2022)
04. Components and related theorems (31/03/2022)
05. Euler Graphs, Representation of Graphs, Eigenvalues of a graph, Bipartite Graphs (02/04/2022)
06. Complete Bipartite Graphs, Operations on Graphs and Arbitrary Traceable Vertices (04/04/2022)
07. Eulerian, Hamiltonian graphs and related theorems (06/04/2022)
08. Trees and Related Theorems (07/04/2022)
09. Distance and Centers in a Tree, Rooted and Binary Trees (18/04/2022)
10. Height of the Binary Tree, Spanning Tree, Directed Graph and Shortest Path Problem (19/04/2022)
11. Kruskal's Algo', Prim's Algo. and DFS (21/04/2022)
12. BFS and Set Theory: Functions (25/04/2022, Extra Class- 9:00 - 10:00 am)
13. Countable Sets: Theorems (25/04/2022)
14. Countable and Uncountable Sets (26/04/2022)
15. Metric Space (28/04/2022)
16. Bounded Set, Infimum & Supremum and Open ball (Open Sphere) in a Metric Space (30/04/2022)
17. Problems in Open ball (Open Sphere) in a Metric Space (02/05/2022)
18. Open Sets (17/05/2022)
19. Examples of Open Set, Introduction to interior of a Set and Closed Set (19/05/2022)
20. Surprise Quiz and Solution, Closed ball and Closed Set (21/05/2022)
21. Number Theory: Division Algorithm (23/05/2022)
22. Theorems on Divisibility, Congruences and related theorems (24/05/2022)
23. Some more theorems on Congruences (26/05/2022)
24. Euler's phi function, Fermat's theorem (28/05/2022)
25. Chinese Remainder theorem (30/05/2022)
26. Groups (31/05/2022)
27. Theorems on Groups and Semi-groups (06/06/2022)
28. Monoid and Subgroups (09/06/2022)
29. More on Centre of a Group and Cyclic Group (13/06/2022, Extra Class- 10:00 - 11:00 am)
30. Rings (13/06/2022)
31. Vector Spaces, Introduction to Logic and Propositional Logic (14/06/2022)
32. Predicate Logic (16/06/2022)
33. Negation of Quantified Propositions and Propositions with Multiple Quantifiers (20/06/2022)
34. Quiz 2 (23/06/2022)
Assignments
01. Assignment 1 (Posted on 05/04/2022, due on 21/04/2022)02. Assignment 2 (Posted on 12/04/2022, due on 26/04/2022)
03. Assignment 3 (Posted on 27/04/2022, due on 20/05/2022)
04. Assignment 4 (Posted on 02/05/2022, due on 27/05/2022)
05. Assignment 5 (Posted on 02/05/2022, due on 03/06/2022)
06. Assignment 6 (Posted on 30/05/2022)
07. Assignment 7 (Posted on 14/06/2022)
- There will be five to eight assignments.
- Late assignments will be accepted, with a 10% penalty per day, up to five days.
- Submission procedure and other requirements will be stated in individual assignments.
- Students are responsible for backing up and protecting their work.
Examinations
01. Mid Term Examination (Held on 11/05/2022, 09:00 to 10:30 am), Solution (12/05/2022)02. Quiz 2 (23/06/2022, 5-6 pm)
03. End Term Examination (Held on 01/07/2022, 09:00 am to 12:00 noon), Solution (06/07/2022)
Recommended Study Material
The following will be used as a reference/text book for this course:1. Herstein, I., Abstract Algebra, Pearson Education. 2005.
2. Harary, F., Graph Theory, Narosa Publishing House. 2001.
3. Huth, M. and Ryan, M., Logic in Computer Science: Modeling and Reasoning About Systems, Cambridge University Press. 2005.
4. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, 1979.