Assignment of Advanced data structure and algorithms..pdf

1 . 2 . 3 . 4 . ● ● ● ● 1 . 2 . Assignment of ADSA. Answer 1: To find the largest element in a given array, you can follow these general steps: Initialize a variable to hold the largest value. You can set this variable to the first element of the array initially. Iterate through the array, comparing each element to the current largest value. Update the largest value if the current element is greater than the current largest value. Return the largest value after completing the iteration. Here's an example in Python: python Copy code def find_largest_element(array): if not array: raise ValueError("The array is empty") largest = array[0] for num in array: if num > largest: largest = num return largest In this function: largest is initially set to the first element of the array. We loop through each element (num) in the array. If num is greater than largest, we update largest. Finally, we return the largest value found. You can adapt this approach to other programming languages with similar logic. Answer 2: To reverse a given array, you can follow these steps: Create a new array to store the reversed elements, or Modify the array in place if you don't need to keep the original order. Here are methods to achieve this in different programming languages: Python Using slicing (creates a new reversed array): python Copy code def reverse_array(arr): return arr[::-1] In-place reversal:

python Copy code def reverse_array_in_place(arr): left, right = 0, len(arr) - 1 while left < right: arr[left], arr[right] = arr[right], arr[left] left += 1 right -= 1 return arr JavaScript Using the reverse method (modifies the original array): javascript Copy code function reverseArray(arr) { return arr.reverse(); } Java Using a loop to reverse in place: java Copy code public class Main { public static void reverseArray(int[] arr) { int left = 0; int right = arr.length - 1; while (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } } C++ Using a loop to reverse in place: cpp Copy code #include <algorithm> // For std::swap

. . ○ ○ void reverseArray(int arr[], int size) { int left = 0; int right = size - 1; while (left < right) { std::swap(arr[left], arr[right]); left++; right--; } } Each method effectively reverses the order of the elements in the array. Choose the one that best fits your needs based on whether you want to modify the array in place or create a new reversed array. Answer 3: To find the second largest element in a given array, you can follow these steps: Initialize two variables: one for the largest element and one for the second largest element. Set both initially to a very low value or the smallest possible value for your data type. Iterate through the array. For each element: If the element is greater than the current largest element, update the second largest to be the current largest and then update the largest to this new element. If the element is not the largest but is greater than the second largest, update the second largest. Here is how you can implement this in various programming languages: Python python Copy code def find_second_largest(arr): if len(arr) < 2: raise ValueError("Array must contain at least two elements") largest = second_largest = float('-inf') for num in arr: if num > largest: second_largest = largest largest = num elif num > second_largest and num != largest: second_largest = num

if second_largest == float('-inf'): raise ValueError("There is no second largest element") return second_largest JavaScript javascript Copy code function findSecondLargest(arr) { if (arr.length < 2) { throw new Error("Array must contain at least two elements"); } let largest = -Infinity; let secondLargest = -Infinity; for (let num of arr) { if (num > largest) { secondLargest = largest; largest = num; } else if (num > secondLargest && num < largest) { secondLargest = num; } } if (secondLargest === -Infinity) { throw new Error("There is no second largest element"); } return secondLargest; } Java java Copy code public class Main { public static int findSecondLargest(int[] arr) { if (arr.length < 2) { throw new IllegalArgumentException("Array must contain at least two elements");

} int largest = Integer.MIN_VALUE; int secondLargest = Integer.MIN_VALUE; for (int num : arr) { if (num > largest) { secondLargest = largest; largest = num; } else if (num > secondLargest && num < largest) { secondLargest = num; } } if (secondLargest == Integer.MIN_VALUE) { throw new IllegalArgumentException("There is no second largest element"); } return secondLargest; } } C++ cpp Copy code #include <iostream> #include <limits.h> int findSecondLargest(int arr[], int size) { if (size < 2) { throw std::invalid_argument("Array must contain at least two elements"); } int largest = INT_MIN; int secondLargest = INT_MIN; for (int i = 0; i < size; ++i) { if (arr[i] > largest) { secondLargest = largest;

largest = arr[i]; } else if (arr[i] > secondLargest && arr[i] < largest) { secondLargest = arr[i]; } } if (secondLargest == INT_MIN) { throw std::invalid_argument("There is no second largest element"); } return secondLargest; } Each of these implementations assumes that there are at least two distinct elements in the array. If there are fewer than two distinct values, the function will indicate that a second largest element cannot be determined. Answer 4: To check if a given array is sorted, you need to determine if the array is sorted in either ascending or descending order. Here’s how you can implement this check in various programming languages: Python python Copy code def is_sorted(arr): if len(arr) < 2: return True ascending = all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1)) descending = all(arr[i] >= arr[i + 1] for i in range(len(arr) - 1)) return ascending or descending JavaScript javascript Copy code function isSorted(arr) { if (arr.length < 2) return true; let ascending = true; let descending = true;

for (let i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) ascending = false; if (arr[i] < arr[i + 1]) descending = false; } return ascending || descending; } Java java Copy code public class Main { public static boolean isSorted(int[] arr) { if (arr.length < 2) return true; boolean ascending = true; boolean descending = true; for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) ascending = false; if (arr[i] < arr[i + 1]) descending = false; } return ascending || descending; } } C++ cpp Copy code #include <iostream> #include <vector> bool isSorted(const std::vector<int>& arr) { if (arr.size() < 2) return true; bool ascending = true; bool descending = true;

. . . for (size_t i = 0; i < arr.size() - 1; ++i) { if (arr[i] > arr[i + 1]) ascending = false; if (arr[i] < arr[i + 1]) descending = false; } return ascending || descending; } Explanation Ascending Check: Iterate through the array and ensure that every element is less than or equal to the next element. Descending Check: Iterate through the array and ensure that every element is greater than or equal to the next element. Return Result: If the array meets either the ascending or descending condition, it is considered sorted. These implementations will return true if the array is sorted in either ascending or descending order, and falseotherwise. Answer 5: To remove duplicates from a given array, you can use various methods depending on the programming language and requirements. Here are some common approaches: Python Using a Set: python Copy code def remove_duplicates(arr): return list(set(arr)) This method leverages Python's set data structure to automatically remove duplicates. The list function converts the set back into a list. Using a List Comprehension (preserving order): python Copy code def remove_duplicates(arr): seen = set() result = [] for item in arr: if item not in seen: result.append(item) seen.add(item)

return result This method maintains the original order of elements while removing duplicates. JavaScript Using a Set: javascript Copy code function removeDuplicates(arr) { return [...new Set(arr)]; } This method uses JavaScript's Set to automatically filter out duplicates and then spreads the set back into an array. Using a Loop (preserving order): javascript Copy code function removeDuplicates(arr) { let seen = new Set(); let result = []; for (let item of arr) { if (!seen.has(item)) { result.push(item); seen.add(item); } } return result; } This method preserves the order of elements while removing duplicates. Java Using a Set: java Copy code import java.util.*; public class Main { public static List<Integer> removeDuplicates(List<Integer> list) { Set<Integer> set = new HashSet<>(list); return new ArrayList<>(set); } }

This method uses a HashSet to filter out duplicates and then converts it back to a List. Using a Loop (preserving order): java Copy code import java.util.*; public class Main { public static List<Integer> removeDuplicates(List<Integer> list) { Set<Integer> seen = new HashSet<>(); List<Integer> result = new ArrayList<>(); for (Integer item : list) { if (seen.add(item)) { result.add(item); } } return result; } } This method preserves the order of elements while removing duplicates. C++ Using a Set: cpp Copy code #include <vector> #include <set> #include <algorithm> std::vector<int> removeDuplicates(const std::vector<int>& vec) { std::set<int> unique_set(vec.begin(), vec.end()); return std::vector<int>(unique_set.begin(), unique_set.end()); } This method uses a std::set to remove duplicates and then converts it back to a std::vector. Using Sorting and Unique (preserving order): cpp Copy code #include <vector> #include <algorithm>

std::vector<int> removeDuplicates(std::vector<int> vec) { std::sort(vec.begin(), vec.end()); auto last = std::unique(vec.begin(), vec.end()); vec.erase(last, vec.end()); return vec; } This method first sorts the array, then uses std::unique to remove duplicates, and finally erases the duplicates. Each method has its own advantages depending on whether you need to maintain the order of elements or are okay with any order. Answer 6: To rotate a given array, you can shift the elements of the array by a certain number of positions. Depending on the direction (left or right) and the number of positions to rotate, the approach may differ. Here’s how you can do it in various programming languages: Python Rotate Array to the Right by k Positions: python Copy code def rotate_right(arr, k): n = len(arr) k = k % n # Handle cases where k is greater than the length of the array return arr[-k:] + arr[:-k] Rotate Array to the Left by k Positions: python Copy code def rotate_left(arr, k): n = len(arr) k = k % n # Handle cases where k is greater than the length of the array return arr[k:] + arr[:k] JavaScript Rotate Array to the Right by k Positions: javascript Copy code function rotateRight(arr, k) { const n = arr.length; k = k % n; // Handle cases where k is greater than the length of the array

return arr.slice(-k).concat(arr.slice(0, -k)); } Rotate Array to the Left by k Positions: javascript Copy code function rotateLeft(arr, k) { const n = arr.length; k = k % n; // Handle cases where k is greater than the length of the array return arr.slice(k).concat(arr.slice(0, k)); } Java Rotate Array to the Right by k Positions: java Copy code import java.util.Arrays; public class Main { public static void rotateRight(int[] arr, int k) { int n = arr.length; k = k % n; // Handle cases where k is greater than the length of the array reverse(arr, 0, n - 1); reverse(arr, 0, k - 1); reverse(arr, k, n - 1); } private static void reverse(int[] arr, int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } } Rotate Array to the Left by k Positions: java Copy code

import java.util.Arrays; public class Main { public static void rotateLeft(int[] arr, int k) { int n = arr.length; k = k % n; // Handle cases where k is greater than the length of the array reverse(arr, 0, k - 1); reverse(arr, k, n - 1); reverse(arr, 0, n - 1); } private static void reverse(int[] arr, int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } } C++ Rotate Array to the Right by k Positions: cpp Copy code #include <vector> #include <algorithm> void rotateRight(std::vector<int>& arr, int k) { int n = arr.size(); k = k % n; // Handle cases where k is greater than the length of the array std::reverse(arr.begin(), arr.end()); std::reverse(arr.begin(), arr.begin() + k); std::reverse(arr.begin() + k, arr.end()); } Rotate Array to the Left by k Positions: cpp Copy code

. . ○ ○ #include <vector> #include <algorithm> void rotateLeft(std::vector<int>& arr, int k) { int n = arr.size(); k = k % n; // Handle cases where k is greater than the length of the array std::reverse(arr.begin(), arr.begin() + k); std::reverse(arr.begin() + k, arr.end()); std::reverse(arr.begin(), arr.end()); } Explanation Modular Arithmetic: k % n ensures that the rotation amount k is within the bounds of the array length. Reversal Method: Right Rotation: Reverse the whole array, then reverse the first k elements and the remaining n - k elements. Left Rotation: Reverse the first k elements, reverse the remaining n - k elements, then reverse the whole array. These methods efficiently rotate the array in-place or return a new rotated array depending on the approach used. Answer 7: To find the frequency of elements in a given array, you can use a hash map (or dictionary) to count occurrences of each element. This approach works efficiently in most programming languages. Below are implementations for various languages: Python Using a dictionary: python Copy code from collections import Counter def count_frequencies(arr): return dict(Counter(arr)) Using a manual approach: python Copy code def count_frequencies(arr): frequency = {}

for item in arr: if item in frequency: frequency[item] += 1 else: frequency[item] = 1 return frequency JavaScript Using an object: javascript Copy code function countFrequencies(arr) { const frequency = {}; arr.forEach(item => { frequency[item] = (frequency[item] || 0) + 1; }); return frequency; } Java Using a HashMap: java Copy code import java.util.HashMap; import java.util.Map; public class Main { public static Map<Integer, Integer> countFrequencies(int[] arr) { Map<Integer, Integer> frequencyMap = new HashMap<>(); for (int num : arr) { frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1); } return frequencyMap; } } C++ Using an unordered_map: cpp Copy code #include <vector>

. . . #include <unordered_map> std::unordered_map<int, int> countFrequencies(const std::vector<int>& arr) { std::unordered_map<int, int> frequencyMap; for (int num : arr) { frequencyMap[num]++; } return frequencyMap; } Explanation Hash Map (or Dictionary): This data structure allows you to store key-value pairs, where keys are array elements, and values are their counts. Iteration: Traverse through the array and update the count of each element in the hash map. Get Frequency: After processing the array, the hash map contains each unique element and its frequency. These methods provide a simple and efficient way to count the occurrences of each element in an array. Answer 8: #include <vector> std::vector<int> mergeSortedArrays(const std::vector<int>& arr1, const std::vector<int>& arr2) { std::vector<int> merged; size_t i = 0, j = 0; while (i < arr1.size() && j < arr2.size()) { if (arr1[i] < arr2[j]) { merged.push_back(arr1[i]); i++; } else { merged.push_back(arr2[j]); j++; } } // Add remaining elements merged.insert(merged.end(), arr1.begin() + i, arr1.end()); merged.insert(merged.end(), arr2.begin() + j, arr2.end());

. . . . return merged; } Explanation Two Pointers: Initialize two pointers (i and j) to traverse both arrays. Comparison: Compare elements from both arrays and append the smaller element to the merged array. Remaining Elements: Once one array is exhausted, append the remaining elements from the other array. Efficiency: This approach runs in O(n + m) time, where n and m are the lengths of the two arrays, making it efficient for merging sorted arrays. This method ensures that the merged array is also sorted, leveraging the fact that both input arrays are already sorted.

Assignment of Advanced data structure and algorithms..pdf

More Related Content

Similar to Assignment of Advanced data structure and algorithms..pdf

More from vishuv3466

Recently uploaded

Assignment of Advanced data structure and algorithms..pdf