Algorithm Assignment Help
An algorithm is a set of rules to be followed to solve a given problem. The time complexity of an algorithm depends on how many times statements execute. Space complexity depends on how much maximum working storage or memory and algorithm needs. There are three important asymptotic representations for complexity.
Measures of Complexity
Big O refers to the upper bound of an algorithm. e.g., if an algorithm needs time of the order of n in the best case, and of the order of n2 in the worst case, then it is O(n2). A function f(n) is said to belong to the set O(g(n)) if there exists a constant c such that f(n) is less than cg(n), for sufficiently large n.
Ω notation, in this case, will be Ω(n) as Ω is the lower bound for the best case. A function f(n) is said to belong to the set Ω(g(n)) if there exists a constant c such that f(n) is greater than cg(n), for sufficiently large n.
Θ notation bounds the algorithm from both the upper side and lower side. e.g. if f(n) is the complexity function of the algorithm, g(n) is a function and c1 and c2 are two constants such that for sufficiently large n, c1g(n) < f(n) < c2g(n) then g(n) belongs to Θ (f(n)) limit of the algorithm.
Structures of Arrays, Lists
Arrays are sequences of elements with each place in it identified by its index, in absolute access.
A list is a sequence of elements with each place in it identified by its successor or predecessor, in relative access. Lists include elements called nodes. These may be linked singly or doubly or cyclic. The links can be implemented as pointers.
Searching for an Item in an Array or List
insertion sort works in arrays as follows
given unsorted Array
for j = 2 to Array.length
key = Array[j]
i = j – 1
while i > 0 and Array[i] > key
Array[i + 1] = Array[i]
i = i -1
Array[i + 1] = key
Now the Array is sorted in increasing order.
This makes only one swap during each pass through the array. It finds the smallest element and puts it in the correct potion. In the second pass, it finds the second smallest element and puts it in its correct place. Thus in the first pass, it checks all elements. In the next pass, it checks one element less and so on.
In this one pivot is taken and the array is divided into two parts with one part having values less than the pivot and the second part having values greater than the pivot. Then recursively each part is similarly subdivided using more pivots. Its complexity is n2. It is useful for large arrays
In this sort, we divide a list into two half lists. Then in recursion, each half is divided into further halves until atomic units can not be further subdivided. Then all units are merged two at a time in sorted order, each unit getting up to two atomic elements. Then again each resulting in two units are merged, each getting up to four elements each. This continues till all combine to form one unit. Its complexity is nlog(n).
Searching in a Graph
A graph is a set of vertices (called nodes) and lines (called edges).
it covers all nodes at the same level before going to a node at the next level. It uses a queue for moving first in first out. Its procedure is
A − Visit the next unvisited node at the same level. Mark it as visited. Display it. Insert it in a queue.
B − If no unvisited node at the same level is found, remove the first node from the queue. Go to the next level of this node
C− Repeat Rule A and Rule B until all nodes are visited and the queue is empty.
In the given example, Fig.Graph.1, it will go in sequence to A them B, C, D, E, F
Depth First Search
It goes depth-wise. It uses a stack. In the given example, Fig.Graph.1 it will go to A, B, D, E, C, F in that order. It is faster than BFS
Directed acyclic graphs can be sorted topologically. The nodes are ordered in a sequence, such that for every adjacent pair (u,v), u appears before v in the sequence. There can be more than one solution for a graph. For example, in Fig. Graph.2, two possible solutions are A, B, C, D, E, F and A, C, F, B, C, D.
A weighted Graph is similar to an ordinary graph with a weight added to each edge. We may need to find the shortest paths with the lowest cost or lowest weight in a weighted graph. The sum of the weights of all edges in this path should be minimum
We take a source node in a directed acyclic graph. Then we find the longest path from this to all nodes which can be reached from the source node. For this, we make a topological sort of graph. We give negative infinity weight to all nodes except the source node. Then we start with the source graph. All vertices connected with it and ahead are given weights. The weights should be the maximum of the previous weight of that node and the weight equal to the sum of the weight of the current node plus the weight of the edge. For example, if the old weight of node D is 10 and the new weight of D calculated from some node is 9, we keep the weight as 10. But if the new weight of D is 12, we change the weight of D to 12, as 12 is greater. This way we proceed forward, changing weights if new weights are found to be greater than old weights.
This algorithm can be used to find the shortest path from a source node to all other connected nodes or from a source node to some other node. Only positive weights are allowed. The procedure is to make weights of all nodes, except the source, equal to infinity. Make the weight of the source equal to zero. Then start with the source code. Make the weight of adjacent nodes of the old node equal to the weight of the old node plus the weight of the edge. However, if the adjacent node has a weight less than this new weight, retain the old less weight. Next go to the adjacent node not yet visited, with the least weight, and repeat the process till all nodes have been visited.
In a weighted digraph with possibly negative weights, the minimum distance from a source node to all other nodes can be found. In this, we first give weights infinity to all nodes except the source node. we start with the source graph and compute the weight of each node adjacent to it. Then we go to the next node and again compute the weights of all remaining nodes. If the new weight of any node is less than its previous value, we keep the new low value for that node. If there are n nodes in a graph, this process will be repeated n-1 times. Sometimes a negative cycle may be discovered. In this case, the shortest path is not possible.
A spanning tree is a part of a connected graph that has the minimum number of edges and all nodes are connected. There are no cycles in a spanning tree. A graph can have more than one possible spanning tree. All these spanning trees have the same number of nodes and edges. If even one edge is removed, it becomes disconnected and does not remain a spanning tree. Adding any edge will make a cycle. For example, in Fig.Graph.3, (1) is a graph, and (2), (3), and (4) are its spanning trees.
we assign weight 0 to the starting node. disconnect all edges. join all nodes adjacent to this node. Take the node with the lowest weight of these. Join all its adjacent nodes, except the edge that creates a cycle. Then again take the node with the lowest weight and repeat until all nodes are joined. If while joining a later node, the new weight of an adjacent edge is found less than its old weight, replace the old weight with the new weight. For example, in Fig.Graph.4 if we start with node A, then join adjacent B and F. Now B has a lower value so we join BC. Next, F has less value 6 so join FE. Now C has a lower value so CD. Now ED gives lower value so remove CD and join ED
Put all edges in increasing order. Take the first edge with the smallest weight which does not form a cycle. Then take the next edge with the smallest weight similarly. Continue this until all nodes are connected and there is no cycle. For example, in Fig.Graph.4, the sequence will be BF, ED, BC, CE, AF. Now FE gives less weight than CE so remove CE and join FE.
Binary Search Trees
A BST has the property that all nodes in the left subtree have values less than the parent node and all nodes in the right subtree have values greater than the parent node. For example, see Fig.Graph.5