ST PAUL UNIVERSITY SURIGAO 8400 Surigao City, Philippines COLLEGE OF BUSINESS AND TECHNOLOGY INFORMATION TECHNOLOGY AREA COURSE

SYLLABUS Course Code Course Title Course Credit Prerequisite Term : : : : : Second Semester, AY 2010-2011 ITED 106 Discrete Structures Three (3)

Course Description: This is a three-unit course intended for computer science and information technology students. Discrete mathematics emphasizes set and operations over set that can be expressed in terms of a subset of the integers. A key feature of this subject as applied to modern computer science is the ability to specify the functionality of computer programs in terms of mathematical expressions. In order to exploit discrete mathematics, the computer science students need to learn how to read, understand and manipulate notation. In practice, such notations describe operands, operations, algorithms, and combinatorics and analysis techniques specific to computer related applications. Course Objectives: At the end of the course, students are expected to; 1. 2. 3. 4. 5. 6. 7. 8. 9. Define the syntax and semantics of propositional and predicate logic; Translate statements from a natural language into its symbolic structures in logic; Analyze sentences in logic and make inferences that are correct and logically sound; Prove the different set properties; Apply the notion of relations on some finite structures, like strings and databases; Analyze algorithms using the concept of functions and function complexity; Apply the principles and techniques in graph theory that are appropriate for a given problem. Design simple logic circuits for a given switching function. Apply the principles and techniques in automata necessary to solve a given problem.

Course Requirements: 1. Major Examinations (Pre-Midterm, Midterm, Pre-Final, Final) 2. Class Attendance 3. Active Class Participation 4. Midterm & Final Projects/Transforms
Page 1

Course Syllabus: Discrete Structures

ST. PAUL UNIVERSITY SURIGAO

Paulinian Values Formation: At the end of the course, the students should: 1. develop analytical minds in using information technology as aid in problem solving. 2. recognize the importance of information technology in society while underlining the detrimental effects of the same if abused and used improperly. 3. exhibit and practice perseverance, accuracy, patience and honesty. 4. create outputs that displays simplicity, precision, prudence, and significance. COURSE CONTENT: Week Module 1,2 1 LOGIC AND PROOFS Lessons 1. Propositions truth tables logic 2. Conditional Proposition and Logical Equivalence De Morgans Law 3. Quantifiers Universal quantifier Existential quantifier 4. Proofs 3,4 2 THE LANGUAGE OF MATHEMATICS Lessons 1. Sets Cartesian Products Venn Diagrams Operation on Sets 2. Number Systems Binary Systems Decimal and Hexadecimal Systems 3. Relations and Functions Matrices of Relations Functions Module Objectives At the end of the unit, the students will be able to: 1. To define the syntax and semantics of propositional logic. 2. To understand the truth table and be able to prove statements/propositions. 3. To evaluate the De Morgans Law.
Learning Competencies

Value/s Accuracy

Learning Strategies
Check up quiz to review prior knowledge. Construction of truth tables using different laws in logic Proving of statements using different laws in logic

Learning Assessment
Pre-Assessment: Quiz Formative Assessment: APPLICATION on truth tables through problem solving. Summative Assessment: INTERPRETATION of propositions through proofs.

Prove statements and propositions through application of laws and theorems. Evaluate different laws through proofs.

At the end of the unit the students will be able to: 1. Manipulate the sets through the use of Venn Diagrams. 2. Prove theorems through the operations of sets. 3. Analyze different number systems through computations. 4. Simplify different functions by solving different problems related to functions.

Manipulation of sets through the use of Venn Diagrams. Analyze different functions through computations.

Critical thinking

Check up quiz to review prior knowledge.

Pre-Assessment: Quiz Formative Assessment: APPLICATION problem solving such as converting of one number system to another number system Summative Assessment: APPLICATION Problem Solving on the language of mathematics.

PRE-MIDTERM EXAMINATION
Course Syllabus: Discrete Structures Page 2

ST. PAUL UNIVERSITY SURIGAO

6,7

COUNTING METHODS AND PIGEONHOLE PRINCIPLE Lessons 1. Basic Principles Multiplication Principle Addition Principle 2. Permutation and Combination Formula used 3. Pigeonhole Principle

At the end of the unit the students will be able to: 1. Restate the different counting methods and principles. 2. Calculate the possible permutations and combinations of a game of chance and contemplate on possible real life consequences. 3. Study the behavior of pigeons in a pigeonhole and infer the principle behind it.

Be able to solve problems related to counting and apply it to real life situations. Understand the process of games of chance through permutations and combinations. Infer the principle of a pigeonhole.

Critical thinking Resourcefulness

Each group will have an activity sheet and using dice or deck of cards and do counting principles. Using the same props, they will count through permutation and combination formula. They will compare the results . Each group will create a pigeonhole of different sizes and holes.

Pre-Assessment: Sharing of experiences in games of luck and gaining insights. Formative Assessment: APPLICATION on permutations and combinations through betting on a lotto game.

Summative Assessment: APPLICATION on counting methods by problem analysis.

ALGORITHMS Lessons 1. Introduction to Algorithms 2. Notation for Algorithms Example algorithms

At the end of the unit the students will be able to: 1. Counter propose another algorithm of a known step; 2. Create a new algorithm using proper notation used for algorithms.

Correct use of notation in algorithm creation and analysis. Reason on the correctness of the algorithm used in a given problem.

Creativity

The students will be given algorithms with purposely erred notation and infer on the correctness of it. The students will analyze the flow of the algorithm and compute for the time complexity.

Pre-Assessment: Analysis of a sample program. Formative Assessment: APPLICATION on algorithm through demonstration of the algorithm in a computer program. Summative Assessment: APPLICATION by creating a new algorithm derived from the given lesson. Pre-Assessment: Analyze the farmer, wolf, goat, cabbage problem Formative Assessment: APPLICATION Analyze and explain the travelling salesman problem. Page 3

10,11

GRAPH THEORY Lessons 1. Introduction to graphs Graph Terminology 2. Paths and Cycles Traveling Salesman Problem Knigsberg Bridge Problem 3. Shortest-Path Algorithms

MIDTERM EXAMINATION At the end of the unit the students will be able to: 1. Put to use the different graphs in different problems in graph theory. 2. Infer the paths and cycles in classical problems like the Be able to construct graphs with accuracy and appropriateness in a given problem. Compute the paths and Accuracy The students will answer the farmer-wolf-goatcabbage problem. They will analyze the paths and cycles in the sample problems such

Course Syllabus: Discrete Structures

ST. PAUL UNIVERSITY SURIGAO

Dijkstras Shortest Path Algorithm

travelling salesman problem. 3. Employ the shortest path algorithm in graph problems such as the farmer-wolf-goatcabbage problem and the travelling salesman problem.

cycles of a given problem. Propose a shortest path as a counterexample in the problems given.

as Traveling Salesman Problem and Knigsberg Bridge Problem They will also determine the shortest path of the salesman through the Dijkstras algorithm They will test a graph if it is a tree by satisfying the u and v is in set T and there is a unique simple path from u to v. Using the given tree, the students will find the MST utilizing the Prims Algorithm. The students will construct a tree from a given algorithm and do the pre order and post order traversal.

Summative Assessment: APPLICATION Prove that Dijkstras shortest-path algorithm correctly finds a shortest path.

12,13

TREES Lessons 1. Terminologies and Characterization of trees. 2. Spanning Trees and MST Prims Algorithm 3. Binary Tree and Tree Traversal

At the end of the unit the students will be able to: 1. Use the different terminologies and apply it to real life problems. 2. Simplify the algorithm used in spanning trees and the MST. 3. Breakdown the tree traversal and its algorithm to determine the time travelled.

Construct trees as application in file and folder organization in PCs. Give alternative characterization of trees. Simplifying the algorithms in the problems at hand. Be able to compute the time of tree traversals.

Accuracy

Pre-Assessment: Present a family tree of the student Formative Assessment: APPLICATION Utilize the tournament bracket of the World Series in Major League Baseball to determine the world champion. Summative Assessment: APPLICATION Organize folders and files in your PC using the tree structure. The root is the desktop and show the screenshot of the tree that was constructed. Pre-Assessment: Identify the different gates used in a combinatorial circuit. Formative Assessment: APPLICATION Utilize the combinatorial circuit used in the pre assessment but this time, it will be tested with inputs. Summative Assessment: APPLICATION Page 4

15,16

BOOLEAN ALGEBRAS AND COMBINATORIAL CIRCUITS Lessons 1. Combinatorial Circuits Properties of Combinatorial Circuits. 2. Boolean Algebras 3. Boolean Functions and Synthesis of Circuits

PRE-FINAL EXAMINATION At the end of the unit the students will be able to: 1. Explain the combinatorial circuit. 2. appreciate the use of Boolean algebra in properties of combinatorial circuits. 3. generate synthesis of the functions an circuits using the different algebraic laws... Creativity and Accuracy The students will identify and trace the gates used in a combinatorial circuit. They will apply the operations in the laws of the combinatorial circuit. The students will construct a truth table applying the different

Construct different circuits using the different Boolean algebraic laws. Design different combinatorial circuits using the different properties of it.

Course Syllabus: Discrete Structures

ST. PAUL UNIVERSITY SURIGAO

equations of the given problem. 12, 13 AUTOMATA, GRAMMARS AND LANGUAGES Lessons 1. Sequential Circuits and Finite-State Machines 2. Finite State Automata 3. Languages and Grammars Backus-Naur Form

The students will design their own combinatorial circuits and be tested using the inputs that will be given by the instructor.
Pre-Assessment: Identify the different gates used in a combinatorial circuit. Formative Assessment: APPLICATION Utilize the combinatorial circuit used in the pre assessment but this time, it will be tested with inputs and determine the state of the system at the time the input is introduced. Summative Assessment: APPLICATION

At the end of the unit the students will be able to: 1. Explain the finite state machine. 2. Relate the use of combinatorial circuit to finite state machines; 3. Compare and contrast natural and formal language. 4. Scrutinize the Backus Naur Form as another phrase structure grammar.

Use the skill in combinatorial circuit to input and to infer the state of the machine in the process. Comparing and contrasting natural and formal languages.

Creativity , Perseverance and Accuracy

The students will identify and trace the gates used in a combinatorial circuit. They will apply the operations in the laws of the combinatorial circuit. The students will construct a truth table applying the different equations of the given problem.

The students will convert the combinatorial circuit that they built into a finite state machine and be tested again.

FINAL EXAMINATION Textbook: Johnsonbaugh, R. 2001. Discrete Mathematics, 5th Ed. Prentice-Hall, NJ: Upper Saddle River References: Busby, Robert and Kolman Bernard. 1992. Discrete Mathematical Structures for Computer Science. Quezon City. St. Martin Publications Chen, W W L. 2002. www.maths.mq.edu.au/~wchen/lndmfolder/lndm.html Johnsonbaugh, R. 2001. Discrete Mathematics, 5th Ed. Prentice-Hall, NJ: Upper Saddle River Larsen R. and Marx, M. 2001. An Introduction to Mathematical Statistics and Its Applications, 3rd Ed. Prentice-Hall, NJ: Upper Saddle River Pangan, M. et. Al 1996. Statistics for College Students. Philippines: Grandwater Publication and Research Corp. Stoll, Robert R. 1963. Set Theory and Logic, New York: Freeman Course Policies: 1. Grading System Summative Assessment Pre-Midterm, Midterm, Pre-Final And Final Examinations Formative Assessment
Course Syllabus: Discrete Structures

50% 30%
Page 5

ST. PAUL UNIVERSITY SURIGAO

Quizzes, Assignments, Seatwork And Hands- on Exercises Creative Assessments Projects/Transforms TOTAL Final Grade =

20% 100%

2. Student Conduct in Class 2.1. The instructor will not tolerate any class disruption that go beyond the normal rights of students to question and discuss with instructors the educational process relative to subject content. 2.2. The instructor prohibits the use of cellular phones, MP3 players and similar devices that may disrupt the discussion. 2.3. The instructor prohibits the use of calculators and computers during examinations and quizzes, unless specified. 2.4. The instructor allows the use of laptop sized computers in lecture for note taking. 3. Quizzes/Examinations 3.1. The instructor gives announced examinations and announced/unannounced quizzes. 3.2. No make-up examinations will be given without prior arrangements. All missed quizzes and hands-on exercises will be equivalent to zero unless there is a valid reason at the discretion of the instructor. 3.3. All major examinations will be conducted as scheduled by the University Registrars Office. 4. Cheating Policy Students are expected to uphold the schools standard of conduct relating to academic honesty. Students assume full responsibility for the content and integrity of the academic work they submit. The guiding principle of academic integrity shall be that a student's submitted work, examinations, reports, and projects must be that of the student's own work. It is permissible to assist classmates in general discussions of solutions to exercises. General advice and interaction are encouraged. Each student, however, must develop his/ her own solutions to the assigned projects, assignments, and tasks therefore students may not "work together" on graded assignments, unless otherwise specified. Such collaboration constitutes cheating. A student may not use or copy (by any means) another's work (or portions of it) and represent it as his/her own. If you need help on an assignment, contact your instructor, not other classmates. Anyone caught cheating or trying to cheat in any manner will be given a final grade of 70. 5. Absences It is the students responsibility to get course notes, handouts and assignments should they miss class or be late. The maximum allowable number of absences is equivalent to 6 class hours. Anyone who exceeds this limit will be given a final grade of FA (Failed due to absences)

Course Syllabus: Discrete Structures

Page 6

ST. PAUL UNIVERSITY SURIGAO

Prepared by:

Reviewed by:

Recommending Approval:

Approved:

JESSEVIM R. GALEON, MIT Instructor

Program Chair

ESTER A. GUARIN, PhD Dean

SR. FELICITAS BERNARDO, SPC VP - Academic Services

Course Syllabus: Discrete Structures

Page 7