Algorithms | Why DFS is used to find the cycle in the graph?

1. DFS is easier to implement.

2. Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to also print the found cycle. This makes DFS a lot more convenient.

BFS won’t work for a directed graph to finding cycles.

Consider A->B and A->C->B as paths from A to B in a graph. BFS will say that after going along one of the paths that B is visited. When continuing to travel the next path it will say that marked node B has been again found, hence, a cycle is there. Clearly, there is no cycle here.

Design Patterns | Software design pattern

What are the design patterns?

A software design pattern is a general, reusable solution to a repetitive occurring problem in software design. It is not a finished design that can be transformed directly into the source or machine code but, a template identifies problems in the system and provides appropriate solutions.

The design pattern testing is not present in normal procedural programming and is mostly adopted by developers in Object Oriented environment. These provide the interaction on Object-Oriented level involving classes and objects. It is used as an efficient programming approach where Object Oriented systems are being developed to provide robustly and error-free software generation.

Need for Design Patterns

With the emerging needs of technology and the growth in the IT industry, typical software development practices, that required the completion of the entire software before testing, has also evolved. To avoid reverting to the stage of development after completion, a testing practice during the development phase was introduced. It can be used to identify error conditions and problems in the code that may not be apparent at the time. The end modules that are obtained are already tested and are less error-prone.

Designing a template that can be reused on multiple codes saves time for test creation and is easy to understand by developers with prior experience working with it. The templates are code and problem independent and do not need to be specified by coders to deal with a problem

Types of Design Patterns

Design patterns are classified into three main categories and each individual design pattern in the category make up a total of 23 design patterns. The four main categories are:

Creational Patterns

Creational Patterns are design patterns that deal with object creation mechanisms, trying to create objects in a manner suitable to the situation.

§  Abstract Factory
In this pattern, a factory of related objects is created by an interface without specification of the class name. The factory passes the objects by following the Factory Pattern.

§  Builder Patterns

This pattern is used for a stage by stage creation of a complex object by combining simple objects. The final object creation depends on the stages of the creative process but is independent of other objects.

§  Factory Method
This pattern is employed mostly during development in Java. It provides implicit object instantiation through common interfaces.

§  Prototype

In Prototype patterns, object duplication is performed while performance is monitored. A prototype interface pattern is present to produce a copy of an object. It is used to restrict memory/database operations by keeping modification to a minimum using object copies.

§  Singleton

This pattern involves the presence of one class and restricting object creation to a single object. The presence of a single object removes the need for object instantiation for accessing.

Structural Patterns

Structural Patterns are design patterns that ease the design by identifying a simple way to realize relationships between entities.

§  Adapter
To link two interfaces that are not compatible and utilize their functionalities, Adapter pattern is used. It is used to provide a new interface covering for any existing class.

§  Bridge

In Bridge Pattern, there is a structural alteration in the main and interface implementer classes without having any effect on each other. These two classes are made independent of each other and are only connected by using the bridge which is an interface.

§  Composite

Composite Pattern is used group together objects as one object. The objects are composed in a tree structure form with the representation of individual tree nodes and the hierarchy as well. The objects belonging to the same groups are modified using this pattern.

§  Decorator

Decorator pattern restricts the alteration of object structure while a new functionality is added to it. The initial class remains unaltered while a decorator class wraps around it and provides extra capabilities.

§  Façade
Façade provides clients with access to the system but conceals the working of the system and its complexities. The pattern creates one class consisting of user functions and delegates provide calling facilities to the classes belonging to the systems.

§  Flyweight
Flyweight pattern is used to reduce memory usage and improve performance by cutting on object creation. The pattern looks for similar objects that already exist to reuse it rather than creating new ones that are similar.

§  Proxy

It is used to create objects that may represent functions of other classes or objects and the interface is used to access these functionalities.

Behavioral patterns

Behavioral pattern deals with the communication between class objects. They are used to sense the presence of already present communication patterns and may be able to manipulate these patterns.

§  Chain of responsibility

A chain of objects is created to deal with the request so that no request goes back unfulfilled.

§  Command
Command pattern deals with requests by hiding it inside an object as a command and sent to be to invoker object which then passes it to an appropriate object that can fulfill the request.

§  Interpreter
Interpreter pattern is used for language or expression evaluation by creating an interface that tells the context for interpretation.

§  Iterator
Iterator pattern is used to provide sequential access to a number elements present inside a collection object without any relevant information exchange.

§  Mediator
Mediator pattern provides easy communication through its mediator class that allows communication for several classes.

§  Memento
Memento pattern involves the working of three classes Memento, CareTaker, and Originator. Memento holds the restorable state of the object. Originator’s job is the creation and storing of state and CareTaker’s job is the restoration of memento states.

§  Observer
A one-to-many relationship calls for the need of Observer pattern to check the relative dependencies of objects.

§  State
In State pattern, the behavior of a class varies with its state and is thus represented by the context object.

§  Strategy
Strategy pattern deals with the change in class behavior at runtime. The objects consist of strategies and the context object judges the behavior at runtime of each strategy.

§  Template method

It is used with components having similarity where a template of the code may be implemented to test both the components. The code can be changed with minor alterations.

§  Visitor
A Visitor performs a set of operations on an element class and changes its behavior of execution. Thus the variance in the behavior of element class is dependent on the change in visitor class.

Algorithms | Write a program to generate n prime numbers

package com.algorithmforum.misc;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.LinkedList;

import java.util.List;

import java.util.Scanner;

public class NPrimesInJava {

      /**

       * Sieve of Eratosthenes

       *

       * @param n

       * @return list of n prime numbers.

       */

      private static List getNPrimesUsingSieve(int n) {

            boolean[] array = new boolean[n * n + 1];

            Arrays.fill(array, true);

            List list = new ArrayList<>();

            int i = 2;

            // exit from loop is the n number has been generated.

            while (list.size() < n) {

                  int j = 2;

                 

                  while (array[i] && i * j < array.length - 1) {

                        array[i * j] = false;

                        j++;

                  }

                  if (array[i]) {

                        list.add(i);

                  }

                  i++;

            }

            return list;

      }

      /**

       * Why is every prime no of form 6k+1 or 6k-1?

       *

       * It is because every third number is divisible by 3 and every second number is

       * divisible by 2. Suppose a number, say 17, then 15 16 17 18 19 ...... now you can

       * see number below and above it are divisible by 2, and either of it has to be

       * a multiple of 3, so this formula holds!

       *

       * @param n

       * @return list of n prime numbers.

       */

      private static List getNPrimes(int n) {

            List primeList = new LinkedList<>(Arrays.asList(2, 3));

            int i = 1;

            while (primeList.size() < n) {

                  int prime1 = 6 * i - 1;

                  int prime2 = 6 * i + 1;

                  if (isPrime(prime1)) {

                        primeList.add(prime1);

                  }

                  if (isPrime(prime2)) {

                        primeList.add(prime2);

                  }

                  i++;

            }

            return primeList;

      }

      /**

       * To check that a number is prime or not.

       *

       * @param prime

       * @return return boolean for number is prime or not.

       */

      private static boolean isPrime(int prime) {

            for (int i = 2; i * i <= prime; i++) {

                  if (prime % i == 0) {

                        return false;

                  }

            }

            return true;

      }

     

      public static void main(String[] args) {

            try (Scanner scan = new Scanner(System.in)) {

                  System.out.println("Enter the number: ");

                  int n = scan.nextInt();

                  List primeList = getNPrimes(n);

                  System.out.println(primeList);

                  primeList = getNPrimesUsingSieve(n);

                  System.out.println(primeList);

            }

      }

}