Webpage of

Umar Faiz

Last updated

Dec 31, 2008

Academics

Program Name:

Bachelor in Computer and Information Sciences

Instructor:

Umar Faiz
Dept. of Computer and Information Sciences
Office: B-206
email: umarfaiz (at) pieas edu pk

Course Code/Credit hrs:

(CIS 143) Discrete Mathematics (3 Credit hrs)
1 Contact Hour is equivalent to 60 minutes. 1 Lab credit is equivalent to 3 contact hours.

Class Coordinates:

Room No# B-106
Monday, Tuesday & Friday

Learning outcomes:

On the completion of this course, the student should be able:

• To develop fundamental knowledge of basic definitions and concepts, and the role of discrete mathematics in computer science.
• To develop knowledge of more complicated definitions and concepts, and application in situations similar to known ones.
• To understand the role of formal definitions, formal and informal mathematical proofs, and underlying algorithmic thinking, and be able to connect the theory to computing applications.
• To understand new situations and definitions, derive their formal meaning, and relate them to existing knowledge.
• To develop the ability to model actual situations in a mathematical way and derive useful results.

Course Description:

Topics include functions, relations, sets, simple proof techniques, Boolean algebra, propositional logic, digital logic, elementary number theory, analysis of algorithms, graphs, computability, finite-state machines, the fundamentals of counting, and a brief introduction to complexity theory. The course emphasizes for the application of the mathematics within computer science. The analysis of algorithms requires the ability to count the number of operations in an algorithm. Recursive algorithms depend on the solution to a recurrence equation, and a proof of correctness is provided by mathematical induction. The knowledge of Boolean algebra requires the knowledge of digital circuit. The understanding of sets, graphs, trees and other data structures is pivotal to software engineering. Logic is used in AI research in theorem proving and in database query systems. Proofs by induction and mathematical proof are very important in theory of computation, compiler design and formal grammars.

Course Objectives:

• To learn the fundamental concepts, notations, and terminologies in discrete mathematics
• To understand introductory logic and techniques of formal proofs
• To develop knowledge of the fundamental structures: Functions (surjections, injections, inverses, composition); relations (reflexivity, symmetry, transitivity, equivalence relations); sets (Venn diagrams, complements, Cartesian products, power sets); pigeonhole principle; cardinality and countability
• To develop the knowledge of Boolean algebra
• To develop the knowledge of propositional logic and digital logic
• To understand the fundamentals of elementary number theory
• To understand the basics of counting, the recurrence relations, proofs, mathematical induction and their applications
• To understand and solve problems involving graphs, paths, circuits, graph coloring, directed graphs, shortest path algorithms
• To understand and solve problems involving counting techniques such as permutations, combinations, binomial theorem, and probability.

Pre-requisites

Discrete Mathematics

Textbooks/ Course URL

Course Text:

• T. Koshy, “Discrete Mathematics with Applications,” Elsevier, 2004
• R. H. Rosen, Discrete Mathematics and its Applications, 6th Edition, McGraw-Hill 2007

Recommended Books:

• K. P. Bogart, Discrete Mathematics, D. C. Heath, 1988.
• J. Bradley, Introduction to Discrete Mathematics, Addison-Wesley, 1988.
• S. Roman, An Introduction to Discrete Mathematics, 2nd Edition, Harcourt Brace Jovanovich, New York, 1989.
• J. A. Dossey, et al, Discrete Mathematics, HarperCollins, Glenview, Illinois, 1987.
• K. A. Ross and C. R. B. Wright, Discrete Structures, 3rd ed., Prentice-Hall, Englewood Cliffs, NJ, 1992.
• B. Kolman, et al, Discrete Mathematical Structures, 4th edition, Prentice-Hall, 2000.
• R. P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th ed., Pearson, 2004.

Course URL:

http://www.pieas.edu.pk/umarfaiz

Assignments:

Assignments represent your opportunity to learn the material and you are not responsible for mastery of the material until the midterm and final exams. Thus, assignment solutions themselves are not graded. Hands-on practice is necessary to achieve the required level of understanding and technical ability. Exercises are assigned that help achieve these objectives. It is strongly advised to attempt all assigned exercises to familiarize yourselves with the concepts and techniques.

Lectures, Tutorials & Attendance Policy:

Teaching Method(s):
Lectures, Tutorials
Teaching Media: Slides, handouts
There will be 48 sessions of 60 minutes each. 80% attendance is mandatory

Grading/Grading Policy:

Quizzes/Assignments [20%]
Sessional I/Sessional II [30%]
Final Exam [50%]

(Grades will be given as per PIEAS’ Policy (see prospectus for further details)
There will be absolutely no makeup quizzes. Makeup midterm will only be allowed in case of extreme emergency. Contact the instructor as soon as the emergency permits to discuss possible course of action depending on the extremity of the emergency. For credit all assignments must be turned in time. Late assignments will not earn any credit but to get a passing grade all assignments must be eventually turned in.

Rules and Regulations:

In addendum to Institute’s policy following rules will be strictly adhered to:
Attendance: Students are expected to attend course sessions. In case of any absence, students are responsible to make up for the course covered in the missed session. Attendance profile is consistently compiled and updated at the department and it is mandatory to meet the minimum requirements of 80% to qualify for appearance in the final examination.
Class Behaviour: Cell phones must be turned off when the student enters the classroom. Disruption of class by a cell phone may lead to expulsion from the class.
Academic Honesty: Academic integrity is the foundation of the academic community. Each student has the primary responsibility for being academically honest, students are advised to read and understand all sections of this policy relating to standards of conduct and academic life.
Plagiarism: Plagiarism involves the use of quotations without quotation marks, the use of quotations without indication of the source, the use of another's idea without acknowledging the source, the submission of a paper, laboratory report, project, or class assignment (any portion of such) prepared by another person, or incorrect paraphrasing.

Topics Coverage:

• Introduction, Logic, Propositional Equivalences, Predicates and Quantifiers (Lectures 1-7)
• Sets, Set Operations, Cardinality, Recursively Defined sets (Lectures 8-12)
• Functions, Special functions, Properties of functions, Pigeonhole principle, Composition of functions (Lectures 17-20)
• Sequences and Summations, Matrices, Division Algorithm, Mathematical induction
• Recursive Definition, Recursive relations, Recursive Algorithms, Solving Recurrence Relations, Binary Trees (Lectures 21-24)
• Counting, Principles of Counting, Permutations, Combinations, Permutations and Combinations with Repetitions (Lectures 25-28)
• Relations & their Properties, Equivalence Relations, Closures of Relations, Transitive Closure, Partial Ordering (Lectures 29-32)
• Introduction to Graphs, Graph Terminology, Representation of Graphs and Graph Isomorphism, Connectivity, Euler and Hamilton Paths (Lectures 33-37)
• Trees and Applications, Tree Traversal, Spanning Trees, Minimum Spanning Trees, MST Algorithms, Directed Graphs, Weighted Digraphs, Djikstra’s Algorithm (Lectures 38-43)
• Formal Languages, Models of Computation, DFA, NFA (Lectures 44-46)
• Boolean Algebra, Combinatorial Circuits (Lectures 47-48)

Weekly Course Plan (Table of Specifications):