Classify the Hashing Functions based on the various methods by which the key value is found

Common multiple

Q: Given two numbers m and n, write a method to return the first number r that is
divisible by both (e.g., the least common multiple).

A:

The Approach:
What does it mean for r to be divisible by m and n? It means that all the primes in m must go into r, and all primes in n must be in r. What if m and n have primes in common?

For example, if m is divisible by 3^5 and n is divisible by 3^7, what does this mean about r? It means r must be divisible by 3^7.

The Rule: For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n, r must be divisible by p^max(a, b)

The Algorithm:
Define q to be 1.
for each prime number p less than m and n:
find the largest a and b such that p^a \ m and p^b \ n
let q = q * p^max(a, b)
return q

Which recursive sorting technique always makes recursive calls to sort subarrays that are about half size of the original array?

Answer: Mergesort always makes recursive calls to sort subarrays that are about half size of the original array, resulting in O(n log n) time.

Euclidean algorithm

Write an algorithm for finding the greatest common divisor of two integers.

Ans
function gcd( a,b : Integer ) returns Integer
{
if ( b != 0 )
return gcd( b, a mod b )
return abs(a)
}

Majority element

Given an array of size N ,we need to find the majority element if it exists ,as efficiently as possible. A majority element in an array of size N is any element which is present more than N/2 times.

Ans
Naive approach:

Just scan the array element wise and then make a count of the frequency of each of the distinct elements present in the array and if any element's count is more than N/2 then it is the majority element, otherwise it doesn't exist!!

One needn't ponder much on the complexity of this bruteforce approach.

This requires O(N) additional space and O(N) time.

Recursive Approach:

Here’s a divide-and-conquer algorithm:

function majority (A[1 . . . N])

if N = 1: return A[1]

let AL , AR be the first and second halves of A

ML = majority(AL ) and MR = majority(AR )

if neither half has a majority:

return ‘‘no majority’’

else:

check whether either ML or MR is a majority element of A

if so, return that element; else return ‘‘no majority’’

Divide a = a1a2 · · · aN by d using long division

Solution

B1 <-- a1 {Bi is what we divide d into in step i}
i <-- 1
while i <= N do
qi <-- largest integer such that d × qi <= Bi; {qi is the ith digit of the quotient q}
if i <= N − 1 then
Bi+1 <-- 10 × (Bi − d × qi) + ai+1
end if
i <-- i + 1;
end while
r <-- BN − d × qN {r is the remainder}

Algorithm Sum N numbers in a list (or array) named values

Solution
sum <-- 0;
index <-- 1;
while index <= N do
sum <-- sum + values[index ];
index <-- index + 1;
end while
print sum;

Algorithms Questions

1- Write a program to reverse a singly linked list

2- Write a program to delete a node in double linked list

3- Write a program to sort a linked list

4- Write a program to reverse a string

5- Write a program to insert a node a sorted linked list