Consider the following hash function: which is used in a Hash Table which has linear probing implemented (with a standard probe step size of 1). Also, consider the following strings: Calculate and state the hash value of the above strings. Explain and show how they are inserted into the table (using the same order of insertion). State what happens when you search for the strings "python", "java" and "program". Ord values: h: 104, w: 119, p: 112, t: 116

Leave your answer below as a comment

Answer: For a sorting algorithm to be stable, it is expected that the relative order of items will remain the same, i.e. when 2 or more items have the same value in an unsorted list, the one which had a lower index in the unsorted list is first.   During the insertion process, when an element (pivot) is being compared to the sorted elements of the list, it will only move past elements which are greater than it, not elements which are less than or equal to it. Hence, insertion sort is stable because when 2 or more items have the same value, the relative order of items remains unchanged.    Alternative Answer: For a sorting algorithm to be stable, it is expected that the relative order of items will remain the same. Insertion sort is stable because of the strict < (Should be >) comparison in the code (elements are only swapped if they are less than the other element, so equal elements are not swapped and the relative order is maintained). Using <=…

Answer: An algorithm is incremental if it does not need to recompute everything after a small change (like a new element is added).  Insertion sort traverses through unchanged element, stores the new element into a temporary variable and loop from right to left to find the correct position. The new element is then inserted to the list. Insertion sort is incremental when the new element is added at the back of the list.   To add on:   Because all original sorted elements would not move as they stop on the first comparison, only when it reaches the new element (last element) does a sequence of swapping and comparing occur, and since it is the last element, the sorting algorithm knows the list is already sorted.  

1. Example: [5, 20, -5, 10, 3] [5, 20, -5, 10, 3] because in the first iteration, it compares 5 and 20, and since 20 is greater than 5 it stays in the same position.   2. Example: [-7,-1,-4,4,5,6] Answer:   [-7,-1,-4,4,5,6] -> List remains unchanged as -7 at index 0 is smaller than index 1.

Answer: Best: O(n) where n is the number of elements in the array occurs if the array is already sorted. The algorithm will store temp, then compare with the element to the left of it in the sorted partition. Since temp is greater than the element in the sorted partition, it will essentially do nothing because it’s already in correct order. It will repeat this for n elements in the array. Worst: O(n2) where n is the number of elements in the array. Worst case occurs if the array is sorted in reverse order. For every unsorted element, the algorithm will then have to traverse the entire sorted partition from right to left until it finds the correct position for temp (which is at the beginning). If the program has to traverse the entire sorted partition (O(n)) for n elements, we get O(n2)

Answer: Best case O(n) Worst case O(n2)

Answer: Each iteration will increase the number of elements in the sorted partition by 1   Alternative Answer: In one iteration of Insertion Sort, the algorithm takes the next element from the unsorted portion of the list and inserts it into its correct position within the sorted portion. This involves: Comparing the element with each item in the sorted portion (from right to left). Shifting elements in the sorted portion to the right if they are greater than the element. Inserting the element into the correct position.   This process expands the sorted portion by one element after each iteration.  

Answer:   Consider the first element as “sorted” (might not necessarily be true)   Create temp variable for first unsorted number   Check over each number in the sorted partition (decrementing right to left)   If the decremented element is greater than temp, shift it to the right by 1 spot.   Once the decremented element is less than or equal to temp, overwrite the number after the decremented element with temp, thus “inserting” it.

Answer:incremental   An algorithm is said to be incremental if it does not need to recompute everything after a small change/if the algorithm can return a sorted list with the new element within one or few iterations.