Algorithms and Data structure Programs
Input is taken from a input file and Output is given in the output file.
1.1 Find out the individual factorial of a set of n numbers given in the list. First number in input file is the value of n. PythonProgver1  PythonProgver2   PythonProgver3
Pythonprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Javaprogver9  Input File  
1.2 Print the series of first n factorial numbers starting from 1, 2, 3.. n PythonProgver1  PythonProgver2   PythonProgver3
Cprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
1.3 Find the factorial of given n numbers using sterling formula. Fist number in input file gives value of n PythonProgver1  PythonProgver2   PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
1.4 Find the factorial of a number without using multiplication PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  
Input File  
1.5 Find the double factorial of k written as k!!. PythonProgver1  PythonProgver2  
PythonProgver3
Cprogver4  Cprogver5  Javaprogver6
Javaprogver7  CPPprogver8  Input File  
1.6 Write an efficient program to find where value of n, k, r are given. First Number in input file represents number of such terms. (n!k!)/ r! PythonProgver1  PythonProgver2   PythonProgver3
Javaprogver4  Javaprogver5  CPPprogver6
Javaprogver7  Input File  
1.7 A multifactorial is a generalization of the double factorial e.g. n!!!!= n(n-4)(n-8)(n-12).till any positive number. Write an efficient program if we have the value of n and value of k where k is the number of multifactorial which is to be subtracted every time from n. First number gives number of such sets given. PythonProgver1  PythonProgver2   PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
1.8 Write an efficient program if given a set of n positive integer number, whether the given number is factorial of some other number or not. First number represents n. PythonProgver1  PythonProgver2  CPPprogver3
Javaprogver4  Javaprogver5  CPPprogver6
Javaprogver7  Input File  
1.9 Write an efficient program to find out the sum of first n factorials. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
1.10 Write an efficient program to find out the product of first n factorials. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
CPPprogver7  Input File  
2.1 Write an efficient program to find out and print the Fibonacci number of at the positions given in a set of n numbers given in the list. First number in the file represents n. PythonProgver1  PythonProgver2  PythonProgver3
Pythonprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Javaprogver9  Input File  
2.2 Write an efficient program to print the series of first n Fibonacci numbers starting from 1,2,3. n PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
2.3 Write an efficient program to find the Fibonacci number of given n numbers using golden ratio formula. First number represents n PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
2.4 Write an efficient program to find the Fibonacci value of a number using matrix multiplication. PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
2.5 Write an efficient program to find the first n Fibonacci numbers which are prime also. PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Cprogver5  Javaprogver6
Javaprogver7  CPPprogver8  Input File  
2.6 Write an efficient program to find factorial of first n Fibonacci primes. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  CPPprogver6
Javaprogver7  Input File  
2.7 Write an efficient program to print Fibonacci number corresponding to the first n numbers in the Fibonacci series. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
2.8 Write an efficient program given a set of n positive integers, find that whether the number is one of the Fibonacci numbers. First number represents n PythonProgver1  PythonProgver2  CPPprogver3
Javaprogver4  Javaprogver5  CPPprogver6
Javaprogver7  Input File  
2.9 Write an efficient program to print the sum of first n Fibonacci numbers. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
2.10 Write an efficient program to print the product of first n Fibonacci numbers. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
CPPprogver7  Input File  
3.1 Write an efficient program to print first n prime numbers. PythonProgver1  PythonProgver2  PythonProgver3
Pythonprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Javaprogver9  Input File  
3.2 Write an efficient program, given a set of n positive integers, find that whether the number is one of the prime numbers or not. First number is n. PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
3.3 Write an efficient program for writing first n prime numbers which are Fibonacci numbers also. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
CPPprogver7  Javaprogver8  Input File  
3.4 Write an efficient program for writing all primes below a given number. PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
3.5 Write an efficient program for writing first prime number greater than a given number. PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Cprogver5  Javaprogver6
Javaprogver7  CPPprogver8  Input File  
3.6 Write an efficient program to find out the prime factors of a given set of n numbers. First number gives number of n. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Input File  
3.7 Primorial numbers are factorials of prime numbers. Write an efficient program to find out the factorial of first n prime numbers which will generate a series of first n primorials. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
3.8 Write an efficient program to find the sum of first n prime numbers. PythonProgver1  PythonProgver2  CPPprogver3
Javaprogver4  Javaprogver5  CPPprogver6
Javaprogver7  Input File  
3.9 Write an efficient program to find the product of first n prime numbers. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
3.10 Write an efficient program to print the nth prime of the first m numbers of Prime series. For example first prime is 2 so print 2nd prime, second prime is 3 so print 3rd prime and so on. PythonProgver1  PythonProgver2  PythonProgver3
CPPprogver4  Javaprogver5  Javaprogver6
CPPprogver7  Input File  
4.1 Given a number m, write all the values corresponding to the first n Fibonacci exponents of that number. PythonProgver1  PythonProgver2  PythonProgver3
Pythonprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Javaprogver9  Input File  
4.2 Given a number m, write all the values corresponding to the first n prime exponents of that number. PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
4.3 Given a number and an exponent write all the values of powers of that number from one to given number. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
4.4 Given two numbers x and y, find the value of x exponent y (or x power y). PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
4.5 Given two numbers x and y find xy + yx and xy - yx and x y / yx and xy * yx PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Cprogver5  Javaprogver6
Javaprogver7  CPPprogver8  Input File  
4.6 Given a number n, find the sum of numbers from 1 to n. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  CPPprogver6
Javaprogver7  Input File  
4.7 Given a number n, find the sum of squares of numbers from 1 to n. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
4.8 Given a number n, find the sum of cubes of numbers from 1 to n. PythonProgver1  PythonProgver2  CPPprogver3
Javaprogver4  Javaprogver5  CPPprogver6
Javaprogver7  Input File  
4.9 Given a number n, find the sum of inverse of numbers from 1 to n. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
4.10 Given a number n, find the sum of series of exponents of 2 from 1 to n. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
CPPprogver7  Input File  
5.1 Write an efficient program to find the octal equivalent of a series of decimal numbers from m to n. PythonProgver1  PythonProgver2  PythonProgver3
Pythonprogver4  Cprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Javaprogver9  Input File  
5.2 Write an efficient program to find the octal equivalent of a series of binary numbers from m to n. PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
5.3 Write an efficient program to find the octal equivalent of a series of hexadecimal numbers from m to n. PythonProgver1  PythonProgver2  PythonProgver3
CPPprogver4  Javaprogver5  Javaprogver6
CPPprogver7  Javaprogver8  Input File  
5.4 Write an efficient program to find the hexadecimal equivalent of a series of binary number from m to n. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
5.5 Write an efficient program to find the hexadecimal equivalent of a given series of decimal number from m to n. PythonProgver1  PythonProgver2  PythonProgver3
Cprogver4  Cprogver5  Javaprogver6
Javaprogver7  CPPprogver8  Input File  
5.6 Write an efficient program to find the hexadecimal equivalent of a given series of octal numbers from m to n. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Input File  
5.7 Write an efficient program to find the decimal equivalent of a given series of binary numbers from m to n. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
5.8 Write an efficient program to find the decimal equivalent of a given series of octal number from m to n. PythonProgver1  PythonProgver2  CPPprogver3
Javaprogver4  Javaprogver5  CPPprogver6
Javaprogver7  Input File  
5.9 Write an efficient program to find the decimal equivalent of a given series of hexadecimal numbers from m to n. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  CPPprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
5.10 Write an efficient program to find the binary equivalent of a given decimal number from m to n. PythonProgver1  PythonProgver2  PythonProgver3
Javaprogver4  Javaprogver5  Javaprogver6
CPPprogver7  Input File  
6.1 Write an efficient program to find out the root of quadratic equation with coefficients as a,b and c. PythonProgver1  PythonProgver2  PythonProgver3
CPPprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
6.2 Write an efficient program to find out the Greatest common divisor using recursion for all values of (m, n) where m varies from x to y and n varies from p to q PythonProgver1  PythonProgver2  Input File  
6.3 Write an efficient program to find the binary equivalent of a given series of octal numbers from m to n. PythonProgver1  PythonProgver2  Input File  
6.4 Write an efficient program to find the binary equivalent of a given series of hexadecimal numbers from m to n. PythonProgver1  PythonProgver2  Input File  
6.5 Write an efficient program to find out the compound interest if rate of interest, principal amount, number of years is given. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
6.6 Given a number print the table of nth number from 1 to 10 in a proper format. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
6.7 Given a number print n sequences of m each such that the sequences are of the form
n,n+1,n+2.n+m
n,n+2,n+4.n+2m
n,n+3,n+6.n+3m
..
PythonProgver1  PythonProgver2  PythonProgver3
Input File  
6.8 Write an efficient program if given a number x, find out the sum of the first n terms of geometric series 1+x+x2+x3+x4+.. PythonProgver1  PythonProgver3
Input File  
6.9 Write an efficient program if given a number x, find out the sum of n terms of arithmetic progression x+(x+d)+(x+2d)+(x+3d).. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
6.10 Write an efficient program to find the floor of the mean of given set of n numbers. First number gives n. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
7.1 Write an efficient program to find the maximum of a given set of n numbers. First number gives n. PythonProgver1  PythonProgver2  PythonProgver3
CPPprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Cprogver8  Input File  
7.2 Write an efficient program to print the sum of the individual digits of numbers from m to n. PythonProgver1  PythonProgver2  Input File  
7.3 Write an efficient program to print the reverse of a given numbers from m to n. PythonProgver1  PythonProgver2  Input File  
7.4 Write an efficient program to find which numbers from range m to n are perfect numbers. A perfect number is a positive integer that is equal to the sum of it divisors. However, for the case of a perfect number, the number itself is not included in the sum. For example divisors of 6 are 1,2 and 3 and their sum is 6. PythonProgver1  PythonProgver2  Input File  
7.5 Write an efficient program to find whether a given set of n numbers is a triangular number or not. first number is n. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
7.6 Write an efficient program to find the smallest and the next smallest number in an array. First number gives the size. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
7.7 Write an efficient program to find whether a given number is present in the given list of numbers or not. First number is the number to be found from the remaining list of numbers. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
7.8 Write an efficient program to convert a number to sum of the ASCII values of its digits. PythonProgver1  Input File  
7.9 Write an efficient program to do bitwise ANDing of two given binary numbers. PythonProgver1  PythonProgver2  Input File  
7.10 Write an efficient program to do bitwise ORing of two given numbers. PythonProgver1  PythonProgver2  Input File  
8.1 An array of size n consists of unique records where the record consists of numbers consisting of three digits from 800 to 999. Insert m numbers from 1 to 100 at given positions. Count the total number of shifts in your program. Print time taken, Memory Used. Also print the size of the array and the array itself at the end of the program. First Number gives n and second gives m PythonProgver1  PythonProgver2  PythonProgver3
CPPprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
8.2 An array of size n consists of unique records where the record consists of numbers consisting of three digits from 800 to 999. Delete m numbers at given positions. Count the total number of shifts in your program. Print time taken, Memory Used. Also print the size of the array and the array itself at the end of the program. First Number gives n and second gives m PythonProgver1  PythonProgver2  Input File  
8.3 An array of size n consists of records where the record consists of numbers consisting of three digits from 900 to 999. Delete m given numbers. All the occurrences of that number are to be deleted. Count the total number of shifts in your program. Print time taken, Memory Used. Also print the size of the array and the array itself at the end of the program. First Number gives n and second gives m PythonProgver1  PythonProgver2  Input File  
8.4 An array of size n consists of records where the record consists of numbers consisting of three digits from 900 to 999. Insert m numbers again from the same range at given positions. Count the total number of shifts in your program. Print time taken, Memory Used. Also print the size of the array and the array itself at the end of the program. First Number gives n and second gives m PythonProgver1  PythonProgver3
Input File  
8.5 A stack of size n (To be implemented using an array) consists of unique records where the record consists of numbers consisting of three digits from 800 to 999. Push m given numbers at given position. Also Delete m elements from the specified given position from the stack. Count the total number of push and pop in your program. Print time taken, Memory Used. Also print the size of the stack and the stack itself at the end of the program. First Number gives n and second gives m PythonProgver1  PythonProgver2  PythonProgver3
Input File  
8.6 A Queue of size n (Implemented with an array) consists of unique records where the record consists of numbers consisting of three digits from 800 to 999. Insert m numbers from 1 to 100 in the queue. Each insertion should be followed by one dequeue. Count the total number of operations in your program. Print time taken, Memory Used. Print the size of the queue and the queue itself at the end of the program. First Number gives n and second gives m PythonProgver1  PythonProgver2  Input File  
8.7 You have an array A of size N. Write a routine that shuffles all the elements of the array in-place. The only restrictions are that all possible permutations of A must be possible and equally likely. First number given values of N. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
8.8 Suppose that each row of an mXn array A consists of 1?s and 0?s such that in any row i of A, all the 1?s come before any 0?s in that row. Suppose further that the number of 1?s in the row i is less than or equal to the number in row i+1, for i = 0,1,n-2. Assuming A is already in memory, describe a method running in O(n) time for counting the number of 1?s in the array.First number gives m and second gives n. PythonProgver1  Input File  
8.9 Given an array A of size 26X26. Determine whether each row and each column of the array consists of the set {A,B,C,..,Z} where each element occurs exactly once. PythonProgver1  PythonProgver2  Input File  
8.10 A certain one Way Street has m parking spaces in a row, numbered 1 through m. A man and his dozing wife drive by, and suddenly she wakes up and orders him to park immediately. He dutifully parks at the first available space, but if there are no available places he follows linear probing but does not backs up. Suppose this happens for n different cars, where the jth wife wakes up just in time to park at space aj.check whether the given sequence can be safely parked assuming that street is initially empty and no one leaves after parking. First number is n and second number is m. PythonProgver2  PythonProgver3
Input File  
9.1 A Link List of size m consists of unique records where the record consists of numbers consisting of three digits from 800 to 999. Insert n numbers from 1 to 100 at given position. Count the total number of operations in your program. Print time taken, Memory Used. Also print the size of the list and the list itself at the end of the program. First number gives m and second number gives n. PythonProgver1  PythonProgver2  PythonProgver3
CPPprogver4  Cprogver5  Cprogver6
Cprogver7  Cprogver8  Input File  
9.2 A Link List of size m consists of unique records where the record consists of numbers consisting of three digits from 800 to 999. Delete n numbers at given position. Count the total number of operations in your program. Print time taken, Memory Used. Also print the size of the list and the list itself at the end of the program. First number gives m and second number gives n. PythonProgver1  PythonProgver2  Input File  
9.3 A Link list of size m consists of records where the record consists of numbers consisting of three digits from 900 to 999. Delete n given numbers. All the occurrences of that number are to be deleted. Count the total number of operations in your program. Print time taken, Memory Used. Also print the size of the list and the list itself at the end of the program. First number gives m and second number gives n. PythonProgver1  PythonProgver2  Input File  
9.4 A Link list of size m consists of records where the record consists of numbers consisting of three digits from 900 to 999. Insert n numbers again from the same range at given positions. Count the total number of operations in your program. Print time taken, Memory Used. Also print the size of the list and the list itself at the end of the program. First number gives m and second number gives n. PythonProgver1  Input File  
9.5 A Doubly circular Link List of size m consists of unique records where the record consists of numbers consisting of three digits from 800 to 999. Insert n numbers at given positions. Count the total number of operations in your program. Print time taken, Memory Used. Also print the size of the list and the list itself at the end of the program. First number gives m and second number gives n. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
9.6 A Doubly circular Link List of size m consists of unique records where the record consists of numbers consisting of three digits from 800 to 999. Delete n numbers at given position. Count the total number of operations in your program. Print time taken, Memory Used. Also print the size of the list and the list itself at the end of the program. First number gives m and second number gives n. PythonProgver1  PythonProgver2  Input File  
9.7 A Doubly circular Link list of size m consists of records where the record consists of numbers consisting of three digits from 900 to 999. Delete n numbers given. All the occurrences of that number are to be deleted. Count the total number of operations in your program. Print time taken, Memory Used. Also print the size of the list and the list itself at the end of the program. First number gives m and second number gives n. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
9.8 A Doubly circular Link list of size m consists of records where the record consists of numbers consisting of three digits from 900 to 999. Insert n numbers again from the same range at given positions. Count the total number of operations in your program. Print time taken, Memory Used. Also print the size of the list and the list itself at the end of the program. First number gives m and second number gives n. PythonProgver1  PythonProgver2  Input File  
9.9 A stack of size m (Implemented with a linked list) consists of unique records where the record consists of numbers consisting of three digits from 800 to 999. Push n numbers from 1 to 100 at given positions. Also Delete 80 elements from the specified position from the stack. Count the total number of push and pop in your program. Print time taken, Memory Used. Also print the size of the stack and the stack itself at the end of the program. First number gives m and second number gives n. PythonProgver1  Input File  
9.10 A Queue of size m (Implemented with a linked list) consists of unique records where the record consists of numbers consisting of three digits from 800 to 999. Insert n given numbers in the queue. Each insertion should be followed by one dequeue. Count the total number of operations in your program. Print time taken, Memory Used. Print the size of the queue and the queue itself at the end of the program. First number gives m and second number gives n. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
10.1a Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement naive selection sorting. There are five such sets given in the input file. Sort five sets and print the number of swappings, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  PythonProgver3
CPPprogver4  Javaprogver5  Javaprogver6
Javaprogver7  Javaprogver8  Input File  
10.1b Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement selection sorting and improve it by taking the min and max element at each pass and swapping it with the first and last elements respectively. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
10.1c Take n numbers from x to y (some elements may be duplicate) n=1000 x=1 y=1000000 as given and implement selection sorting and improve it by taking the min and max element at each pass and swapping it with the first and last elements respectively. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
10.2a Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement naive bubble sorting. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  Input File  
10.2b Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement improved bubble sorting program which stops at the pass when there is no exchange in the previous pass and also that the next pass stops at last swap of the previous pass. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  Input File  
10.2c Take n numbers from x to y (some elements may be duplicate) n=1000 x=1 y=1000000 as given and implement improved bubble sorting algorithm which stops at the pass when there is no exchange in the previous pass and also that the next pass stops at last swap of the previous pass. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  Input File  
10.3a Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement simple na mso-fareast-font-family:"Times New Roman"'>? Insertion sorting. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.3b Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement Insertion sorting. Implement the improvement of binary search while searching within the subset of sorted elements. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.3c Take n numbers from x to y (numbers may be duplicate) n=1000 x=1 y=1000000 as given and implement Insertion sorting. Implement the improvement of binary search while searching within the subset of sorted elements. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.4a Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement simple Shell sorting. Take the sedgewick sequence to sort the list. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.4b Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement Shell sorting. Take the gap sequence as 813,288,129, 68, 33, 18, 9, 8,3,1 . Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.4c Take n numbers from x to y (numbers may be duplicate) n=1000 x=1 y=1000000 as given and implement shell sorting. Take the sedgewick sequence to sort the list. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.5a Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement simple naive Merge sort. Sort five sets and print the number of swapping, comparisons, memory used, Time taken PythonProgver1  PythonProgver2  PythonProgver3
Input File  
10.5b Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement Merge sorting. Implement the improvement of applying the insertion sort when the list size is less than 16. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
10.5c Take n numbers from x to y (numbers may be duplicate) n=1000 x=1 y=1000000 as given and implement Merge sorting. Implement the program without using any additional memory. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  Input File  
10.6a Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement counting sort. Sort five sets and print the number of swapping, comparisons, memory used, Time taken PythonProgver1  PythonProgver1  PythonProgver2  Input File  
10.6b Take n numbers from x to y (numbers may be duplicate) n=1000 x=1 y=1000000 as given and implement counting sort. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
10.6c Take n numbers from x to y (numbers may be duplicate) n=1000 x=1 y=10 as given and implement counting sort. Sort given set and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
10.7a Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement bucket sort. Use Insertion sort to individually sort the buckets. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
10.7b Take n numbers from x to y (numbers may be duplicate) n=1000 x=1 y=1000000 as given and implement simple bucket sort. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  Input File  
10.7c Take n numbers from x to y (numbers may be duplicate) n=1000 x=1 y=10 as given and implement bucket sort. Sort given set and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  Input File  
10.8a Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement Radix sort. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.8b Take n numbers from x to y (numbers may be duplicate) n=1000 x=1 y=1000000 as given and implement radix sort. Implement counting sort to sort individual columns. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.8c Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement Radix sort. Start from the Most Significant Digit first and go towards the least significant digit. Sort five sets and print the number of swapping, comparisons, memory used, Time taken PythonProgver1  Input File  
10.9a Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement Quick sort. Take first number of the list as median. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.9b Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement Quick sort. Take the median of first three numbers as the partitioning element. ort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.9c Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement Randomized Quick sort. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  Input File  
10.10a Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement max heap sort. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
10.10b Take n numbers from x to y (all unique) n=1000 x=1 y=1000000 as given and implement min heap sort. Sort five sets and print the number of swapping, comparisons, memory used, Time taken. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
11.1 Write an efficient program to solve Josephus permutation problem which is defined as: Suppose n people are arranged in a circle and we are given a positive integer m <= n. Beginning with a designated first person, we proceed around the circle removing mth person. After each person is removed, counting continues around the circle that remains. This continues until all n people have been removed. The order in which the people are removed from the circle defines (n,m) Josephus permutation. E.g. Josephus (8,3) is 3,6,2,8,8,1,4. PythonProgver1  Input File  
11.2 Write an efficient for checking that whether a given word is an anagram of another word. The word should have same length and same frequency of each letter occurring in the original word. Letters can be repeated with in a word. PythonProgver1  PythonProgver2  Input File  
11.3 An array A contains n-1 unique integers in the range [0,n-1] that is there is one number from the range [0,n] that is not in A. Design an O(n) time efficient program for finding that number. You are allowed to use only O(1) additional space besides the array A itself. First number gives n. First Number gives n. PythonProgver1  Input File  
11.4 The first n cells of the array E contains integers sorted in increasing order. The remaining cells all contain some very large integer that we may think of as infinity (name it as maxint). The array may be arbitrarily large and you don?t know n. Give an efficient program to find a position of a given integer x (x< maxint) in array in O(log n) time.First number is x. PythonProgver1   PythonProgver2  Input File  
11.5 Imagine four railroad cars positioned on the input side of the track numbered 1,2,3,4 respectively. Suppose we perform the following operations: move car 1 into stack, move 2 into stack, move 2 out, move 3 into stack, move 4 into stack, move 4 out, move 3 out, move 1 out. As a result the original order has been changed from 1234 to 2431. What permutations of the number 1,2,3,4 are possible that can be get using the above method? Input that permutation and get the output as yes or no indicating it is possible or not. First Number gives number of permutations. PythonProgver1  PythonProgver2  Input File  
11.6 Each of n boys in an array may have one of the values red, white or blue. Give an efficient program for rearranging the keys so that all red come before white and all white come before blue. It can happen that there are no keys of one or two colours. Operation permitted is swap. First Number gives the total numbers. Don?t use any extra storage. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
11.7 A popular diversion, word find, asks the player to find a word in a square table filled with single letters. A word can read horizontally, vertically or diagonally in any direction. Write a efficient program to find the word. PythonProgver1  Input File  
11.8 An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison the king?s wine. Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle. Unfortunately they don?t know which one. To make the matter worse the poison the spy used was very deadly. Just one drop diluted even to a billion will still kill someone. Even so, the poison works slowly. It takes a full month for the person to die. Design a scheme that allows the evil king to determine exactly which one of his wine bottles was poisoned in just one month?s time while expending at most O(logn) of his taste testers. First integer gives number of bottles and the sequence gives the number of taste testers who died. PythonProgver1  Input File  
11.9 In towers of Hanoi problem n disks of different sizes are piled on a peg in order by size, with the largest at the bottom. There are two empty pegs. The problem is to move all the disks to the third peg by moving only one at a time and never placing a disk on top of a smaller one. The second peg may be used for intermediate moves. The usual solution recursively moves all but the last disk from the starting peg to the spare peg, and then moves the remaining disk on the start peg to the destination peg, and then recursively moves all the others from the spare peg to the destination peg. Give the recursive procedure for the above. PythonProgver1  Input File  
11.10 Consider the problem of searching in a sorted matrix. That is, you are given an m? matrix A, where each entry is an integer. Each row of the matrix is sorted in ascending order, and each column is also sorted in ascending order. Given a value x, the problem is to decide whether x is stored somewhere in the array (i.e., whether there is some i and j such that A[i][j] = x). First number gives m and second gives n. PythonProgver1  PythonProgver2  Input File  
12.1 Implement Integer multiplication using Divide and Conquer technique. Assume that digits in the numbers are in 2n. You are given the input in binary numbers. PythonProgver1  PythonProgver2  Input File  
12.2 Implement matrix multiplication using Strassen method. PythonProgver1  Input File  
12.3 You have n coins that all are supposed to be gold coins of the same weight but you know that one coin is fake and weighs less than the others. You have a balance scale. You can put any number of coins on each side of the scale at one time and it will tell you if the two sides weigh the same, or which side is lighter. Write an efficient program to find out the fake coin in minimum number of weighing. You are given Coin number along with the weights of the coin. You have to identify the Coin with less weight. Standard weight of the coin is 4. PythonProgver1  Input File  
12.4 Given n points in 2 dimensional spaces, write an efficient program to find a pair of points with the smallest distance between them. It is known as closest pair problem. PythonProgver1  PythonProgver2  Input File  
12.5 Given n objects, their profits and weights (in this order) and knapsack weight W. Write an efficient program to implement fractional knapsack problem using Greedy Programming. First Number gives n and second number gives W. PythonProgver1  Input File  
12.6 One Processor Scheduling Problem is defined as follows. We are given a set of n jobs. Each job I has a start time ti and a deadline di. A feasible solution is a permutation of the jobs such that when the jobs are performed in that order, then every job is finished before the deadline. Write an efficient greedy program for this which processes the jobs in the order of deadline (the early deadlines processed before the late ones). PythonProgver1  PythonProgver2  PythonProgver3
Input File  
12.7 You are given starting and ending times of the intervals. Write an efficient program to implement Scheduling of intervals for a particular resource so that there is no overlap in scheduling. PythonProgver1  PythonProgver2  Input File  
12.8 Write an efficient program for Optimal merge patterns for merging n sorted lists into a single sorted lists. First number gives n followed by number in each of the list. PythonProgver1  PythonProgver2  Input File  
12.9 Write an efficient program to generate the prefix free codes using Huffman Compression for different alphabets of a given file. PythonProgver1  Input File  
12.10 Suppose we are given an n-element sequence S such that each element in S represents a different vote in an election, where each vote is given an integer representing the ID of the chosen candidate. Without making any assumptions about who is running or even how many candidates are there, design an O(nlogn) time program to see who wins the election S represents, assuming that the candidate with the most votes win. PythonProgver1  PythonProgver2  Input File  
13.1 A magic square is an arrangement of the numbers 1 through n2 in a square array so that the sum of each row and column is the same as well as the sum of the two main diagonals. Write an efficient program to determine whether such a square exists for a given number and if it exists then print the square from m to n. PythonProgver1  PythonProgver2  Input File  
13.2 Write an efficient program to print the sum of the numbers occurring in a given alphanumeric string. The numerals coming in continuation should be considered as one number PythonProgver1  PythonProgver2  Input File  
13.3 Rotate a one dimensional vector of n elements left by i positions. For instance with n=8 and i=3, the vector abcdefgh is rotated to defghabc. Write an efficient program to rotate the vector in time proportional to n using only a few dozen extra bytes of storage? PythonProgver1  Input File  
13.4 There are n closed doors along a corridor numbered from 1 to n. A person walks through the corridor and opens each door. Another person walks through the corridor and closes every alternate door. Continuing like this, ith person comes and toggles every ith door starting from position i. Determine how many doors are open and which one after nth person has walked through the corridor PythonProgver1  PythonProgver2  Input File  
13.5 Write an efficient program to find that whether a given string is a rotation of the other given string. For example rotations of car are arc,rca but not rac. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
13.6 Given a matrix, write an efficient program to find the transpose of the matrix. First two numbers give the degree of the matrix. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
13.7 Given a matrix, write an efficient program to find the Determinant of the matrix. First two numbers give the degree of the matrix. PythonProgver1  Input File  
13.8 Given a matrix, write an efficient program to find the Adjoint of the matrix. First two numbers give the degree of the matrix. PythonProgver1  Input File  
13.9 Given Two Lists, write an efficient program to find the Union of two lists where n is the number of elements in each list.Use Arrays for doing operations. First number gives n PythonProgver1  PythonProgver2  PythonProgver3
Input File  
13.10 Given Two Lists, write an efficient program to find the Intersection of two lists where n is the number of elements in each list. Use Link Lists for doing operations. PythonProgver1  PythonProgver2  Input File  
14.1 Create a binary search tree of n elements. After creating BST Find the predecessor and successor of given three numbers in the binary search tree. First number gives value of n. PythonProgver1  Input File  
14.2 As per Collatz conjecture if n is even, C(n)=n/2 else C(n)=3n+1 then for any choice of n, Ci(n)=1 for some i. For example if we start with the number 11 and iteratively compute Ci(11), we get the sequence 11,34,18,82,26,13,40,20,10,8,16,8,4,2,1 Prove the Collatz conjecture for first n numbers PythonProgver1  PythonProgver2  PythonProgver3
Input File  
14.3 1829 is the first smallest number that can be represented as sum of cubes of two numbers in two different ways. e.g. 103+93=123+13=1829 PythonProgver1  Input File  
14.4 A chocolate bar is modelled as mXn rectangles of m*n pieces. You can take a bar and break it along horizontal or vertical axis into two bars. Write an efficient program to find that how will you break a m*n bar into m*n pieces using as few breaks as possible PythonProgver1  PythonProgver2  Input File  
14.5 You are working in the finance office for ABC corporation. There are n employees and each employee received ci compensation last year and total compensation disbursement was C. This year the company needs to cut payroll expenses to C*. Company wants to put a cap # on salaries such that any employee who was paid more than # last year will be paid # this year. Employees who were paid less than # last year will be paid the same amount as of last year. e.g. if(c1,c2,c3,c4,c8) = (90,30,100,40,20) and C*=210 then 60 is suitable value for #. Write an efficient algorithm for finding #.Input file first number gives number of employees followed by C* and then followed by the salary of last year of each employee PythonProgver1  PythonProgver2  Input File  
14.6 Given a list of n numbers. Find Maximum and Nextmaximum numbers from the list. First number gives number of elements in the list. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
14.7 Given a list of n numbers. Find Maximum and minimum numbers from the list. First number gives number of elements in the list. PythonProgver1  PythonProgver2  Input File  
14.8 There is a very long stream of integers arriving as an input such that each integer is at most one thousand positions away from its correctly sorted position. Write an efficient program that outputs the integers in the correct sorted order and uses only a constant amount of storage. PythonProgver1  PythonProgver3
Input File  
14.9 Given an array A of ints representing a permutation ?. Update the array A to represent inverse of the given permutation ?-1 PythonProgver1  PythonProgver2  Input File  
14.10 Implement a function which takes a URL as input and performs the following transformations on it (1) make hostname and protocol lowercase (2)if it ends in index.html or default.html, remove the filename (3) if protocol field is missing add http:// at the beginning and (4) replace consecutive / characters by a single / in the path segment of the URL. N gives number of such sequences PythonProgver1  PythonProgver2  Input File  
15.1 Given a set S of 28 integers and a CPU that has a special instruction, SORT8 that can sort 8 integers in one cycle. Write an efficient program to identify the 3 largest integers in S using SORT8 and minimize the total number of calls to SORT8.Output file gives total number of calls to function SORT8. PythonProgver1  Input File  
15.2 P is a character String (of length m) consisting of letters and at most one asterisk (*). The * is a wild character. It can match any sequence of zero or more characters e.g. P=sun*day then in happysundaemonday there is match of if * is taken as daemon. Write an efficient Program to find a match in a text string T (of n characters). Output file will return 0 is there is no match PythonProgver1  PythonProgver2  Input File  
15.3 Write an efficient program to implement Boyer-Moore algorithm for string comparison.Output file gives the starting position in the string where the pattern is matching, if any. PythonProgver1  Input File  
15.4 Write an efficient program to implement Knuth Morris Pratt Algorithm for string comparison. Output file gives the starting position in the string where the pattern is matching, if any. PythonProgver1  PythonProgver2  Input File  
15.5 Write an efficient algorithm to implement Binary Search.First number gives n PythonProgver1  PythonProgver2  PythonProgver3
Input File  
15.6 Write an efficient program to find the square root of given n numbers without using square root function. First number in the input file gives n. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
15.7 There is a list of distinct sorted numbers stored in array A. Design an efficient algorithm for finding an index i such that A[i]=i or concluding that no such index exists. First number gives the total number of elements in the list. PythonProgver1  PythonProgver2  Input File  
15.8 Find the index of the first occurrence of an element k in the sorted array A whose length is unknown in advance, however accessing the array beyond its limits will throw an exception. Output should be -1 if element is not present in the array. PythonProgver1  PythonProgver2  Input File  
15.9 Given a dictionary of English words, return the set of all words grouped into subset of words that are anagram of each other. PythonProgver1  PythonProgver2  Input File  
15.10 You are given two sorted arrays of length m and n. Give a O(log m+ log n) time algorithm for computing the kth smallest element in the union of the two arrays. Keep in mind that the elements may be repeated. First two numbers gives the size of the arrays followed by four values of k. PythonProgver1  PythonProgver2  Input File  
16.1 Write an efficient program for random number generation between a given range of numbers. Input file has n different ranges. First number gives n. PythonProgver1  Input File  
16.2 Write an efficient algorithm for random series generation between a given range of numbers. Input file gives the count of numbers that are to be generated between this given range PythonProgver1  PythonProgver2  Input File  
16.3 A node in a linked list might point to a previous element in the list. This is bad for many reasons, not the least of which is that any loop which iterates over all the nodes in the list by accessing the next node will never terminate. So, it becomes important to detect when linked lists have loops. Here?s what one such errant linked list looks like. PythonProgver1  Input File  
16.4 Write an efficient program to Implement a stack using two queues which means implement push and pop function on two queue structures PythonProgver1  Input File  
16.5 Write an efficient program to Implement a queue using two stacks by implementing enqueue and dequeue operation on two stacks PythonProgver1  PythonProgver2  Input File  
16.6 Write an efficient program to find all the substrings that are being repeated in a given string. For example in the string hellohowareyouhel substring hel? is repeated. Don?t consider single alphabet repetitions. PythonProgver1  PythonProgver2  Input File  
16.7 Write an efficient program to implement AVL Trees with insert and Delete functions. PythonProgver1  Input File  
16.8 Write a function that takes a set of open intervals on the real line (ai,bi) for i ? {0,1,.,n-1} and determine if there exists some interval (al,bl) that is completely contained inside another interval (am,bm). If such pairs of intervals exist, then return one such pair. PythonProgver1  PythonProgver2  Input File  
16.9 You are given a number of identical balls and a building with N floors. You know that there is an integer X lessthan N such that the ball will break if it is dropped from any floor X or higher but will remain intact if dropped from a floor below X.Given K balls and N floors what is the minimum number of ball drops that are required to determine X in the worst case.Input is in the order (K,X,N). PythonProgver1  PythonProgver2  Input File  
16.10 Consider an mXn array A containing integer elements (positive, integer and zero). Assume that elements in each row of A are in strictly increasing order and the elements in each column of A are in strictly decreasing order. Write an efficient program that counts the number of zeros in A. First number gives m and second gives n PythonProgver1  PythonProgver2  Input File  
17.1 Write an efficient program to implement multiplication of n matrices using dynamic programming. First number gives n followed by the degree of the matrices. For example following input has 10 matrices where first is 3X6, second is 6X8, third is 8X4 and so on. PythonProgver1  Input File  
17.2 Write an efficient program to implement optimal binary search tree using Dynamic Programming. Input file contains the numbers to be inserted in a binary search tree. Input File  
17.3 One way to transform the source string algorithm to the target string altruistic is to use the following sequence of operations Operation Target String Source String Copy a a lgortihm Copy l al gorithm Replace g by t alt orithm Delete o alt rithm Copy r altr ithm Insert u altru ithm Insert I altrui ithm Insert s altruis ithm Twiddleit into ti altruisti hm Insert c altruistic hm Kill hm altruistic Each of the operations has certain cost associated with it. Total cost is 3.cost(copy) + cost (replace)+ cost (delete) + 3.cost (insert) + cost (twiddle) + cost (kill) . Given two strings and set of costs for each operation. Write an efficient program to find least cost sequence that converts sequence of one string to another string. use Dynamic Programming. Assume all operations have the unit cost. PythonProgver1  Input File  
17. 4. Arbitrage is the use of discrepancies in the currency exchange rates to make profit. Suppose 1 US $ buys 0.74 pounds, 1 pound buys 2 Australian dollars & 1 Australlian dollar buys 0.70 US $. Then 1 US $ buy 0.75 *2 * 0.7 = 1.05 US $ having a profit of 5 %. We are given n currencies c1,c2,,cn & nXn table R of exchange rates, such that one unit of currency Ci buys R[i,j] units of currency Cj . Give an efficient algorithm to determine the maximum profit for a sequence [i1,i2].R[i2,i3]R[ik-1,ik].R[ik,i1] Input File should consist of a table consisting of currency exchange rates. PythonProgver1  Input File  
17.5 Write an algorithm for the multi stage graph problem, where we need to calculate the overall shortest path from source to target in a multi stage graph. Use Dynamic Programming. Input File will consists of number of stages in the graph and then the number of nodes in each stage and also the distance between nodes from one stage to another stage. PythonProgver1  PythonProgver2  Input File  
17.6 A programmer wants to test whether or not n given conditions are all simultaneously true (e.g. he may want o test whether both x > 0 & y < z2, but it is not clear which condition should be tested first. Suppose that it costs Ti units of time to check condition i and that the condition will be true with probability pi, independent of the outcomes of all other conditions. In which order he should make the test. Input File will consists of number of conditions, time required to check each condition and the probability of its being will be true. PythonProgver1  PythonProgver2  Input File  
17.7 Write an efficient program that returns the parenthesization of an unparenthesized expression after maximizing the value of the expression. Expression may contain addition, subtraction and multiplication operators. For example 5-3*4+6 will yield -25= 5-(3*(4+6)) -13=5-((3*4)+6) 20= (5-3) * (4+6) -1 = (5-(3*4)) + 6 14 = ((5-3*4) + 6 So the maximum value is returned by the parenthesization at line 3. Input File will contain an arithmetic expression. PythonProgver1  Input File  
17.8 Design an efficient program that inputs a natural number C, an outputs all of the ways that a group of ascending positive numbers can be summed to give C. For example if C=6, the output should be 1+2+3 1+5 2+4 PythonProgver1  PythonProgver2  PythonProgver3
Input File  
17.9 You have 32 movable pieces that are initially placed on a board as shown. A piece can move by jumping over its immediate neighbor horizontally or vertically into an empty square opposite. The jump removes the jumped over neighbor from the board. The goal is to remove 31 pieces to finish with a single piece at the center of the board. Write a suitable efficient algorithm for this. PythonProgver1  Input File  
17.10 Optimal (Polygon) Triangulation problem : We are given a convex polygon P= < V0,V1,..,Vn-1> & a weight function w defined on triangles formed by sides & chords of P. The problem is to find a triangulation that minimizes the sum of the weights of the triangles in the triangulation. Weight function is W (?vivjvk) = |vivj|+ |vjvk| +|vkvi| Where |vi vj| is the Euclidean distance from vi to vj. Use Dynamic Programming. Input File  
18.1 A triangle in an undirected Graph G=(V,E) is a set of three pairwaise distinct vertices u,v,w ? V such that (u,v) ? E, (v,w) ? E, (u,w) ? E. Write an efficient program to check whether an undirected graph has a triangle. If G has n vertices and e edges then program should run in time O(n+e).Incidence matrix is given as input check whether this graph has a triangle or not? PythonProgver1  Input File  
18.2 Given a directed Graph G=(V,E) and a distinguished vertex s ? V. Write an efficient program to determine for each v ? V the shortest path from s to v. If G has n vertices and e edges then program should run in time O(n+e). PythonProgver1  Input File  
18.3 A forest is a graph composed of zero or more disconnected trees. Given a graph G with n nodes, write an efficient Program to determine whether G is a forest and how many disconnected components it has. PythonProgver1  Input File  
18.4 An undirected graph G=(V,E) is said to be k-colorable if all the vertices of G can be can be colored using k different colors such that no two adjacent vertices have the same color. Design an efficient program that runs in time O(n+e) to color a graph with two colors or determine that Graph is not 2-colorable. PythonProgver1  PythonProgver2  Input File  
18.5 Suppose an arithmetic expression is given as a DAG with common subexpressions removed. Devise an algorithm for evaluating such a DAG with out-degree 2 in time O(n). E.g. expression 2+3*4+5/(3*4) PythonProgver1  Input File  
18.6. An Euler path is the path in which All the edges are travelled exactly once. Find whether there is an Euler path in a given graph or not. If yes, it should give one such Euler cycle. If G has n vertices and e edges then program should run in time O(n+e). PythonProgver1  Input File  
18.7 An Hamiltonian path is the path in which All the vertices are travelled exactly once. Find whether there is an Hamiltonian path in a given graph or not. PythonProgver1  PythonProgver2  Input File  
18.8 Given a graph G=(V,E). Implement BFS for a graph and output the sequence in which the graph will be searched. PythonProgver1  PythonProgver2  Input File  
18.9 Given a graph G=(V,E). Implement Kruskal method for MST. Output should be a set of edges making a MST of G. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
18.10 Given a graph G=(V,E). Implement DFS for a graph and output the sequence in which the graph will be searched. PythonProgver1  Input File  
19.1 Given a graph G=(V,E). Implement Prim method for MST. Output should be a set of edges making a MST of G. PythonProgver1  Input File  
19.2 Write an algorithm for 6-queen problem for a 6X6 chessboard. A queen has the property that it can attack in horizontal, diagonal and vertical positions. The solution should contain the queens in the position that they are in non-attacking position PythonProgver1  Input File  
19.3 A Knight can make up to eight moves as shown in the figure. Starting at an arbitrary position (Given as input) in the nXn board, A knights tour is a sequence of n2-1 moves such that every square of the board is visited once. Write a backtracking program that either produces a knights tour or determines that no such tour exists. PythonProgver1  Input File  
19.4 Let G=(V,E) be a directed Graph (not necessarily acyclic) . Design an efficient program to label the vertices of the graph with distinct labels from 1 to |V| such that the label of each vertex v is greater than the label of at least one of vs predecessors ( if v a has any) , or to determine that no such labelling is possible (w is a predecessor of v iff (w,v) ? E. If G has n vertices and e edges then program should run in time O(n+e). PythonProgver1  Input File  
19.5 Let G=(V,E) be a undirected Graph. Write an efficient program to find all the vertices with degree more than n. Also print the total degree of the graph. PythonProgver1  PythonProgver2  Input File  
19.6 Let G=(V,E) be a directed Graph. Check whether the given sequence of vertices and edges makes a simple path. PythonProgver1  PythonProgver2  Input File  
19.7 Let G=(V,E) be a directed Graph. Check whether the given sequence of vertices and edges makes a simple Cycle. PythonProgver1  PythonProgver2  Input File  
19.8 Let G=(V,E) be a directed Graph. Check whether the given Graph is a tree or not. PythonProgver1  PythonProgver2  Input File  
19.9 You are helping some security analysts monitor a collection of networked computers, tracking the spread of an online virus. There are n computers in the system, labelled C1,C2,,Cn and as input you are given a collection of trace data indicating the times at which pairs of computers communicated. Thus the data is a sequence of ordered triples( Ci,Cj,tk); such a triple indicates that Ci and cj exchanged bits at time tk. There are m triples total. we will assume that the triples are presented to you in sorted order of time. For purposes of simplicity, we will assume that each pair of computers communicates at most once during the interval you are observing. The security analysts you are working with would like to be able to answer questions of the following form: if the virus was inserted into computer ca at time x, could it possible have infected computer cb by time y? The mechanics of infection are simple: if an infected computer ci communicates with an uninfected computerCj at time tk ( In other words, if one of the triples (Ci,Cj,tk) or (Cj,Ci,tk) appears in the trace data), then computer Cj becomes infected as well, starting at time tk. Infection can thus spread from one machine to another across a sequence of communications, provided that no step in this sequence involves a move backward in time. Thus, for example, if ci is infected by time tk, and the trace data contains triples(Ci,Cj,tk) and (Cj,Cq,tr) where tk? tr then cq will become infected via cj. (Note that it is okay for tk to be equal to tr; this would mean that cj had open connections to both ci and cq at the same time, and so a virus could move from ci to cq.) For example, suppose n=4, the trace data consists of the triples (C1,C2,4), (C2,C4,8) (C3,C4,8) (C1,C4,12), and the virus was inserted into computer c1 at time 2. Then C3 would be infected at time 8 by a sequence of three steps: first C2 becomes infected at time 4, then c4 gets the virus from C2 at time 8, and then C4 gets the virus from C4 at time 8. On the other hand, if the trace data were (C2,C3,8), (C1,C4,12), (C1,C2,14), and again the virus was inserted into computer C1 at time 2, then C3 would not become infected during the period of observation: although C2 becomes infected at time 14, we see that C3 only communicates with C2 before C2 was infected. There is no sequence of communications moving forward in time by which the virus could get from c1 to c3 in this second example. Design an algorithm that answers questions of this type: given a collection of trace data, the algorithm should decide whether a virus introduced at computer ca at time x could have infected computer cb by time y. The algorithm should run in time O(m+n). PythonProgver1  Input File  
19.10 The race for the election of Democratville's mayor is heating up and everyone in Democratville is competing for it. Each candidate has a few preferences (people who the person would be willing to accept as a mayor). Of course, the set of preferences for a person includes him/her self all the time. What we are looking for is a \perfect" mayor who is in the set of preferences of every person and who does not prefer anyone but him/her self (wouldn't that make a good mayor?). In fact, all we want to know whether such a person exists or not. Otherwise, we're willing to live in anarchy. Dene a directed graph with the set of candidates as the vertices and a directed edge from vertex a to vertex b if and only if b is in the set of preferences of a. Suppose that the number of people (also the number of candidates) is n. Give an algorithm which executes in O(n) time and determines if such a perfect mayor exists or not. Assume that you are given the graph described above in the form of an n n adjacency matrix PythonProgver1  Input File  
20.1 A small business say, a photocopying service with a single large machine faces the following scheduling problem. Each morning, they get a set of jobs from customers. They want to do the jobs on their single machine in an order that keeps their customers happiest. Customer is job will take ti time to complete. Given a schedule (i.e., an ordering of the jobs, let Ci denote the finishing time of job i. For example, if job i is the first to be done, we would have Ci = ti ; and if job j is done right after job i, we would have Cj = Ci + tj . Each customer i also has a given weight wi that represents his or her importance to the business. The happiness of customer i is expected to be dependent on the finishing time of is job. So the company decides that they want to order the jobs to minimize the weighted sum of the completion times, ?=niwiCi1. Design an efficient algorithm to solve this problem. That is, you are given a set of n jobs with a processing time ti and a weight wi for each job. You want to order the jobs so as to minimize the weighted sum of the completion times, ?=niwiCi1. Example. Suppose there are two jobs: the first takes time t1 = 1 and has weight w1 = 10, while the second job takes time t2 = 3 and has weight w2 = 2. Then doing job 1 first would yield a weighted completion time of 10*1 + 2*4 = 18, while doing the second job first would yield the larger weighted completion time of 10*4 + 2*3 = 46. Note: to prove that your greedy strategy yields the optimal solution, you have to prove that the problem has the greedy-choice property. PythonProgver1  Input File  
20.2 Post order traversal of a binary tree when implemented on a mathematical expression is also called Reverse Polish Notation (RPN) which is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 ? 4 + 5" would be written "3 4 ? 5 +" first subtract 4 from 3, then add 5 to that. Transform the algebraic expression with brackets into RPN form. You can assume that for the test cases below only single letters will be used, brackets [] will not be used and each expression has only one RPN form (no expressions like a*b*c) The first line contains t, the number of test cases. PythonProgver1  PythonProgver2  Input File  
20.3 A permutation of the integers 1 to n is an ordering of these integers. So the natural way to represent a permutation is to list the integers in this order. With n = 5, a permutation might look like 2, 3, 4, 5, 1. However, there is another possibility of representing a permutation: You create a list of numbers where the i-th number is the position of the integer i in the permutation. Let us call this second possibility aninverse permutation. The inverse permutation for the sequence above is 5, 1, 2, 3, 4. An involution is a permutation which is exactly same as its inverse permutation. The permutation 1, 4, 3, 2 for example is an involution, because its inverse permutation is the same. Given a permutation we have to find its inverse and then detect whether it is an involution or not PythonProgver1  Input File  
20.4 There are K nuclear reactor chambers labelled from 0 to K-1. Particles are bombarded onto chamber 0. The particles keep collecting in the chamber 0. However if at any time, there are more than N particles in a chamber, a reaction will cause 1 particle to move to the immediate next chamber(if current chamber is 0, then to chamber number 1), and all the particles in the current chamber will be be destroyed and same continues till no chamber has number of particles greater than N. Given K,N and the total number of particles bombarded (A), find the final distribution of particles in the K chambers. Particles are bombarded one at a time. After one particle is bombarded, the set of reactions, as described, take place. After all reactions are over, the next particle is bombarded. If a particle is going out from the last chamber, it has nowhere to go and is lost. PythonProgver1  PythonProgver2  Input File  
20.5 We consider permutations of the numbers 1,..., N for some N. By permutation we mean a rearrangment of the number 1,...,N. For example 2 4 5 1 7 6 3 8 is a permutation of 1,2,...,8. Of course, 1 2 3 4 5 6 7 8 is also a permutation of 1,2,...,8. We can "walk around" a permutation in a interesting way and here is how it is done for the permutation above: Start at position 1. At position 1 we have 2 and so we go to position 2. Here we find 4 and so we go to position 4. Here we find 1, which is a position that we have already visited. This completes the first part of our walk and we denote this walk by (1 2 4 1). Such a walk is called a cycle. An interesting property of such walks, that you may take for granted, is that the position we revisit will always be the one we started from! We continue our walk by jumping to first unvisited position, in this case position 3 and continue in the same manner. This time we find 5 at position 3 and so we go to position 5 and find 7 and we go to position 7 and find 3 and thus we get the cycle (3 5 7 3). Next we start at position 6 and get (6 6) and finally we start at position 8 and get the cycle (8 8). We have exhausted all the positions. Our walk through this permutation consists of 4 cycles. One can carry out this walk through any permutation and obtain a set of cycles as the result. Your task is to print out the cycles that result from walking through a given permutation. PythonProgver1  Input File  
20.6 Three students are asked to make a list of numbers from a given range. Write an efficient program which makes a final list from these three lists that will contain only those numbers that appear in at least two of the three lists. Those numbers that appear in only one list will not appear in the final list. PythonProgver1  PythonProgver2  Input File  
20.7 Find the prime numbers which are palindromes also. E.g. 101 PythonProgver1  Input File  
20.8 Chef wrote some text on a piece of paper and now he wants to know how many holes are in the text. What is a hole? If you think of the paper as the plane and a letter as a curve on the plane, then each letter divides the plane into regions. For example letters "A", "D", "O", "P", "R" divide the plane into two regions so we say these letters each have one hole. Similarly, letter "B" has two holes and letters such as "C", "E", "F", "K" have no holes. We say that the number of holes in the text is equal to the total number of holes in the letters of the text. Help Chef to determine how many holes are in the text. PythonProgver1  PythonProgver2  PythonProgver3
Input File  
20.9 After a long and successful day of preparing food for the banquet, it is time to clean up. There is a list of n jobs to do before the kitchen can be closed for the night. These jobs are indexed from 1 to n. Most of the cooks have already left and only the Chef and his assistant are left to clean up. Thankfully, some of the cooks took care of some of the jobs before they left so only a subset of the n jobs remain. The Chef and his assistant divide up the remaining jobs in the following manner. The Chef takes the unfinished job with least index, the assistant takes the unfinished job with the second least index, the Chef takes the unfinished job with the third least index, etc. That is, if the unfinished jobs were listed in increasing order of their index then the Chef would take every other one starting with the first job in the list and the assistant would take every other one starting with the second job on in the list. The cooks logged which jobs they finished before they left. Unfortunately, these jobs were not recorded in any particular order. Given an unsorted list of finished jobs, you are to determine which jobs the Chef must complete and which jobs his assistant must complete before closing the kitchen for the evening. PythonProgver1  PythonProgver2  Input File  
20.10 The chef is preparing a birthday cake for one of his guests, and his decided to write the age of the guest in candles on the cake. There are 10 types of candles, one for each of the digits '0' through '9'. The chef has forgotten the age of the guest, however, so doesn't know whether he has enough candles of the right types. For example, if the guest were 101 years old, the chef would need two '1' candles and one '0' candle. Given the candles the chef has, your task is to determine the smallest positive integer that cannot be represented with those candles. Input: Input will begin with an integer T?100, the number of test cases. Each test case consists of a single line with exactly 10 integers, each between 0 and 8, inclusive. The first integer of each test case represents the number of '0' candles the chef has, the second integer represents the number of '1' candles the chef has, and so on. Output: For each test case, output on a single line the smallest positive integer that cannot be expressed with the given candles. Sample input: 3 2 1 1 4 0 6 3 2 2 2 0 1 1 1 1 1 1 1 1 1 2 2 1 2 1 1 3 1 1 1 Sample output: 4 10 PythonProgver1  Input File  
21.1 Implement the basic operation of Skip List Data Structure? PythonProgver1  Input File  
21.2 Implement the basic operation of B-Tree Data Structure?
21.3 Implement the Insertion operation of RB-Tree Data Structure? PythonProgver1  Input File  
21.4 Implement the basic operation of Fibbonacci Heap Data Structure? PythonProgver1  Input File  
21.5 Implement the basic operation of B+ Tree Data Structure? PythonProgver1  PythonProgver1  Input File  
21.6 Implement the basic operation of Binomial Heap Data Structure? PythonProgver1  Input File  
21.7 Implement the Deletion operation of RB-Tree Data Structure? PythonProgver1  Input File  
21.8 Implement the basic operation of Disjoint Set Data Structure? PythonProgver1  PythonProgver2  PythonProgver3
Input File  
21.9 Implement the basic operation of Splay Tree Data Structure? PythonProgver1  Input File  
21.10 Implement the basic operation of Trie Data Structure? PythonProgver1  Input File  

For any feedback or suggestions please write to dgarg@acm.org, deepakgarg@ieee.org,deep108@yahoo.com