Question

1. Recently, there was cyber-attack on one of the banks in Ghana. Millions of Ghana Cedis were transferred from the bank to some individual’s account. In details, explain cryptography and its purpose in providing cybersecurity to firms such as financial institutions.                             

  

2. Analyze Kruskal’s algorithm and explain its application in data structures and algorithms. Write a program to implement Kruskal’s algorithms using a high-level programming language.

3. Describe in details abstraction and their relevance in data structures.   

Question 2

1. Explain the concept of trees in data structures and algorithm expanding their applications. Model a step to make best decision using decision tree concept.

2. Suppose you're a traveling salesperson who must visit certain locations on a map and then return to your starting point. The traveling salesman problem is to visit those locations in an order that minimizes the total distance covered. Evaluate how such a traveling salesman would solve this problem to minimize the operational cost of their organization. Demonstrate with mathematical expressions.       

3. Explain Dijkstra’s algorithm and write a program to implement Dijkstra’s algorithm. Explain the relevance of Dijkstra’s algorithm to computational intelligence in problem solving.

Answer 1

1. Recently, there was cyber-attack on one of the banks in Ghana. Millions of Ghana Cedis were transferred from the bank to some individual’s account. In details, explain cryptography and its purpose in providing cybersecurity to firms such as financial institutions.                             

  ANS- Cryptography is associated with the process of converting ordinary plain text into unintelligible text and vice-versa. It is a method of storing and transmitting data in a particular form so that only those for whom it is intended can read and process it.

HOW TO IMPROVE CYBERSECURITY IN FINANCIAL INSTITUTIONS

The CIA triangle

All information security comes from the concept of protecting the information’s Confidentiality, Integrity, and Availability.

Confidentiality – Only those allowed to may access the information.

Integrity – The information does not get changed either purposely or accidentally

Availability – The information can be accessed when needed, even in the event of DDoS or natural disaster.

Physical Security

Network equipment is locked in a separate room and access is controlled. The office doors and windows are all locked when no one is there. Sensitive areas are not accessible by unauthorized personnel. Fire protection is sufficient.

Network perimeter

An adequate hardware firewall that does a stateful inspection and is properly configured is the first piece of your network the internet must go through.

User management

All users are assigned unique IDs and only given access to information required to do their job. Elevated privileges are kept to a minimum number of users.

Patch management

Administrators keep abreast of new vulnerabilities on their networks. Software patching is tested and completed in a timely manner.

Anti-virus

A reputable A/V is installed, automatically updated, and settings are not able to be changed by users.

Personnel training

All personnel are trained on basic security measures the company observes. Personnel that deal with sensitive information regularly receive training specific to the data environment.

Your Information Security Policy (ISP)

Network security is about more than having the right IT gear with the right settings. Security should be looked at more holistically taking people, processes, and technology into account. Generally, the best place to start is with your Information Security Policy (ISP). This document should have detailed guidelines to all aspects of your program including Risk Assessments, Access and Authorization, Physical security, Incident Response Plan, Business Continuity Plan, and much more.

Defense in depth

This is the concept that vital information cannot be improperly accessed by beating 1 security measure. With defense in depth, multiple measures must be beaten. For instance, an attacker might have to beat a firewall, know a user name, crack a password, avoid the honeypot, and install malware that isn’t detected by the Anti-virus (A/V) all while not alerting the Intrusion Detection System (IDS) to reach sensitive portions of the network, and then beat the encryption and other measures to access the critical portions of the network.

Physical defense in depth may have roving security, cameras, complex locks, motion sensors, and alarms all before you can even access the server room.

Multiple barriers take time to overcome. The more time it takes to complete an attack, the more opportunities there will be to make a mistake, and the higher the chances of getting caught. Multiple barriers require multiple areas of expertise to overcome, making the attack more difficult and time-consuming.

DMZ or Network segmentation

A form of defense in depth, segmenting your network can keep your sensitive information safe while allowing relative freedom for other portions of the network. A DMZ puts a web server behind a firewall that is accessible from the internet. A second firewall behind the web server protects the internal network.

Analyze Kruskal’s algorithm and explain its application in data structures and algorithms. Write a program to implement Kruskal’s algorithms using a high-level programming language.

ANS-Kruskal's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which

• form a tree that includes every vertex
• has the minimum sum of weights among all the trees that can be formed from the graph

How Kruskal's algorithm works

It falls under a class of algorithms called greedy algorithms that find the local optimum in the hopes of finding a global optimum.

We start from the edges with the lowest weight and keep adding edges until we reach our goal.

The steps for implementing Kruskal's algorithm are as follows:

1. Sort all the edges from low weight to high
2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge.
3. Keep adding edges until we reach all vertices.

# Python program for Kruskal's algorithm to find

# Minimum Spanning Tree of a given connected,

# undirected and weighted graph

from collections import defaultdict

#Class to represent a graph

class Graph:

    def __init__(self,vertices):

        self.V= vertices #No. of vertices

        self.graph = [] # default dictionary

                                # to store graph

         

  

    # function to add an edge to graph

    def addEdge(self,u,v,w):

        self.graph.append([u,v,w])

    # A utility function to find set of an element i

    # (uses path compression technique)

    def find(self, parent, i):

        if parent[i] == i:

            return i

        return self.find(parent, parent[i])

    # A function that does union of two sets of x and y

    # (uses union by rank)

    def union(self, parent, rank, x, y):

        xroot = self.find(parent, x)

        yroot = self.find(parent, y)

        # Attach smaller rank tree under root of

        # high rank tree (Union by Rank)

        if rank[xroot] < rank[yroot]:

            parent[xroot] = yroot

        elif rank[xroot] > rank[yroot]:

            parent[yroot] = xroot

        # If ranks are same, then make one as root

        # and increment its rank by one

        else :

            parent[yroot] = xroot

            rank[xroot] += 1

    # The main function to construct MST using Kruskal's

        # algorithm

    def KruskalMST(self):

        result =[] #This will store the resultant MST

        i = 0 # An index variable, used for sorted edges

        e = 0 # An index variable, used for result[]

            # Step 1: Sort all the edges in non-decreasing

                # order of their

                # weight. If we are not allowed to change the

                # given graph, we can create a copy of graph

        self.graph = sorted(self.graph,key=lambda item: item[2])

        parent = [] ; rank = []

        # Create V subsets with single elements

        for node in range(self.V):

            parent.append(node)

            rank.append(0)

     

        # Number of edges to be taken is equal to V-1

        while e < self.V -1 :

            # Step 2: Pick the smallest edge and increment

                    # the index for next iteration

            u,v,w = self.graph[i]

            i = i + 1

            x = self.find(parent, u)

            y = self.find(parent ,v)

            # If including this edge does't cause cycle,

                        # include it in result and increment the index

                        # of result for next edge

            if x != y:

                e = e + 1     

                result.append([u,v,w])

                self.union(parent, rank, x, y)            

            # Else discard the edge

        # print the contents of result[] to display the built MST

        print "Following are the edges in the constructed MST"

        for u,v,weight in result:

            #print str(u) + " -- " + str(v) + " == " + str(weight)

            print ("%d -- %d == %d" % (u,v,weight))

# Driver code

g = Graph(4)

g.addEdge(0, 1, 10)

g.addEdge(0, 2, 6)

g.addEdge(0, 3, 5)

g.addEdge(1, 3, 15)

g.addEdge(2, 3, 4)

g.KruskalMST()

Describe in details abstraction and their relevance in data structures.

ANS-

Data abstraction is one of the most essential and important feature of object oriented programming in C++. Abstraction means displaying only essential information and hiding the details. Data abstraction refers to providing only essential information about the data to the outside world, hiding the background details or implementation.

Consider a real life example of a man driving a car. The man only knows that pressing the accelerators will increase the speed of car or applying brakes will stop the car but he does not know about how on pressing accelerator the speed is actually increasing, he does not know about the inner mechanism of the car or the implementation of accelerator, brakes etc in the car. This is what abstraction is.

Abstraction using Classes: We can implement Abstraction in C++ using classes. Class helps us to group data members and member functions using available access specifiers. A Class can decide which data member will be visible to outside world and which is not.

Abstraction in Header files: One more type of abstraction in C++ can be header files. For example, consider the pow() method present in math.h header file. Whenever we need to calculate power of a number, we simply call the function pow() present in the math.h header file and pass the numbers as arguments without knowing the underlying algorithm according to which the function is actually calculating power of numbers.

Abstraction using access specifiers

Access specifiers are the main pillar of implementing abstraction in datastructures. We can use access specifiers to enforce restrictions on class members. For example:

• Members declared as public in a class, can be accessed from anywhere in the program.
• Members declared as private in a class, can be accessed only from within the class. They are not allowed to be accessed from any part of code outside the class.

We can easily implement abstraction using the above two features provided by access specifiers. Say, the members that defines the internal implementation can be marked as private in a class. And the important information needed to be given to the outside world can be marked as public. And these public members can access the private members as they are inside the class.

Explain the concept of trees in data structures and algorithm expanding their applications. Model a step to make best decision using decision tree concept

ANS-

A decision tree is a map of the possible outcomes of a series of related choices. It allows an individual or organization to weigh possible actions against one another based on their costs, probabilities, and benefits.

As the name goes, it uses a tree-like model of decisions. They can be used either to drive informal discussion or to map out an algorithm that predicts the best choice mathematically.

A decision tree typically starts with a single node, which branches into possible outcomes. Each of those outcomes leads to additional nodes, which branch off into other possibilities. This gives it a tree-like shape.

Suppose you're a traveling salesperson who must visit certain locations on a map and then return to your starting point. The traveling salesman problem is to visit those locations in an order that minimizes the total distance covered. Evaluate how such a traveling salesman would solve this problem to minimize the operational cost of their organization. Demonstrate with mathematical expressions.

ANS-

Travelling Salesman Problem (TSP): Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
Note the difference between Hamiltonian Cycle and TSP. The Hamiltoninan cycle problem is to find if there exist a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.

For example, consider the graph shown in figure on right side. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80.

The problem is a famous NP hard problem. There is no polynomial time know solution for this problem.

Following are different solutions for the traveling salesman problem.

Naive Solution:
1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate cost of every permutation and keep track of minimum cost permutation.
4) Return the permutation with minimum cost.

Time Complexity: Θ(n!)

Dynamic Programming:
Let the given set of vertices be {1, 2, 3, 4,….n}. Let us consider 1 as starting and ending point of output. For every other vertex i (other than 1), we find the minimum cost path with 1 as the starting point, i as the ending point and all vertices appearing exactly once. Let the cost of this path be cost(i), the cost of corresponding Cycle would be cost(i) + dist(i, 1) where dist(i, 1) is the distance from i to 1. Finally, we return the minimum of all [cost(i) + dist(i, 1)] values. This looks simple so far. Now the question is how to get cost(i)?
To calculate cost(i) using Dynamic Programming, we need to have some recursive relation in terms of sub-problems. Let us define a term C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i.
We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note that 1 must be present in every subset.

For a set of size n, we consider n-2 subsets each of size n-1 such that all subsets don’t have nth in them.
Using the above recurrence relation, we can write dynamic programming based solution. There are at most O(n*2ⁿ) subproblems, and each one takes linear time to solve. The total running time is therefore O(n²*2ⁿ). The time complexity is much less than O(n!), but still exponential. Space required is also exponential. So this approach is also infeasible even for slightly higher number of vertices.

Explain Dijkstra’s algorithm and write a program to implement Dijkstra’s algorithm. Explain the relevance of Dijkstra’s algorithm to computational intelligence in problem solving.

ANS-

Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root. We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has a minimum distance from the source.

Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other vertices in the given graph.
Algorithm
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
….a) Pick a vertex u which is not there in sptSet and has minimum distance value.
….b) Include u to sptSet.
….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

Python program for Dijkstra's single

# source shortest path algorithm. The program is

# for adjacency matrix representation of the graph

# Library for INT_MAX

import sys

class Graph():

    def __init__(self, vertices):

        self.V = vertices

        self.graph = [[0 for column in range(vertices)]

                    for row in range(vertices)]

    def printSolution(self, dist):

        print "Vertex \tDistance from Source"

        for node in range(self.V):

            print node, "\t", dist[node]

    # A utility function to find the vertex with

    # minimum distance value, from the set of vertices

    # not yet included in shortest path tree

    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node

        min = sys.maxint

        # Search not nearest vertex not in the

        # shortest path tree

        for v in range(self.V):

            if dist[v] < min and sptSet[v] == False:

                min = dist[v]

                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source

    # shortest path algorithm for a graph represented

    # using adjacency matrix representation

    def dijkstra(self, src):

        dist = [sys.maxint] * self.V

        dist[src] = 0

        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from

            # the set of vertices not yet processed.

            # u is always equal to src in first iteration

            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the

            # shotest path tree

            sptSet[u] = True

            # Update dist value of the adjacent vertices

            # of the picked vertex only if the current

            # distance is greater than new distance and

            # the vertex in not in the shotest path tree

            for v in range(self.V):

                if self.graph[u][v] > 0 and sptSet[v] == False and \

                dist[v] > dist[u] + self.graph[u][v]:

                        dist[v] = dist[u] + self.graph[u][v]

        self.printSolution(dist)

# Driver program

g = Graph(9)

g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],

        [4, 0, 8, 0, 0, 0, 0, 11, 0],

        [0, 8, 0, 7, 0, 4, 0, 0, 2],

        [0, 0, 7, 0, 9, 14, 0, 0, 0],

        [0, 0, 0, 9, 0, 10, 0, 0, 0],

        [0, 0, 4, 14, 10, 0, 2, 0, 0],

        [0, 0, 0, 0, 0, 2, 0, 1, 6],

        [8, 11, 0, 0, 0, 0, 1, 0, 7],

        [0, 0, 2, 0, 0, 0, 6, 7, 0]

        ];

g.dijkstra(0);

##That is all about your answer.........please upvote my answer............please...................................