211902007-algo-lab-uva problem-presentation.pptx

uva problems

1. Presented By : Name : Saidur Rahman Emon . ID : 211902007. Dept : Computer Science and Engineering. Course Name : Algorithms Lab. Course Code : CSE 206. Section : PC-213 DA. Presented To : Name : Md. Sultanul Islam Ovi. Designation : Lecturer. Dept : Computer Science and Engineering.

2. Problem Solving From UVA.

3. First Problem From UVA Problem 11953 - BFS/DFS: In this problem, you are given a grid representing a bat- tlefield with different types of cells, including empty cells and cells occupied by ships. My task is to determine the number of ships present in the battlefield by performing a Breadth-First Search (BFS) or Depth-First Search (DFS) algorithm. 3

4. Algorithm for first Problem : 4 Read the input grid and initialize a visited array to keep track of visited cells. Initialize a variable, count_ships , to 0. Define a function, traverse, which takes the current position (row, column) as input: If the current cell is out of bounds or already visited, return. Mark the current cell as visited. If the current cell contains a ship, increment count_ships . Recursively call traverse on adjacent cells (up, down, left, right). Iterate through each cell in the grid: If the cell is not visited and contains a ship: Increment count_ships . Call traverse on the current cell's position. Output the value of count_ships .

5. Source Code in Java for first problem : 5

6. Test Result/Output : 6 The input represents a single test case with a 5x5 grid. There are two ships in the grid. One ship is formed by the cells (0,0) and (1,3), and the other ship is formed by the cells (1,2) and (4,2). The program correctly identifies and counts these ships, resulting in an output of "Case 1: 2". Time Complexity : The time complexity of the solution for UVA P 11953 using a depth-first search (DFS) approach is O(n^2), where n is the size of the grid.

7. Second Problem From UVA : Problem 1208 - MST: This problem involves finding the Minimum Spanning Tree (MST) of a given graph. You are given a weighted, undirected graph where each edge represents a road between two cities and has a certain cost. The MST is the subset of edges that connects all the cities together with the minimum total cost. My task is to determine the MST and calculate the total cost of constructing the roads that form the MST.

8. Algorithm for Second Problem : Read the number of test cases, T. For each test case: Read the number of cities, N. Read the weight matrix of size N x N, representing the cost of building each road between cities. For each pair of cities ( i , j), where i < j: Add the edge ( i , j) with weight matrix[ i ][j] to a list of edges. Sort the list of edges in non-decreasing order by weight. Initialize an empty list, mst , to store the edges of the Minimum Spanning Tree. Initialize an array, parent, of size N to keep track of the parent city for each city in the MST. For each edge (u, v) in the sorted list of edges: If u and v are not already connected in the MST (by checking parent[u] and parent[v]): Add the edge (u, v) to the MST. Set parent[v] = u. Output the edges in the MST, along with their weights.

9. Source Code in Java for Second problem :

10. Test Result/Output : The input represents a single test case with 4 cities. The weight matrix indicates the cost of building roads between cities. The program constructs the Minimum Spanning Tree (MST) using Kruskal's algorithm. The output shows the MST edges and their weights. In this case, the MST consists of the edges A-B, A-C, and A-D, with weights 1, 2, and 3 respectively. Time Complexity : The time complexity of the solution for UVA P 1208 using the Minimum Spanning Tree (MST) approach is O(N^2 log N), where N is the number of cities.

11. Third Problem From UVA : Problem 612 - Sorting: The Sorting problem deals with arranging a list of DNA sequences based on their similarity. Each DNA sequence is represented by a string containing characters ’A’, ’C’, ’G’, or ’T’. Your goal is to sort the given list of DNA sequences in non-decreasing order of similarity. We need to implement an efficient sorting algorithm to rearrange the sequences and output the sorted list.

12. Algorithm for third Problem : Read the number of test cases, T. For each test case: Read the number of strings, N. Read N strings and store them in an array or list. Sort the array or list of strings based on the number of inversions in each string. Calculate the number of inversions for each string. Use a comparison-based sorting algorithm (e.g., quicksort, mergesort ) to sort the strings based on the number of inversions. Output the sorted strings for each test case.

13. Source Code in Java for third problem :

14. Test Result/Output : The program takes in two test cases. For each test case, it sorts the given strings based on the number of inversions. The sorted strings are then outputted. In the first test case, the strings " abcd ", " dcba ", and " bcda " are sorted based on the number of inversions: 0, 6, and 3 respectively. In the second test case, the strings " xyz " and " abc " are sorted lexicographically since they have the same number of inversions (0). Time Complexity : The time complexity of the solution for UVA P 612 using the sorting approach is O(N * M * log(N * M)), where N is the number of strings and M is the length of each string.

15. Thank You.