Course Code:                           MATH 2276

Course Title:                            Introduction to Discrete Mathematics

Course Type:                           Core

Level:                                      2

Semester:                                1               

No. of Credits:                          3

Pre-requisite(s):                       MATH1141 and Math 1152

 

 

Course Rationale

 Mathematics is an engaging field that is rich in beauty that provides potent tools for all fields of applied science. The term “discrete” signifies areas of mathematics normally thought of as not involving calculus. Such a viewpoint is fundamentally misguided, but serviceable for the purpose of this course. Discrete Mathematics is about the study of mathematical structures that are discrete, such as graphs and networks, in contrast to continuous, such as differentiability and limits. Concepts arising from the study of discrete mathematics are fundamental for all students and practitioners of mathematics. The central ideas and proofs emerging from this field have shaped human thought over the years.

This course serves to sharpen the analytical and critical reasoning skills of the student and to improve his/her ability to express mathematical ideas with coherence and clarity.

The importance of discrete mathematics lies in its applications. It plays an essential role in modeling the natural world, e.g. ., modeling the genome, and the technological world, e.g., routing on the internet. As well as being the core of modern computer science and operations research, it is commonly applied in cryptography, computer security, banking and auctions, coding theory, algorithms, theory of computing, social sciences and telecommunication.

The aims of the course include:

. Providing you with an academic perspective on discrete mathematics, addressing key topics in areas such as mathematics, discrete structures and algorithmic applications.

. Developing your ability to think rigorously and analytically to solve complex real-world problems, particularly using mathematical reasoning, combinatorial analysis, discrete structures.

. Equipping you with a range of technical and transferable skills that are relevant to your future career.

 

 

Course Description

Students who take this course will require a solid foundation of most topics that are examined in the level 1 courses Math 1141 and Math 1152.

We begin with a study of methods of proofs and discrete mathematical structures. Some basic definitions in combinatorics and graph theory are given. In such a situation recurrence relations are formulated but linear type ones are solved. The solutions of various problems in enumeration are expressed in terms of recurrences.

We introduce different general network structures and the models that generate them. Some of the notations and terminology of graphs are used that would lead to established properties of networks, combinatorial designs and the efficiency of the Hungarian algorithm.

 Assessment is designed to encourage students to work continuously with the course materials. Active learning will be achieved through weekly assignments and problem sheets allowing continuous feedback and guidance on problem solving techniques in tutorials and lectures. Assessment will be based on the weekly assignments and in-course tests followed by a final examination based on the whole course

 

 

Learning Outcomes

Upon successful completion of the course, students will be able to:

  • Write standard proofs.
  • Formulate problems that can be solved by computers.
  • Use combinatorial principles ,graph theory and associated ideas for the development of algorithms to solve applied problems.
  • Use Combinatorics and Graph Theory ideas in formulating network models and associated algorithms.
  • Give the importance and applications of combinatorial designs.

 

Content

  • Discrete Mathematical Structures:
  • Methods of Proof:
  • Formulation of Recurrences
  • Enumerative Problems in Combinatorics and Graph Theory
  • Combinatorial Designs
  • Graphs and Network Models ; Related Algorithms
  • Hungarian Algorithm

 

Teaching Methodology

 

Lectures: Two (2) lectures each week (50 minutes each).

Tutorials: One (1) weekly tutorial session (50 minutes of problem solving, based on theory

                covered during lectures).

 

 

Assessment

Coursework: 50%  - Two 20% Coursework examinations and 10% Assignments (based on ten assignments at 1 % each, given during the semester).

 

Final Examination: 50% (one 2  - hour written paper).

 

 

Course Calendar

 

Week

Lecture/Tutorial Topic

Assignments

1

Course Overview/Introduction

 

Discrete Mathematical Structures; Methods of Proof

Assignment #1

2

Methods of Proof;  Formulation of Recurrences

Assignment #2

3

Formulation of Recurrences;

Assignment #3

4

Enumerative Problems in Combinatorics and Graph Theory

Assignment#4

5

Enumerative Problems in Combinatorics and Graph Theory

Coursework Exam #1

6

Enumerative Problems in Combinatorics and Graph Theory ,Graphs and Network Models

Assignment #5

7

Graphs and Network Models

Assignment #6

8

Related Algorithms of Graph Models

Assignment #7

9

Related Algorithms of Network Models

Assignment #8

10

Combinatorial Designs

Assignment#9

11

Combinatorial Designs

Coursework Exam#2

12

Hungarian Algorithm

Assignment #10

13

Revision

-

 

Suggested Texts / References

 

Text Books:

  • Norman L.Biggs, Discrete Mathematics,Oxford University Press, ISBN: 978-0-19-850717-8,(2002).
  • Susanna S.Epp, Discrete Mathematics With Applications, Thomas Brooks/Cole.

ISBN: 978-0-495-39132-6.(2010).

                 

Reference Books:

  • D. B. West, Introduction to Graph Theory, Prentice Hall, ISBN 0-13-014400-2, 2001.