FACULTY OF ARTS AND SCIENCES
DEPARTMENT OF MATHEMATICS
COURSE OUTLINE
Course Code / MATH134 / Course Title / Discrete Mathematics for Information Technology
Semester / 2012-2013Spring / Language / English
Category / AC (Area Core) / Level / First Year
Workload / 180 Hours / Teaching Format / 3 Hours Lecture, 1 Hour Tutorial
EMU Credit / (3,0,1) 3 / ECTS Credit / 6
Prerequisite(s) / None / Course Web /
Instructors(s) / Dr. Şerife Bekar
e-mail(s) / / Office No: / AS 209
Course Description
This course introduces the fundamental techniques in Discrete Mathematics for the application in information technologies. Topics include mathematical induction, set theory, prepositional calculus (Logical operations, Truth tables), relations (graphical representation of relations, matrix representation of relations, properties of relations, composite relations, and inverse relations), Boolean algebra, graphs, trees, basic counting arguments, and discrete probability.
General Learning Outcomes
On successful completion of this course students should be able to:
- Manipulate formulae involving sets, integers, reals and functions of such quantities.
- Solve simple problems involving sets, functions, graphs and trees.
- Construct sound logical arguments, including use of induction.
- Appreciate the importance of discrete mathematics to the understanding of computation.
Teaching Methodology/Classroom Procedures
- Each week there are three lecture sessionsand one tutorial session.
- Students’ ideas will be enriched by explicit examples in tutorial sessions by the assistant.
- Regular quizzes and/or exercises will be given.
Course Materials / Main References
Text Book:
Discrete Mathematics Theory and Applications, by D. S. Malik and M. K. Sen, Revised ed., Cengage Learning,
ISBN: 9789814296359
Resource Books:
Discrete Mathematics with Graph Theory, 3rd ed., by Goodaire and Parmenter, Prentice Hall, ISBN:0131679953
Lecture Notes:
All course materials are also available online in Adobe PDF (Portable Document Format).
Weekly Schedule / Summary of Topics
Week 1 / SETS: sets, special sets, operations on sets, Venn diagram,algebra of sets, associative, commutative, distributive and DeMorgan laws, duality principle, power set.
Week 2 / RELATION:ordered pairs, Cartesian product, binary relations, graphical representation of relations, partial ordering and equivalence relations, partitions, inverse relation.
Week 3 / FUNCTIONS: domain, range and image of function, one-to-one (or injective), onto (or surjective), one-to-one correspondence (or bijective), inverse and composition of functions.
Week 4 / MATHEMATICAL INDUCTION: the principle of mathematical induction, introducing numerous examples.
Week 5 / PERMUTATION AND COMBINATION:basic counting rules(product and sum rule) , ordered samples and permutations,combinations, binomial coefficients
Week 6 / PERMUTATION AND COMBINATION:unordered samples without repetition, permutations involving indistinguishable objects, Pigeonhole principle, the principle of inclusion and exclusion.
Week 7 / BOOLEAN ALGEBRA:propositions, basic Boolean functions, truth tables, logic gates.
Week 8-9 / Midterm Examinations
Week10 / BOOLEAN ALGEBRA:minterm and maxterm expansions, dual forms.
Week11 / BOOLEAN ALGEBRA:simplifying boolean expressions using Karnaugh maps.
Week 12 / GRAPHS:graph terminology, representation of graphs, Euler graph
Week 13 / TREES AND TREE ALGORITHMS :definition of tree, properties of trees, spanning trees, minimal spanning trees.
Week 14 / TREES AND TREE ALGORITHMS :Prim’s algorithm, shortest-path problem.
Week 15 / TREES AND TREE ALGORITHMS : Dijkstra’s algorithm.
Week 16-17 / Final Examinations
Requirements
- One who misses an exam should provide a medical report or a valid excuse within 3 days after the missed exam. Time and place of midterm make-up exam will be announced later. No make-up exam will be given for the quizzes.Students missing Final examination have to provide a valid excuse latest on June 13, 2013 Thursday, otherwise their final score will be considered to be ‘zero’. Makeup for Final examination will be RESIT examination.
- Students who do not pass the course and fail to attend the lectures regularly may be given NG grade.
- Duplicated solutions of Assignments need disciplinary actions.
Method of Assessment
Evaluation and Grading / Assignments+Attendance / Quizzes / Midterm Exam / Final Exam
Percentage / 6% / 24 % / 30 % / 40 %