Gain insights into connecting discrete mathematics with programming. Explore variables, expressions, data structures, and algorithm design to enhance your problem-solving and implementation skills.

Discrete Mathematical Algorithms and Data Structures-02-02.png

momoexp4.tar.gz

java and C++

OnlyPython

OnlyJava

OnlyCplusplus

OnlyC

JavaLang3

Discrete mathematics is the basis of several popular algorithms. This course shows the discreteness of data structures and algorithms. It can benefit programmers with a non-CS background looking to strengthen their foundations by connecting theoretical concepts with practical programming scenarios.

The course starts with discussing relating discrete mathematics with algorithms and data structures. You will have examples demonstrating variables, conditional expressions, and arrays as basic building blocks of programming. Then, you will use classes and objects to define and implement linear data structures. You will also learn about the binary tree traversals and templates and the topics of time complexity, set difference, and rearranging the values in a string.

By the end of the course, you will have a strong grasp of algorithm design, data structure implementation, and overall problem-solving.

Programming Discrete Math Concepts for Beginners

# Understanding algorithms from mathematics to computation
Algorithms are one of the main branches of computer science and discrete mathematics. This is why we use concepts and notations from discrete mathematics in computational algorithms. We can map any problem from mathematical form to a computer program with the help of the same algorithm.


Read More about the History of Discrete Mathematics

Although ancient Babylonian, Egyptian, and Greek mathematicians started using the concepts of the algorithm in antiquity, the very term “algorithm” is derived from the name of the ninth-century Persian mathematician Muhammad ibn Mūsā al-Khwārizmī. Before that, Greek mathematicians used the sieve of Eratosthenes to find prime numbers and the Euclidean algorithm to find the greatest common divisors (GCD).

An algorithm is created when we combine mathematics and computation. More specifically, an algorithm refers to a set of well-defined computer-implementable instructions. Yet, mathematics is a separate domain. When we try to map a mathematical problem into the computational domain, we need a sequence of instructions that should be unequivocal, which means the algorithm should exhibit a single clearly defined meaning. A distinct, meaningful output should come out from the inputs.
We now know what an algorithm is; however, we must know why we need it.

The answer is to decide something. When we travel by car and come to a road divider that indicates two ways, we can’t go two ways simultaneously. Our decision should be discrete: 1 or 0; true or false.

Decision-making very heavily depends on effective calculation. Many renowned mathematicians worked on that in the last century, and it continues. High-level programming languages have to come to terms with that because as time has passed by, the size of data has increased, and it will continue to increase over time.



Let’s plunge into code to understand how we can map our problems from the mathematical domain to our computational field. Let’s start with prime numbers. We have plenty of ways to implement it. Let’s first look at what a prime number means.

A **prime number** is a natural number with exactly two discrete natural divisors. For example, 2 is a prime number because it has precisely two divisors—1 and 2. In the same way, 11 is a prime number because there are precisely two divisors—1 and 11.

Based on that concept, we can write our algorithm in natural language this way:


1.  Use any natural number as input.


2. Count the number of factors.

3. If the number of factors is equal to two, classify the the number as prime.

4. If the number is greater than two, classify the number as not prime.









# Finding prime numbers by counting factors

Let’s code this algorithm using the Java programming language.

> **Note:** You can run the following code after entering the input value in the box provided below the code.


import java.util.*; 
import java.math.*; 

//TryingToFindPrime
class Main{
        private static Scanner sc;
        public static void main(String[] args) {
                int numOne, integerOne;
                //Enter any number to Find Factors
                sc = new Scanner(System.in);
                numOne = sc.nextInt();
                System.out.println("Enter a number to find factors: ");
                System.out.println(numOne);

                int controOne = 0;
                for(integerOne = 1; integerOne <= Math.sqrt(numOne); integerOne++)
                {
                        if (numOne % integerOne == 0) {
                                if (numOne / integerOne == integerOne){ 
                                        controOne++;
                                } else {
                                        controOne = controOne + 2;
                                } 
                        }
                }
                if(controOne == 2){
                        System.out.println(numOne + " is prime."); 
                } 
                else {
                        System.out.println(numOne + " is not prime.");
                }

        } 
}

We can test the program by giving inputs like `49` and `47`.

- Output 1:
  ```txt
  Enter a number to find factors: 
  49
  49 is not prime.
  ```
- Output 2:
  ```txt
  Enter a number to find factors: 
  47
  47 is prime.
  ```

Here, in the code above, the algorithm is one of the simplest. We’ve counted the number of factors of the input number and tested the condition, whether that number crosses `2`.

This Java code takes a number, $n$, as input from the user (represented in code by the `numOne` variable).

- **Line 16:** After that, we iterate using a `for` loop from 1 to $\sqrt n$ since the number of factors can’t be greater than $\sqrt n$.
- **Line 22:** If the indexer (`integerOne`) is a factor of $n$, we increment the number of factors (`controOne`, initialized to zero) by two.
- **Lines 26–31:** Finally, if the number of factors is exactly `2`, it’s a prime number; otherwise, it’s a composite.

 


# Clever solution to reduce iterations

Let’s solve the same problem with the help of a different algorithm. Let’s first look at the code. And then, we’ll discuss the algorithm used in it.

> **Note:** You can run the following code after entering the input value in the box provided below the code.

Learn to optimize an algorithm with programming constructs.

Course Introduction

Programming Language and Boolean Algebra

Logical Expressions and Algorithms

Arrays and Discrete Mathematics

Classes, Objects, and Methods

Linear Data Structures

Tree, Algorithms, and Templates

Time Complexity

Propositional Logic

Combinatorics

Wrapping Up

Improving an Algorithm

Understanding algorithms from mathematics to computation