Interesting problems and Algorithms

hi all
i am starting this new thread for all of us to post some interesting problems for the computer techies. Do post ur problems here.

1. Giiven a graph( any representation), tell whether it is a tree??

2. Given a graph(any representation),count no of cycles in the graph.


3.Given a tree find the depth of the tree. (can u make it more efficient if u know the no. of leaves in that tree.


There are many to come....

byeeeeeeeeeeeeeee.....

4. Given a graph(any representation) find the shortest distance between node A and B

hi.
I really don't understant, what's the problem...

Simple deep search algorithm, that recursively check every part of tree. If will get to same part again -> loop.

thats the solution for 1) & 2).

3) can be find out by simple deep search algorithm that remember max. depth.

4) is a part of problem "Shortest path from every node to every node" -> dijkstr. algorithm.

anything else?

hi

The first one is quite easy. as we will calculate indegree and outdegrees of each node. Then outdegree of each node should be equal or less than 2 and indegree of an 1 node should be 0 with all other nodes having indegree exactly1.

The fourth posted problem have a standered greedy based algorithm and can be found in any standard book on algorithms.

The second one can be done by backtracking of dynamic programming but i was getting some problem when i was trying. can u just write a psudo code or chalk out algo for this.

The third one is just a ptimization ques. ?????????

These are just to keep ourselfs in touch with algorithms..

bye....

5)Given 3 integers a,b,c, without making use of comparision operator can u find which is greatest of the three. The operation such as +,-,/,*,sqr,abs are available.

6) Given a bit pattern(0's and 1's). count no of 1's in the pattern without going to each bit.

7) Given an array of integers of odd size say 2N+1, N>0. This array has N elements present twice and 1 element present once. How fast (complexity) u can find the distinct number.

5)

6) If there is some bit you didn't visit, then your answer didn't depend on the value of that bit, so if we change that bit, the number of 1's is different, but your algorithm must give the same answer as before (since it didn't depend on the value of that bit), so either the previous answer or this answer was wrong. How can you avoid visiting every bit if the answer depends on the value of every bit? Did I misinterpret the problem?

7) I can see an N*log(M) complexity algorithm (where M is the largest number in the set): go through the array, maintaining a symbol table of integers. When visiting an element x of the array, if x is in the symbol table already, remove it; if not, insert it. After reaching the end of the array, the odd one out is the sole integer left in the symbol table. There are various tree-based symbol table implementations that have guaranteed O(log(M)) time insertion/deletion.

hi lux(if i am not wrong)
nice to see some post after such a long time.

abt Q5. sorry i forgot to memtion, u can even use logial and boolean operation..

Q6 ya i think u did misinteprit it. by not going to each bit i meant that u cant have a for loop which just shifts the bits and counts the no the 1's by cheking the sign bit everytime.
No of 1s in the number is many to 1 function.
Bits(8)=Bits(1000)=1 and Bits(2)= Bits(0010)=1

Q7 No there exits a solution O(n) time n that too u just need single scan of array. I will give u hint : the array is of integer type.


ok bye...
if u have such ques plz post..
we will be happy to see some gud ques.

8)can u find in one step whether a given integer is a power of 2????

bye...

Here's a slightly more elegant answer to 7:



On the surface, that's O(n). However, to nitpick, the use of the xor operation will give you a factor of log(M) (M is the maximum integer) somewhere, either in hardware complexity or time complexity. That would only matter if we were to consider integers of arbitrary size. But the previous algorithm and this one really have the same big-O complexity; it's just that we usually deal with integers in a bounded range.

hi,
i been reading in books and i dont understand wots the difference between floyd's algorithm / floyd-warshall algorithm / warshall algorithm?? I have to answer a question using the warshall algorithm where my motes say this algortihm is a slight modification of floyd's where the original adjacency matrix is set up having boolean values and not numerical values which i dont get??

i'm given a adjacecny matrix for a graph where {a,b,c,d) are nodes:

a b c d
a 0 2 x x
b x 0 x 8
c 2 x 0 x
d x x 8 0

( where x = infinity)
and i need to generate the input matrix using warshall givin the intermideate n final matrices. im kinda stuck can ne one help me plz