Foundation Course in Applications: Programming Concepts Dijkstra’s algorithm Dijkstra’s algorithm finds the shortest path from a particular node, called the source node to every other node in a connected graph. It produces a shortest path tree with the source node as the root. Algorithm Step 1: Start with a weighted graph Step 2 Choose a starting vertex and assign infinity path values to all other devices Step 3: Go to each vertex and update its path length Step 4: If the path length of the adjacent vertex is lesser than new path length, don't update it Step 5: Avoid updating path lengths of already visited vertices Step 6: After each iteration, we pick the unvisited vertex with the least path length. So we choose 5 before 7 Step 7: Notice how the rightmost vertex has its path length updated twice Step 8: Repeat until all the vertices have been visited Page 51 of 57 All Rights Reserved. Vol. TLE001/03-2022
Foundation Course in Applications: Programming Concepts Kruskal's algorithm 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? Algorithm Step 1: Start with a weighted graph Step 2 : Choose the edge with the least weight, if there are more than 1, choose anyone Step 3: Choose the next shortest edge and add it Step 4: Choose the next shortest edge that doesn't create a cycle and add it Step 5: Choose the next shortest edge that doesn't create a cycle and add it Page 52 of 57 All Rights Reserved. Vol. TLE001/03-2022
Foundation Course in Applications: Programming Concepts Step 6: Repeat until you have a spanning tree Page 53 of 57 All Rights Reserved. Vol. TLE001/03-2022
Foundation Course in Applications: Programming Concepts Prim’s algorithm Prim'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? Algorithm Step 1: Start with a weighted graph Step 2: Choose a vertex Step 3: Choose the shortest edge from this vertex and add it Step 4: Choose the nearest vertex not yet in the solution Step 5: Choose the nearest edge not yet in the solution, if there are multiple choices, choose one at random Step 6: Repeat until you have a spanning tree Page 54 of 57 All Rights Reserved. Vol. TLE001/03-2022
Foundation Course in Applications: Programming Concepts Dynamic Programming Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. Here, will discuss two patterns of solving dynamic programming (DP) problems: 1. Tabulation: Bottom Up 2. Memoization: Top Down Tabulation Method – Bottom Up Dynamic Programming As the name itself suggests starting from the bottom and accumulating answers to the top. Let’s discuss in terms of state transition. Let’s describe a state for our DP problem to be dp[x] with dp [0] as base state and dp[n] as our destination state. So, we need to find the value of destination state i.e dp[n]. If we start our transition from our base state i.e dp [0] and follow our state transition relation to reach our destination state dp[n], we call it the Bottom-Up approach as it is quite clear that we started our transition from the bottom base state and reached the topmost desired state. // Tabulated version to find factorial x. int dp[MAXN]; // base case int dp[0] = 1; for (int i = 1; i< =n; i++) { dp[i] = dp[i-1] * i; } Memoization Method – Top-Down Dynamic Programming Once, again let’s describe it in terms of state transition. If we need to find the value for some state say dp[n] and instead of starting from the base state that i.e dp [0] we ask our answer from the states that can Page 55 of 57 All Rights Reserved. Vol. TLE001/03-2022
Foundation Course in Applications: Programming Concepts reach the destination state dp[n] following the state transition relation, then it is the top-down fashion of DP. Here, we start our journey from the top most destination state and compute its answer by taking in count the values of states that can reach the destination state, till we reach the bottom-most base state. Once again, let’s write the code for the factorial problem in the top-down fashion // Memoized version to find factorial x. // To speed up we store the values // of calculated states // initialized to -1 int dp[MAXN] // return fact x! int solve(int x) { if (x==0) return 1; if (dp[x]!=-1) return dp[x]; return (dp[x] = x * solve(x-1)); } State Tabulation Memoization Code Speed State Transition relation is State transition relation is difficult to think easy to think Code gets complicated when Code is easy and less lot of conditions are required complicated Fast, as we directly access Slow due to lot of recursive previous states from the calls and return statements table Page 56 of 57 All Rights Reserved. Vol. TLE001/03-2022
Foundation Course in Applications: Programming Concepts Subproble If all subproblems must be If some subproblems in the m solving solved at least once, a subproblem space need not be bottom-up dynamic- solved at all, the memoized Table programming algorithm solution has the advantage of Entries usually outperforms a top- solving only those down memorized algorithm subproblems that are by constant factor definitely required In Tabulated version, starting Unlike the Tabulated version, from the first entry, all all entries of the lookup table entries are filled one by one are not necessarily filled in Memoized version. The table is filled on demand 3.4 Summary Today we have learned: ● Major Concepts of Object-Oriented Programming (OOPS) ● Complex Programming Algorithms with Data Structures and Algorithms 3.5Glossary ● Algorithm: a set of rules that must be followed when solving a particular problem ● Building Block: Building Block is a package of functionality defined to meet the business needs ● Lexicographical order: It is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a totally ordered set. 3.6References • https://www.tutorialspoint.com/data_structures_algorithms/ • https://www.geeksforgeeks.org/data-structures/ • https://www.programiz.com/dsa Page 57 of 57 All Rights Reserved. Vol. TLE001/03-2022
Search
