CodeGuru Forums - Algorithms & Data Structures

Problem output of function

mathmari — Thu, 23 May 2013 22:15:21 GMT

void find_winner(int array[]){
int i,questions[3],j=0;
for (i=0; i<3; i++){
questions[i]=1;
}
for (i=0; i<3; i++){
while (array[j+1]!=1){
questions[i]++;
j++;
}
}
for (i=0; i<3; i++){
printf("%d",questions[i]);
}
}

This function should find the winner of a game,that is the one that answered at the most questions.For example,if there is an array
[1]
[2]
[3]
[1]
[2]
[1]
[2]
[3]
the first player answered three questions,the second one answered 2 questions and the third one three.so,there are two winners,the player one and the player three.
My problem is that it just prints the number of questions that the first two players answered.What have I done wrong?
I hope someone can help me!!!

Algorithm for finding subset of permutations with maximum value

mayeri — Thu, 23 May 2013 09:48:19 GMT

Hello,
Can anyone help with suggestions for implementation of an efficient algorithm for the following issue:
Given a list of permutations with a score for each permutation, we need to find a subset of permutations with the highest summed score, given the condition that any one of permutation in the subset will not intersect or be contained with another permutation in the subset.
For example, given the following list of permutations, marked as |Index: start, end, score|, permutation A cannot be in the same subset with permutation B, since they intersect with each other. Permutation C cannot be in the same subset with permutation F, since permutation F is contained within permutation C.

A: 43 70 27
B: 45 74 26
C: 3 28 24
D: 65 99 45
E: 20 39 26
F: 10 18 20
G: 78 97 23

I guess the challenge is to implelent this in O(NlogN) rather than the na�ve implemention of O(N2)
Thanks in advance!

Tom.

Help with understanding an Algorithm

Hallow — Wed, 22 May 2013 14:20:41 GMT

I'm trying to code the Algorithm discussed in the paper - (see here http://tinyurl.com/nzdf6rq ). The problem is I am not sure if I understand the problem enough to be able to correctly write the code.

This is what I understand from the problem so far. I am hoping someone can help fill in blanks.

To determine a trending activity:

- Take a recent activity (observation s)
- Compare s to the example patterns r (from past topics)
- For each example, take a vote V(r,s) to determine if a topic is trending or not.

Assuming my understanding is correct, what other information do we require in the example beside the name of the topic that we are tracking?

what variables are we to use to compare s with r?

What is the purpose of scaling parameter y (greek symbol)?

It would be a real help if someone can break the algorithm down into a series of steps that is easy to follow.

Files,question about data

mathmari — Tue, 21 May 2013 18:17:25 GMT

Hi!!!!I have a question...How can I use the data from a file????For example at the following code I want to write a function that finds the max of the numbers i*n,that exist in the file "d.dat".How can I do this????Thank you!!!
#include
int main()
{
FILE *fp;
int i,n;
fp = fopen("d.dat","w");
if (fp==NULL) {
exit(0);
}
for (i=0; i<=10; i++){
printf("Give number:");
scanf("%d",&n);
fprintf(fp,"%d,%d\n",n,i*n);
}
fclose(fp);
return 0;
}

depth-first search of a graph

mathmari — Sat, 18 May 2013 23:07:16 GMT

Hi!!! I need some help...
The exercise is:
You have to implement a data structure to represent graphs,directed or undirected,that tries to avoid the wasted space in the representation of a graph with adjacency matrix and the difficulty of searching the edges with adjacency list representation.
We consider that the vertices are numbered from 1 to nverts and the exit degree of each vertex is at most MAXDEG. If deg[i] is the exit degree of the vertex i then the neighbors of the vertex i can be saved at the matrix edge[i][j], 1<=j<=deg[i].
Write a program that reads the datas from a file: if the graph is directed or undirected(1 or 0), the number of vertices (nverts),the number of edges (nedges) and the first and the last vertex of each edge.
Write the function dfs that, with argument the data structure that you implemented before for the representation of a graph, prints the edges by the depth-first search of a graph.

What I've done so far is: I wrote a program that reads these information from a file, calculates the exit degree of each vertex and creates the matrix edge[i][j].

What data structure do I have to implement???

Disjoint pairs problem

lucav — Wed, 01 May 2013 14:49:06 GMT

Hi to all,
excuse me in advance if I have done something wrong in posting this thread (I'm new :)).
My problem is the following:
I have a set of pairs identified by two end point: u and, that respectively represent two process connected (u sends and v receives), and each process can hold one connection at a time, so I have to divide the computation in communication rounds so that in each round communicate as many process as possibile. This example may explain better the idea:
I have
1-2
1-3
1-4
2-1
2-3
3-4
3-5
4-6
4-2
...
If I choose 1-2 in a communication round I can't choose in the same communication round 1-3, 1-4, 2-1, 2-3, 4-2 because these pairs involve process 1 or 2.
I tried to solve the problem with a greedy algorithm that for each pair choose a round that doesn't intersect with it and if there are no feasible rounds it creates a new one.
I find lots of problems in literature regarding path coloring, arc coloring and interval scheduling, but I'm not sure if I'm dealing with a difficoult problem, I mean NP-hard, or with a polynomial one, so I can't prove if my solution is optimal. Can you help me? Do you think my problem is reconducible to path coloring? If so, are there some approximation algorithms that give less than O(n^2)?
Thanks in advance to all
luca v.

initialization of a pointer

mathmari — Sat, 27 Apr 2013 22:10:29 GMT

I have to write a function,which gets a string,deletes its spaces and returns the result..That's what I did:

char *removespaces(char *s1)
{
char *s2=s1;
int i,j=0;
for (i = 0; i if (s1[i]!=' ') {
s2[j]=s1[i];
}else {
j--;
}
j++;
}
s2[j]=0;
return s2;
}

Is this right???If yes,could you explain me why I have to initialize the pointer *s2 with the first element of the array s1...???If I don't initialize the pointer,or initialize it with something else,I get a segmentation fault...