CS112 Discrete Mathematics

  • Course Outline

    This course covers essential mathematics for Computer Science. It emphasizes mathematical definitions and proofs as well as applicable methods. We broadly try to cover the following topics

    • Counting Principles
    • Combinatorics
    • Graph Theory
    • Abstract Algebra
  • Taught by:
  • Class Meetings
  • The necessary evil - marks, exam, etc.

    The evaluation for the course will be based on midterm test1, midterm test2, assignments and final exam. There will be 2-4 assignments that will carry weightage for your final evaluation. In addition, a number of problem sheets will be given which are for your practice, and in particular, solving them will be useful for getting good marks in the exams.

  • Some cautionary notes on tests, assignments and problem sheets

    This course is essentially a problem solving course, and so there will be lots of problems in the form of assignments and practice problems. Anything you hand in is assumed to be done by you on your own. If you had consulted any resource (including books, internet, or other persons), then please mention that in the work you hand in. Copying from any source without acknowledgement will result in unwanted consequences for everyone!

  • Supplementary materials
 

Number of Classes

Topics Covered

Part A

3

Problem Solving Strategies

  • The Invariance Principle
  • Coloring Proof
  • Basic number theory

4

Basic Counting

  • The Product Rule
  • The Sum Rule
  • Permutations and combinations
  • Occupancy Problems

3

Counting Technique

  • Principle of inclusion Exclusion
  • Pigeonhole principle

4

Recurrence relation
 

Number of Classes

Topics Covered

Part B

1

Introduction to Graph Theory

2

Matching

2

Coloring

2

Shortest Path

2

Connectivity

2

Trees

2

Planer Graphs

Part C

2

Propositional Logic

2

Induction

Part D

1

Introduction To Group Theory

2

Subgroups

2

Cosets

3

Homomorphisms and isomorphisms

1

Rings

Assignments

  • Applied Combinatorics by Fred Roberts, Barry Tesman
  • Graph Theory by Frank Harary
  • Algebra by Michael Artin