Summary: This page describes basic course information such as meeting times and locations, subject content and format, assessment materials, and the names and contact details of the lecturer.

Lecturer: Dr Abdollah Khodkar

Office: STV 312F     E-mail: ak@maths.uq.edu.au     Web Site: www.maths.uq.edu.au/~ak

Tel Numbers: 438-7365 (W), 452-2705 (H), 438-8781 (Math Department)

Lectures: Monday, Wednesday, Thursday and Friday 1:00pm. - 1:50pm. in Room STV 126.

Office hours: 11am. - 12noon. Monday, Wednesday, Thursday and Friday or by appointment.

Prerequisites: A grade C or better in MAT175 is required. MAT260 is a 4 semester hours course.

Objective

Today an increasing proportion of the applications of mathematics involves discrete rather than continuous models. The main reason for this trend is the integration of the computer into more and more of modern society. The course is concerned with the discrete, that is, finite processes and sets of elements that can be listed. This contrasts with calculus, which has to do with infinite processes and intervals of real numbers. This course is an introduction to discrete mathematics.

In this course we study counting problems, generating functions, recurrence relations, inclusion-exclusion, graphs, matching and covering, pigeonhole principle and applications.

Resources

The set text for this subject is

Discrete mathematics (third edition) by John A. Dossey, Albert D. Otto, Lawrence E. Spence and Charles Vanden Eynden, Addison-Wesley Educational Publishers Inc.

Assignments will be set from this book. It will be expected that you obtain access to a book either through purchase or use of the reserve copies.

If you wish to read more books on Discrete Mathematics, then the following ones are recommended for reference. They are all available in the library.

1. V.K. Balakrishnan, Introductory discrete mathematics, QA39.2 B357 1996.
2. S.S. Epp, Discrete mathematics with applications, QA39.2 E65 1995.
3. W.M. Dymacek and H. Sharp, Jr., Introduction to discrete mathematics, QA39.2 D95 1998.

4. N. Biggs, Discrete mathematics, QA76.9.M35 B54 1985.

Tentative Content Schedule

1. Chapter 1: An Introduction to Combinatorial Problems and Techniques (1 week)

The Time to Complete a Project; A Matching Problem; A Knapsack Problem; Algorithms and Their Efficiency.

2. Chapter 2: Sets, relations, and Functions (3.5 weeks)

Set Operations; Equivalence Relations; Congruence; Partial Ordering Relations; Functions; Mathematical Induction; Application.

3. Chapter 3: Graphs (1.5 weeks)

Graphs and Their Representations; Paths and Circuits; Shortest Paths and Distance; Coloring a Graph; Directed Graphs and Multigraphs.

4. Chapter 4: Trees (Sections 4.1 through 4.4) (1 week)

Properties of Trees; Spanning Trees; Minimal and Maximal Spanning Trees; Depth-First Search; Rooted Trees.

5. Chapter 5: Matching (1.5 weeks)

Systems of Distinct Representative; Matching in Graphs; A Matching Algorithm; Applications of the Algorithm; The Hungarian Method.

6. Chapter 6: Network Flows (1.5 weeks)

Flows and Cuts; A Flow Augmentation Algorithm; The Max-Flow Min-Cut Theorem; Flows and Matching.

7. Chapter 7: Counting Techniques (Sections 7.1 through 7.6) (2 weeks)

Pascal's triangle and the Binomial Theorem; Three Fundamental Principles; Permutations and Combinations; Arrangements and Selections with Repetitions; Probability; The Principle of Inclusion-Exclusion; Generating Permutations and r-Combinations.

8. Chapter 8: Recurrence Relations and Generating Functions (Sections 8.1 through 8.3) (1.5 weeks)

Recurrence Relations; The Method of Iteration; Linear Difference Equations with Constant Coefficients.

Assessment

Course assessment will consist of the following components:

1. A comprehensive final examination worth 30% of the final grade.
2. Four one-hour tests conducted during the scheduled teaching session worth 50% of the final grade.
3. A set of two weekly assignments worth 20% of the final grade.

Test One: 1:00pm. - 1:50pm. Monday September 10, Room STV 126.

Test Two: 1:00pm. - 1:50pm. Monday October 1, Room STV 126.

Test Three: 1:00pm. - 1:50pm. Monday October 29, Room STV 126.

Test Four: 1:00pm. - 1:50pm. Monday November 19, Room STV 126.

Final Exam: 1:00pm. - 3:40pm. Thursday December 13, Room SH 310.

Attendance at exams is required. If you must miss an exam for a legitimate reason, you must notify me in advance either by calling my office before class or leaving a message in the Math Department Office.

Students with disability

Any student needing to arrange a reasonable accommodation for documented disability should contact Disability Concerns at 350 Fell Hall, 438-5853 (voice) or 438-8620 (TDD).