Problems Day 1:
Session 1
Problem 1:
You are given an m-bit message. Assume this is at locations 0 to m-1 in an array M. Write a program to compute the Hamming code corresponding to this message in an array S.
Problem 2:
You are given an n×n system of linear equations (n equations in n variables). Write a program to solve this system using Gaussian elimination (the method discussed in class).
Session 2
Problem 1:
Propose an O(n) time algorithm to find the largest element in every contiguous subarray of size k.
For example:
If the array is: {12, 1, 78, 90, 57, 89, 56} and k = 3.
The answer will be: 78, 90, 90, 90, 89
In this case, we find the maximum of elements with indices: (0,1,2), (1,2,3), (2,3,4), (3,4,5) and so on ...
The important point to note is that the time complexity should be independent of k. You can use auxiliary data structures such as stacks and queues.
Problem 2:
Assume that I have an unsorted array with n elements. Each element is an integer between 0 and (n-1). Propose an O(n) time algorithm for sorting this array.
Hi
ReplyDeleteI hv doubt in hamming code qn. Mr Naveen Garg told us to store the message bits from index 1 onwards as 4 bit binary representation of 0 is 0000. But qn says store message bits from 0 to m-1 positions in array.
We r storing the data in an array... hence index is considered 0
DeleteDeepa that's true but Mr Naveen said 0th position will not store neither data bit nor parity bit. every bit is based on positional value system
ReplyDelete