What do you understand about greedy algorithms? List a few examples of greedy algorithms.
A greedy algorithm is a type of algorithmic method that seeks to select the best optimal decision at each sub-step, with the ultimate goal of arriving at a solution that is optimal across the board.
This indicates that the algorithm will always select the solution that provides the best possible outcome at the time, regardless of the repercussions.
To put it another way, when searching for an answer, an algorithm will always choose the immediate or local alternative that provides the greatest results.
Greedy algorithms may identify answers that are less than perfect for some situations of other problems; while finding the overall ideal solution for some idealistic problems.
In order to solve the problems presented by the following algorithms, the Greedy algorithm is utilised:
Prim’s Minimal Spanning Tree Algorithm
Kruskal’s Minimal Spanning Tree Algorithm
Travelling Salesman Problem
Fractional Knapsack Problem
Dijkstra’s Algorithm
Job Scheduling Problem
Graph Map Coloring
Graph Vertex Cover.
Write down an algorithm for adding a node to a linked list sorted in ascending order(maintaining the sorting property).
The following is a description of an algorithm for adding a node to a link list that is already sorted in ascending order while preserving its sorting property:
Step 1: First, determine whether or not the linked list contains any values (or is empty). If the answer is yes, then the new node will become the head of the tree, and you will return it.
Step 2: Check to see if the value of the node that is going to be inserted is lower than the value of the node that is going to be the head. If the answer is yes, then move it to the beginning of the chain and make it the head node.
Step 3: Step 3 is to locate the appropriate node that should be inserted in a loop following the input node so that the process can continue. To find the needed node, start at the head of the tree and go forward one node at a time until you get to a node whose value is greater than the value of the input node. The right node is the one that comes before it.
Step 4: Insert the node after you have determined which node is the proper one in step 3.
What do you understand by a searching algorithm? List a few types of searching algorithms.
Searching algorithms are put to use whenever an element needs to be located or extracted from a data structure (usually a list of elements). On the basis of the kind of search operation being performed, these algorithms are split into two categories:
Sequential Search is a method that goes through the list of elements in order, checking each one to see if it contains the element to be searched for, and reporting its findings if it does. One example of a Sequential Search Algorithm is something called Linear Search.
These algorithms were developed expressly for the purpose of exploring sorted data structures and are referred to as interval search. These sorts of search algorithms are significantly more effective than Sequential Search algorithms due to the fact that they consistently target the centre of the search structure and divide the search space in half. One type of Interval Search Algorithm that can be used is called Binary Search.
How do the encryption algorithms work?
Encryption is the process of converting plaintext into a format for a secret code that is known as “Ciphertext.”
This method involves converting the text using a string of bits, also known as “keys,” in order to perform calculations.
The larger the key, the greater the number of different combinations of characters that could be used to produce ciphertext.
The vast majority of encryption algorithms make use of fixed blocks of input ranging in length from 64 bits all the way up to 128 bits, while others employ the stream method.
Can we use the binary search algorithm for linked lists? Justify your answer.
No, the binary search algorithm cannot be utilised for linked lists in any way.
Explanation: In linked lists, random access is not permitted, so it is not possible to reach the middle element in constant or O(1) time.
As a direct consequence of this, applying a binary search algorithm to a linked list is not something that can be done.
Define insertion sort and selection sort.
Insertion Sort:
Insertion sort is a type of sorting that divides a list into sorted and unsorted subsections.
It does it by inserting one element at a time into the appropriate location inside the sorted sub-list.
The output is a sorted sub-list when the insertion has been completed.
It works through each element of an unsorted sublist iteratively and then adds those elements, in the correct order, to a sorted sublist.
Selection Sort:
The sorting method known as selection sort is one that is performed in-place.
It creates sorted and unsorted sublists from the original data collection that was provided.
After that, the least important item from the unsorted sub-list is chosen and added to the sorted list.
This continues to loop until every element from the unsorted sub-list has been used up by the sorted sub-list.
Describe the Linear Search Algorithm
A linear search is one method that can be utilised to locate an element within a collection of elements.
In order for it to function properly, it must move through the list of elements in order from the beginning to the finish and examine the characteristics of each element it comes across along the way.
Let us take into consideration the scenario of an array that has some entries that are integers. It is our goal to determine and then print the positions of all of the elements that are a match for a specific value (also known as the “key” for the linear search).
The linear search operates in this situation in a sequential manner, first matching each element with the number that progresses from the beginning to the end of the list, and then publishing the element’s location if the element that is now occupying that position is equivalent to the key.
The following is an algorithm that describes the Linear Search procedure:
Step 1: Iterate through the provided list of elements by using a loop.
Step 2: Perform a comparison of the target value (also known as the key-value) with the value that is currently contained in the list.
Step 3: If the values are the same, print out the current index of the array.
Step 4: If the values do not match, proceed to the following entry in the array.
Repeat Steps 1 through 4 until you have exhausted the whole list of components, which brings us to the fifth and final step.
The time complexity of the Linear Search Algorithm is O(n), where n is the size of the list of elements, and its space complexity is constant, that is, O, while the time complexity of the Linear Search Algorithm is O(n) (1).
Explain the binary search algorithm
In order to use binary search on a list of items, the list of elements must first be sorted.
This is a precondition for using binary search. The Divide and Conquer Algorithmic concept serves as the foundation for this approach.
In order to search the sorted list using the Binary Search Algorithm, we periodically cut the search interval in half at certain intervals.
To begin, we will construct an interval that is inclusive of the whole list. In the event that the value of the search key is lower than the value of the item that serves as the interval’s midpoint, the interval should be condensed to the lower half.
Aside from that, we only allow it to take up the upper half of the page. We continue to look for the value until either we find it or the interval becomes vacant.
The following is a description of an algorithm called Binary Search:
Step 1: The first thing that you should do is compare x to the element in the middle.
Step 2: Determine whether or not x matches the middle element and then return its index.
Step 3: Else Since the array is sorted in ascending order, the only place x can be found after the centre element is in the right half subarray. This is the case if x is greater than the element that is in the middle. As a consequence of this, we carry out the procedure once more for the right side.
Step 4: If the condition is not met, we will repeat the process for the left half (x is smaller).
Step 5: If the interval does not include any values, the binary search will be finished.
The Binary Search Algorithm has a time complexity of O(log(n), where n is the size of the list of entries, and its space complexity is constant, that is, O.
The Binary Search Algorithm also has a space complexity of O(1).
