(PDF) Discrete Mathematics for Computer Science

Discrete Mathematics
for IT

Table of Contents
INTRODUCTION...........................................................................................................................3
PROBLEM DEFINITION..............................................................................................................3
REAL WORLD APPLICATION...................................................................................................3
SOLUTION TO THE PROBLEM................................................................................................5
POSSIBLE ALGORITHM.............................................................................................................5
CONCLUSION...............................................................................................................................7
REFLECTION................................................................................................................................7
REFRENCES.................................................................................................................................8

INTRODUCTION
Discrete mathematics refers to the important topic that deals mainly with discrete objects. It
includes Integers (positive and negative whole numbers), rational numbers (numbers that can
be represented in the form of quotient of two integers), sets and more. But others real numbers
that include irrational numbers are not considered as discrete. Therefore, discrete mathematics
includes a limited set of integers only. This subject becomes a most important one in real world
problems, especially within computer science. Using discrete mathematics, a formal language
that also known as object language can be formed, in the form of mathematical expression to
denote logical statements. The present assignment is going to evaluate the concept of discrete
mathematics and its importance in solving real life problems. As this topic includes a number of
topics like Polynomial Evaluation Algorithm; Algorithm for constructing a Euler circuit; Kruskal’s
algorithm; Insertion sort and more. Therefore, problem chosen here is Polynomial Evaluation
Algorithm, which will be solved by using both mathematical formula and computer
language –
PROBLEM DEFINITION
Polynomial evaluation algorithm also known as Horner’s method, i.e. expressed in
the form of –
p(x) = a0 + a1 x + a2 x2 + a3 x3 + a4 x4 + … + an xn
or, p(x) = ∑ ai xi for all values of i=0 to n.
Let, a problem is defined in the form of an xn + an-1 xn-1 + an-2 xn-2 + … + a1 x + a0, where an,
a1, a1 and so on are integers and x is a variable, as
Problem: Evaluate the value of 2x3 – 6x2 + 2x – 1
REAL WORLD APPLICATION
As normal language is not suitable for coding languages. Therefore, in ICT (Information and
Communication Technology), algorithm is preferred to write codes to build language, C, JAVA,
Python and more. Complex logical problems and difficult questions can easily be solved by
using discrete maths. A computer programmer can use this subject for designing efficient
algorithms, which defines as a set of rules to operate a program. Such rules are created by the
laws of discrete mathematics, that helps in running a computer more faster. For example –
For multiplication, algorithm can be written in following way –
a,b are positive integers, then binary expression for a & b are (), () respectively;

for j = 0 to j = n-1
if j = 1 then shifted j places to 0
let p = 0 for j = 0 to j = n-1
then p = p + return p (p is the value of ab)
therefore, it can be said that discrete mathematics is useful in solving a number of
practical problems. As computer understand only binary language i.e. in the form of 0 and 1
only, so binary language is also a part of discrete maths only. Other examples include –
Encryption and decryption which is a form of cryptography, is also considered as a part of
discrete maths, where internet shopping can be done by using public-key cryptography.
Figure 1Discrete maths in cryptography
Graphical theory is used in network security also like cybersecurity for identifying the criminal or
hacked servers.
In Neuroscience, graph theory is used to study the brain network organisation, for nervous
system disorders.
In cluster analysis on geosocial data, linear algebra and graph theory both are used for locating
gangs and insurgencies.
In medical science, discrete maths is used for kidney donor matching, assessing risks for heart-
patients and more.
In railway planning, discrete mathematics is used for deciding expansion of tracks and railway
lines, time table schedules and more.
Computer graphics like video games mostly usage linear algebra, for transforming the objects.
Therefore, discrete maths hereby is used for game development and operating system as
xy rotation matrix - Cos Ø -Sin Ø 0
Sin Ø Cos Ø 0

0 0 1
SOLUTION TO THE PROBLEM
Problem: Evaluate the value of 2x3 – 6x2 + 2x – 1
Using, Horner’s Method or Polynomial Evaluation Algorithm, the given problem can be
solved by –
p(x) = 2x3 – 6x2 + 2x – 1
At x = 1,
p(1) = 2(1)3 – 6(1)2 + 2(1) – 1
= 2 – 6 + 2 – 1
= 4 – 7
= 3
Similarly, at x = 2,
p(1) = 2(2)3 – 6(2)2 + 2(2) – 1
= 16 – 24 + 4 – 1
= 20 – 25
= -5
POSSIBLE ALGORITHM
The given problem, using different languages of computer can be solved in following
manner –
Solution 1: Using C / C++
#include <iostream>
Using namespace std;
//returns value of poly[0] x(n-1) + poly[1] x(n-2) + poly[2] x(n-3) + … + poly[n-1]
int horner (int poly[], int n, int x)
{
int result = poly[Ø]; // initialisation result
// Evaluate value of polynomial using Horner’s method

for (int i=1; i<n; i++)
result = result * x + poly [i];
return result;
}
// Driver program to test the above function.
int main()
{
// Let us evaluate value of 2x3 - 6x2 + 2x - 1 for x = 2
int poly [] = {2, -6, 2, -1};
int x = 2;
int n = size of (poly) / size of (poly[0]);
cout << "Val ue of polynomial is " << horner (poly, n, x);
return 0;
}
Output
value of polynomial is -5.
Solution 2: Using JAVA language,
// JAVA program for implementation of Horner Method
// for Polynomial Evaluation
import java.io.* ;
class HornerPolynomial
{
// function that returns value of poly[Ø] x[n-1] +
// poly[1] x(n-2) + ….+ poly[n-1]
static int horner (int poly[], int n, int x)
{
// Initialize result
int result = poly[0];
// Evaluate value of polynomial using Horner's method
for (int i=1; i<n; i++)

result = result*x + poly[i];
return result;
}
// Driver program
public static void main (String[] args)
{
// Let us evaluate value of 2x3 - 6x2 + 2x - 1 for x = 2
int[] poly = {2, -6, 2, -1};
int x = 2;
int n = poly. length;
System.out.println("Value of polynomial is "
+ horner (poly,n,x));
}
}
Output
value of polynomial is -5
CONCLUSION
It has been concluded from all above mathematical analysis and description that discrete
mathematics is most important part in information and communication technology, which is used
for solving a number of real life based problems. It includes cryptography, medical science,
Google maps and more. Using discrete mathematics, computer software can run in smooth and
fast manner.
REFLECTION
The given project has given me the opportunity to enhance my analytical skills, whereby
working on understanding how discrete mathematics help in solving the real life based problems
helps to enhance my knowledge level. On this project, I have worked in a team of three
members, where I am good in using mathematical formulae to solve the questions. While other
two members of my team, know how to set algorithms in computer language. Therefore, one of
them has evaluate the value of problem in C language, while other one in JAVA. Thus,
cooperation and efforts of each team-member has helped in making assignment on discrete
maths more easily, in desired way.

REFRENCES
Books and Journals
More, M., 2018. Mathematics and engineering in real life through mathematical
competitions. International Journal of Mathematical Education in Science and
Technology, 49(2), pp.305-321.
Ieren, T.G. and Kuhe, D.A., 2018. On the properties and applications of Lomax-exponential
distribution. Asian Journal of Probability and Statistics, pp.1-13.
Fleming, M., 2018. The art of drama teaching. Routledge.
Kurgalin, S. and Borzunov, S., 2018. The Discrete Math Workbook: A Companion Manual for
Practical Study. Springer.
Rupe, A. and Crutchfield, J.P., 2018. Local causal states and discrete coherent
structures. Chaos: An Interdisciplinary Journal of Nonlinear Science, 28(7), p.075312.