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

# Ways to decide a prime number

In this lesson, we’ll discuss algorithms and time complexity. First, we’ll look at a few code snippets and the time it takes to run the program. Moreover, we’ll also learn about the underlying logic and algorithm of the code.

By now, we’re familiar with the terms “algorithm” and “time complexity.” We know that our algorithm should be efficient enough to reduce the time to run the code.
We should also remember that problems can have many solutions; we just need to find the best algorithm.



Okay, let's try some code in Dart. In this first case, we’re trying to find the factors of a positive integer. As we know, a positive integer, like 4, has three #key# factors: A factor is an integer that can divide the number. It always starts with 1 and ends with that number. #key#: 1, 2, and 4.

A prime number is a number that can be divided only by 1 and the number itself, such as 2, 3, 5, or 7. The list goes on. It’s easy to find whether a number is prime.

# Finding all factors

We can start with a prime number like 5. All we need to do is check whether all the numbers starting from 2 to 4 can divide 5. If any number can divide 5, then 5 is not prime. Otherwise, 5 is prime. 

We’ll look at how to do this in a minute. But first, we’ll find the factors of the number 36, which is a composite number (i.e., not prime.)
Let’s see what factors 36 has. 

//Dart
import'dart:math';
void main(){
  //we will find factors of 36
  //we can add two factors, 1 and 36 itself
  //time complexity is O(n)
  List<int> numbers= List();
  for(int i=1;i<=36;i++){
    if(36 % i == 0){
      numbers.add(i);
    }
  }
  print("${List.from(numbers)}");
  List<int>moreNumbers= List();
  moreNumbers.add(1);
  for(int i=1;i<=18;i++){
    if(36 % i == 0){
      moreNumbers.add(i);
    }
  }
  moreNumbers.add(36);
  print("${List.from(numbers)}");
  //in both cases below, time complexity is O(square root of n)
  List<double>nums= List();
  for(double j=1; j<=sqrt(36); j++){
    if(36 % j == 0){
      nums.add(j);
      if(j != sqrt(36)){
        nums.add(36/j);
      }
    }
  }
  nums..sort();
  print("${List.from(nums)}");
  List<int>moreNums= List();
  for(int j=1; j<=sqrt(36); j++){
    if(36 % j == 0){
      moreNums.add(j);
      if(j != sqrt(36)){
        moreNums.add((36/j).round());
      }
    }
  }
  moreNums.sort();
  print("${List.from(moreNums)}");

  List<int>numsMore= List();
  for(int j=1; j<=sqrt(35); j++){
    if(35 % j == 0){
      numsMore.add(j);
      if(j != sqrt(35)){
        print("true");
        numsMore.add((35/j).round());
      }
    } 
  }
  numsMore.sort();
  print("${List.from(numsMore)}");
}

Let's see the output first.

```txt
[1, 2, 3, 4, 6, 9, 12, 18, 36]
[1, 2, 3, 4, 6, 9, 12, 18, 36]
[1.0, 2.0, 3.0, 4.0, 6.0, 9.0, 12.0, 18.0, 36.0]
[1, 2, 3, 4, 6, 9, 12, 18, 36]
true
true
[1, 5, 7, 35]
```
In the code above, we take the number 36 and keep checking all its factors from 1 to itself. If it has a factor, we add it to the `numbers` list.
- **Lines 16–21:** We try the same approach with half of the number 36; we check all the factors of 36 from 1 to 18 and manually add 36 in the end.
- **Line 28:** This is followed by a smarter approach where we only check until $\sqrt{36} = 6$, and if it’s a factor, we add not only that number but also its quotient. Because both would be the same in the case of the square root, we skip that case.

- **Line 35:** Because it outputs floating point values, we update the code with integer data types and try it for another value, i.e., 35.

# Reducing the iterations 
In the first part of the code above, we loop through the number itself.

```
List<int> numbers= List();
for(int i=1;i<=36;i++){
  if(36 % i == 0){
  numbers.add(i);
  }
}
print("${List.from(numbers)}");
```

However, in the following code, we loop to half of the number.

```java
List<int> moreNumbers= List(); 
moreNumbers.add(1); 
for(int i=1;i<=18;i++){
    if(36 % i == 0){ 
      moreNumbers.add(i);
    }
}
moreNumbers.add(36);
print("${List.from(numbers)}");
```

But the problem in both cases is that we must reduce the number so that the time complexity is big $O(n)$. Can we reduce the time to run the program?

We can check that with the following code.

```java
List<double> nums= List(); 
for(double j=1;j<=sqrt(36);j++){
    if(36 % j == 0){ 
      nums.add(j);
      if(j != sqrt(36)){
         nums.add(36/j);
      }
    }
}
nums.sort();
print("${List.from(nums)}");
```

This time, we successfully reduced the time complexity to big $O(\sqrt{n})$. For an enormous amount of integers, this algorithm fits fine.

# Finding only the prime factors

In the following code snippets, we'll find the prime factors of a positive integer. Factors of any integer can be divided to get the prime factors quickly. Factors of 4 are 1, 2, and 4. We can't divide 1 and 2. The integer 2 is prime. But we can divide 4 and get 2 multiplied by 2.

Let's look at the following code snippets to find the prime factors of any positive integer by passing the integer as a parameter to a function.

Learn about optimizing the running time of an algorithm.

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

Optimizing the Algorithm

Ways to decide a prime number

Finding all factors