Applications of Discrete Structures

Applications of Discrete Structures of Second Year Computer Engineering Pune University

1. Applications of Discrete Structures

2. Why Discrete Mathematics? (I) Computers use discrete structures to represent and manipulate data. Computer Science is not Programming Computer Science is not Software Engineering Edsger Dijkstra : “Computer Science is no more about computers than Astronomy is about telescopes.” Computer Science is about problem solving .

3. Why Discrete Mathematics? (II) Mathematics is at the heart of problem solving Defining a problem requires mathematical rigor Use and analysis of models, data structures, algorithms requires a solid foundation of mathematics To justify why a particular way of solving a problem is correct or efficient (i.e., better than another way) requires analysis with a well-defined mathematical model.

4. Applications(1) Discrete mathematics describes processes that consist of a sequence of individual steps. This contrasts with calculus, which describes processes that change in a continuous fashion. Whereas the ideas of calculus were fundamental to the science and technology of the industrial revolution, the ideas of discrete mathematics underlie the science and technology of the computer age.

5. Applications(2) The main themes of a first course in discrete mathematics are logic and proof, induction and recursion, discrete structures, combinatorics and discrete probability, algorithms and their analysis, and applications and modeling.

6. Unit I Sets and Propositions This unit help students develop the ability to think abstractly. This means learning to use logically valid forms of argument and avoid common logical errors Set theory is the foundation of mathematics.

7. Unit II Relations and Functions 1 to many 1 to 1 many to many

8. Unit III Groups and Rings Problems in this field often arise (or follow naturally from) a problem that is easily stated involving counting, divisibility, or some other basic arithmetic operation. While many of the problems are easily stated, the techniques used to attack these problems are some of the most difficult and advanced in mathematics.

9. Unit IV Graph Theory “EVERYTHING IS A GRAPH” (labeled, directed, etc., ...)  graph theory can be used in modelling of: Social networks Communications networks Information networks Software design Transportation networks Biological networks

10. Unit V Trees 1. Manipulate hierarchical data. 2. Make information easy to search (see tree traversal). 3. Manipulate sorted lists of data. 4. As a workflow for compositing digital images for visual effects. 5. Router algorithms

11. Unit VI Permutations, Combinations and Discrete Probability A  combination  is a selection of all or part of a set of objects,  without  regard to the order in which they were selected. This means that XYZ is considered the same combination as ZYX. A  permutation  is an arrangement of all or part of a set of objects,  with  regard to the order of the arrangement. This means that XYZ is considered a different permutation than ZYX. The  probability  of an event refers to the likelihood that the event will occur