DAA 1, 2, 3 Units Notes PDF

## UNIT-1 ### Introduction - **Definition**: An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. - An algorithm must satisfy the following criteria/characteristics: 1. **Input**: 0 or more quantities are externally supplied. 2. **Output**: At least one quantity is produced. 3. **Definiteness**: Each instruction is clear and unambiguous. 4. **Finiteness**: Algorithm terminates after a finite number of steps. 5. **Effectiveness**: Every instruction must be basic (can be feasible). ### Areas of Study - **How to devise an algorithm?** - Generating an algorithm is an artifact that may never be fully automated. - **How to validate an algorithm?** - Once an algorithm is devised, it is necessary to compute the correct results for all possible legal inputs. - **How to analyze an algorithm?** - It refers to the task of determining how much computing time and storage an algorithm requires. - **How to test a program?** 1. **Debugging**: The process of executing programs on sample data sets to determine whether faulty results occur and, if so, to correct them. 2. **Profiling**: The process of executing a correct program on datasets and measuring the time and space it takes to compute the results. ### Pseudocode Conventions 1. **Comments**: Begin with // until at the end line. 2. **Blocks**: Are indicated with matching {} braces. 3. **Identifier**: Begins with a letter. Datatypes are not explicitly declared. 4. **Assignment of values**: Is done: (x=1) 5. **Boolean Values**: True and False 6. **Elements of multi-dimensional arrays**: Are accessed (A[I][J]) 7. **Loop Statements**: - For - While - Repeat until 8. **Conditional Statements**: Have the following forms: - if <condition> then <stmt 1> - eif <condition> then <stmt 1> else <stmt 2> - Case - if <condition 1> then <stmt 1> - if <condition n> then <stmt n> 9. **Input and Output**: Are done using the instructions - Input →read - Output →write 10. **Algorithm**: Only one type of procedure: - **Algorithm Name** (Parameter List) - **{** … body … **}** ### Sum of elements in an array ``` Algorithm Sum (A,n) { S:=0; for i:=1 to n do S:=S+ A[i]; return S; } ``` ### Algorithm to find the maximum of 'A' array values and size of an array ``` Algorithm max (A,n) { result := A[1]; for i:=2 to n do if (A[i] > result) then result: = A[i]; return result; } ``` ### Recursive Algorithm - **Direct Recursive**: An algorithm 'A' is said to be direct recursive if it calls itself. - **Indirect Recursive**: An algorithm 'A' is said to be indirect recursive if it calls another algorithm 'B' which in turn calls 'A'. ### Algorithm to solve the Towers of Hanoi Problem ``` Algorithm TOH (n,A,B,C) { if (n>=1) then TOH (n-1, A,B,C) write ("move top disk from tower", A, "to tower", B); TOH (n-1,C,B,A) } ``` ### Algorithm to find the factorial of a given number ``` Algorithm FACT (n) { if (n=1) then write ("factorial of", n, "is", 1); else return (n*fact(n-1)); } ``` ### Performance Analysis - Algorithm can be evaluated by its runtime performance. - Performance can be of two types: 1. **A priori estimates / performance analysis** 2. **Posteriori testing / performance measurement** - **Performance analysis** can be computed by: - **Space complexity**: The amount of memory an algorithm needs to run to completion. - **Time Complexity**: The amount of computer time an algorithm needs to run to completion. #### Space Complexity - **Space complexity** contains two parts: 1. **Fixed Part**: Independent of instance characteristics. Typically includes the dependent variables (constants) 2. **Variable Part**: Dependent on instance characteristics. - Space complexity of P is denoted by - **S(P) = C + Sp**, where: - **C**: Denotes the constants - **Sp**: Denotes the instance characteristics #### Time Complexity - **Time Complexity** of an algorithm is the amount of computer time it needs to run to completion. - **TC** contains two components: 1. **Compiletime** - Independent of instance characteristics. Once a compiled program, it will run several times without recompilation. 2. **Runtime** - Depends on instance characteristics. The time complexity of an algorithm (P) is - **T(P) = C + tP**, where: - C: Compiletime - t: Runtime complexity of a statement - **Comments**: Will occupy 'O' steps. - **Assignment Statement**: '1' steps. - **Condition Statement**: '1' steps. - **Loop Condition**: (n+1) steps. - **Body of Loop**: n steps ## UNIT-2 - Graphs ### Breadth First Search ``` Algorithm BFS(V) { u:=V; visited[V]:=1; repeat for all vertices w adjacent from u do if (visited [w]=0) then { Add w to q; visited [w]:=1; } if q is empty then return; delete u from q; until (false); } ``` ### Depth First Search ``` Algorithm DFS(V) { visited[V]:=1; for each vertex w adjacent from V do if (visited [w]=0) then DFS(w); } ``` ### Connected Components - If 'G' is a connected undirected graph then all vertices of 'G' are visited. - If 'G' is not connected, then for at least two calls of BFS, we will need to visit all vertices. ### Spanning Tree - Consider the problem of obtaining a spanning tree for an undirected graph 'G'. - A graph 'G' has a spanning tree if it is only a connected graph. - Let 'T' denote the set of the forward edges except (5,6) (6,8) (4,8). - The spanning tree obtained using BFS is called a Breadth First Spanning Tree. ### Biconnected Components and DFS - A vertex 'V' in a connected graph G is an articulation point if and only if the deletion of vertex 'V' together with all edges incident to 'V' disconnects the graph into two or more non-empty components. ### Greedy Method ``` Algorithm Greedy (a, n) { sol =∅; for i:=1 to n do x = select (a); if feasible (sol, x) then sol = union (sol, x); return sol; } ``` ### 0/1 Knapsack Problem - Consider the knapsack instance where n=3 and m=6. Profits are (P1, P2, P3) = (1, 2, 5) and weights (W1, W2, W3) = (2,3,4). #### Maximum Profit ``` x1 = 1 x2 = 2/15 x3 = 0 ΣP₁x₁ = P₁x₁ + P₂x₂ + P₃x₃ = 25*1 + 24*2 + 15*0 = 25 + 48 + 0 = 73 Profit = 73 ``` #### Minimum Weight ``` x3 = 1 x2 = 10/15 x1 = 0 ΣP₁x₁ = P₁x₁ + P₂x₂ + P₃x₃ = 25*0 + 24*10 + 15*1 = 0 + 240 + 15 = 255 Weight = 20 ``` #### Maximum P/W Ratio ``` x₂ = 1 x₃ = 5/10 x₁ = 0 ΣP₁x₁ = P₁x₁ + P₂x₂ + P₃x₃ =25* 0 + 24*1 + 15*½ = 0 + 24 + 7.5 = 31.5 Weight = 20 ``` ## UNIT-3 - Dynamic Programming ### Principle of Optimality A problem can be solved by taking a sequence of decisions to get the optimal solution. This is called the principle of optimality. ### All Pairs Shortest Path - Consider the graph below: - **A**: | 1 | 2 | 3 | 4 | |---|---|---|---| | 1 | 0 | 3 | ∞ | 7 | | 2 | ∞ | 0 | 2 | ∞ | | 3 | 5 | ∞ | 0 | 1 | | 4 | 2 | ∞ | ∞ | 0 | - **A¹**: | 1 | 2 | 3 | 4 | |---|---|---|---| | 1 | 0 | 3 | ∞ | 7 | | 2 | ∞ | 0 | 2 | ∞ | | 3 | 5 | 8 | 0 | 1 | | 4 | 2 | 5 | ∞ | 0 | - **A²**: | 1 | 2 | 3 | 4 | |---|---|---|---| | 1 | 0 | 3 | 5 | 7 | | 2 | ∞ | 0 | 2 | 15 | | 3 | 5 | 8 | 0 | 1 | | 4 | 2 | 5 | ∞ | 0 | ### Matrix Chain Multiplication - **Mᵢⱼ**: Denotes the cost of multiplying Aᵢ*…*Aⱼ where the cost is measured in the number of scalar multiplications. - Mᵢⱼ = 0, Mⱼᵢ = 0, and Mᵢₙ is the required solution. - The sequence of decisions can be built using the principle of optimality. - Let **T** be the true corresponding to the optimal way of multiplying Aᵢ…Aⱼ. It has a left subtree **I** and a right subtree **R**. - **L** corresponds to multiply Aᵢ…Aₖ and **R** corresponds to multiply Aₖ₊₁…Aⱼ for some integer k, such that i≤ k<j. - We will apply the following formula for computing the following sequence: ``` Mᵢⱼ = min {Mᵢₖ + Mₖ₊₁ⱼ + Pᵢ₋₁PₖPⱼ} ``` - Let: - A₁ = 5x4 - A₂ = 4x6 - A₃ = 6x2 - A₄ = 2x7 - Calculate `M₁₂`: - M₁₂ = min{M₁₁ + M₂₂ + P₀P₁P₂} - M₁₂ = min{0 + 0 + 5*4*6} - M₁₂ = 120 - Calculate `M₂₃`: - M₂₃ = min{M₂₂ + M₃₃ + P₁P₂P₃} - M₂₃ = min{0 + 0 + 4*6*2} - M₂₃ = 48 - Calculate `M₃₄`: - M₃₄ = min{M₃₃ + M₄₄ + P₂P₃P₄} - M₃₄ = min{0 + 0 + 6*2*7} - M₃₄ = 84 - Calculate `M₁₃`: - M₁₃ = min {M₁₂ + M₂₃ + P₀P₁P₃, M₁₁ + M₂₃ + P₀P₂P₃} - M₁₃ = min{120 + 0 + 5*4*2, 0 + 48 + 5*4*2} - M₁₃ = 180, M₁₃ = 88 - Calculate `M₂₄`: - M₂₄ = min{M₂₂ + M₃₄ + P₁P₂P₄, M₂₃ + M₃₄ + P₁P₃P₄} - M₂₄ = min{0 + 84 + 4*6*7, 48 + 84 + 4*2*7} - M₂₄ = 1024 - Calculate `M₁₄`: - M₁₄ = min {M₁₃ + M₄₄ + P₀P₁P₄, M₁₂ + M₃₄ + P₀P₂P₄, M₁₁ + M₃₄ + P₀P₃P₄} - M₁₄ = min{¹⁸⁰ + 0 + 5*4*7, 120 + 84 + 5*4*7, 0 + 84 + 5*6*7} - M₁₄ = 158 ## UNIT-4 - Travelling Salesperson Problem - Consider the graph below: | 1 | 2 | 3 | 4 | |---|---|---|---| | 1 | 0 | 10 | 15 | 20 | | 2 | 5 | 0 | 9 | 10 | | 3 | 6 | 13 | 0 | 9 | | 4 | 8 | 8 | 9 | 0 | ### Finding the shortest tour Using Dynamic Programming: - **g(i, S)**: The cost of the shortest path from node **i** to node 1, visiting all the nodes in set **S** exactly once. - The base cases are: - **g(1, { }) = 0** - **g(i, { i }) = Ci, 1** - **g(i, S)** is ∞ if node 1 is not in set **S**. - The recursive formula is: **g(i, S) = minj ∈ S, j≠i [Ci, j + g(j, S - {i }) ]** ``` g(1, {2, 3, 4}) = min {C1, 2 + g(2, {3, 4}), C1, 3+ g(3, {2, 4}), C1, 4+ g(4, {2, 3})} = min {10 + 25, 15 + 25, 20 + 23} = 35 ``` The shortest path is 1-2-4-3-1 which has a total cost of 35. ### Optimal Binary Search Trees - Let n=4. The probabilities of success (p) are: - P(1:4) = (3, 3, 1, 1). - P(0:4) = (2, 3, 1, 1, 1). - **Ci,j**: Probability of unsuccessful search. - **wi,j**: Weight of a node. - The base cases are: - **Ci,i = 0** - **Ci,j = 0** for i=j-1 - The recurrence relation is: **Ci,j = mink = ij-1[Ci,k + Ck+1,j + wi,j] ** - Calculate **C0,1**: - C0,1 = min[C0,0 + C1,1 + w0,1 , - C0,1 = min [0 + 0 + 8] - C0,1 = 8 - Calculate **C1,2**: - C1,2 = min[C1,1 + C2,2 + w1,2] - C1,2 = min[0 + 0 + 7] - C1,2 = 7 - Calculate **C2,3**: - C2,3 = min[C2,2 + C3,3 + w2,3] - C2,3 = min[ 0 + 0 + 3] - C2,3 = 3 - Calculate **C3,4**: - C3,4 = min[C3,3 + C4,4 + w3,4] - C3,4 = min[0 + 0 + 3] - C3,4 = 3 - Calculate **C0,2**: - C0,2 = min [C0,0 + C1,2 + w0,2, C0,1 + C2,2 + w0,2] - C0,2 = min[0 + 7 + 12, 8 + 0 + 12] - C0,2 = 19 - Calculate **C1,3**: - C1,3 = min[C1,1 + C1,3 + w1,3, C1,2 + C3,3 + w1,3] - C1,3 = min[0 + 12 + 9, 7 + 0 + 9] - C1,3 = 12 - Calculate **C2,4**: - C2,4 = min[C2,2 + C3,4 + w2,4, C2,3 + C4,4 + w2,4] - C2,4 = min[0 + 3 + 5, 3 + 0 + 5] - C2,4 = 8 - Calculate **C0,3**: - C0,3 = min[C0,0 + C1,3 + w0,3, C0,1 + C2,3 + w0,3, C0,2 + C3,3 + w0,3] - C0,3 = min[0 + 12 + 9, 8 + 3 + 9, 19 + 0 + 9] - C0,3 = 25 - Calculate **C0,4**: - C0,4 = min[C0,0 + C1,4 + w0,4, C0,1 + C2,4 + w0,4, C0,2 + C3,4 + w0,4, C0,3 + C4,4 + w0,4] - C0,4 = min[0 + 16, 8 + 8, 19 + 3, 25 + 0 + 11] - C0,4 = 32 **Multistage Graph:** - **V**: Set of vertices - **S**: Source vertex - **T**: Terminal vertex - **Cost(a, b)**: cost of going from vertex a to vertex b in the a'th stage. - `a` stands for stage number - `b` stands for vertex number - **d(i)**: Minimum cost to reach terminal vertex `t` from vertex `i`. - The cost of reaching vertex `t` from vertex `i` is the cost of the shortest path from vertex `i` to vertex `t`, where a path must pass exactly once through each stage. - The shortest path from each vertex in the first stage is calculated by considering all possible paths leading to the next stage and using the recurrence relation: ``` d(i) = min_{j ∈ Adj(i)}[c(i, j) + d(j)] ``` - Where `Adj(i)` is the set of adjacent vertices to vertex `i`. - Using the above formula, the cost of reaching the terminal vertex `t` can be computed starting from the last stage and moving backwards to the first stage. - In the given multistage graph, there are no outgoing edges (no paths) from vertices 5 and 12 in the last stage. Therefore: - **d(5) = 0** and **d(12) = 0**. - The cost of reaching `t` from the next stage is: - **d(4) = min{c(4,9) + d(9), c(4,10) + d(10), c(4,11) + d(11)}** - **d(4) = min{4 + 2, 2 + 5, 5 + 0}** - **d(4) = 4** - The cost of reaching `t` from the next stage is: - **d(3) = min{c(3,6) + d(6), c(3,7) + d(7), c(3,8) + d(8)}** - **d(3) = min{2 + 7, 7 + 5, 7 + 7}** - **d(3) = 9** - The cost of reaching `t` from the next stage is: - **d(2) = min{c(2, 2) + d(2), c(2, 3) + d(3), c(2, 4) + d(4), c(2, 5) + d(5)}** - **d(2) = min{5 + 9, 9 + 9, 4 + 4, 5 + 0}** - **d(2) = 9** - The cost of reaching `t` from the next stage is: - **d(1) = min{c(1, 2) + d(2), c(1, 3) + d(3), c(1, 4) + d(4), c(1, 5) + d(5)}** - **d(1) = min{7 + 9, 9 + 9, 10 + 4, 10 + 0}** - **d(1) = 16** - Therefore, the minimum cost to reach the terminal vertex `t` from the source vertex `S` is **d(1) = 16**.

DAA 1, 2, 3 Units Notes PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue