/sci/ - Science & Math » Thread #12473262

272KiB, 935x913, e4630dd2981c51383ce28988e4f268c3.png

View Same Google iqdb SauceNAO

Algorithm problem solving

Anonymous Wed 16 Dec 19:34:21 2020 No.12473262 View Reply Original Report

Quoted By:

Can anyone help me answer these to prepare for my final? Not sure how to write the pseudocode for these problems

Anonymous

Anonymous Wed 16 Dec 2020 20:09:48 No.12473437 Report

Quoted By: >>12473505 >>12473522

H = V
check = true
while(check){
check = false
for v in H{
if number of e = (v,w) in E < k{
check = true
remove all edges e=(v,w) from E
remove v from H
}
}
}
return H

My guess. Can't be arsed to check if it's correct or the runtime fits.
Generally it works like the hint: You check for each vertex if it has at least k neighbors. If not, remove the vertex and remove all edges containing the vertex.
Since you can possibly remove a vertex and it's edges which consequently makes another vertex drop to below k you have to go over the V once without any failures. Hence the check thing.

Also I don't know if this is appropriate for whatever or where ever you are studying but this is how I learned it at a european university.

Anonymous

Anonymous Wed 16 Dec 2020 20:15:22 No.12473455 Report

Quoted By: >>12473509

Thanks, I have a question, though. Would your input be k and H? I don't see how we can do this with just k as input or did you assume that H is globally available in the code?

Anonymous

Anonymous Wed 16 Dec 2020 20:25:03 No.12473505 Report

Quoted By: >>12473532

>>12473437
Also, what does w represent? I figure that lowercase v is each vertex and lowercase e is each edge?

Anonymous

Anonymous Wed 16 Dec 2020 20:26:30 No.12473509 Report

Quoted By: >>12473516

>>12473455
Forgot that:
Input should be (G = (V,E), k)
That doesn't really matter tho, unless you are asked about space complexity.

Also I checked the runtime. My program would be around $O(|V^2| +|E|)$

I think the better solution is to check each vertex for it's neighbor count.. Then every time you find one <k you remove it and check each neighbor if it's count is still above k.
Like that you at most have to check $O(|V| +|E|)$ vertexes.

Anonymous

Anonymous Wed 16 Dec 2020 20:28:00 No.12473516 Report

Quoted By:

>>12473509
Okay, thanks so much man!

Anonymous

Anonymous Wed 16 Dec 2020 20:31:35 No.12473522 Report

Quoted By: >>12473538

>>12473437
this is obviously not in $\theta(\mid\! N\! \mid + \mid\! E\! \mid)$ since it goes over all remaining vertices until the end condition is reached. Since the only hard limit to how often you repeat that till you end is the number of nodes in the graph, it is quite obvious that this algorithm is more likely in something like $\theta(\mid\! S^2\! \mid )$ .

The real solution would, after it removed a node, instantly check if it has to remove one of the neighbouring nodes now, I think

Anonymous

Anonymous Wed 16 Dec 2020 20:33:48 No.12473532 Report

Quoted By: >>12473575

>>12473505
Yes.
for v vertex in H
check edge e=(v,w) in E (where w also means vertex)
Edges e can be represented as tuple of vertices. Have a bunch of edges e=(v,w) with the vertex v you are currently in the loop with. w is interchangeable with every vertex that is neighbor of w.
Mind that since you have an undirected the order of the tuple doesn't matter. (v,w)=(w,v). This of course changes in a directed graph
As is listed in the adjacency list

Anonymous

Anonymous Wed 16 Dec 2020 20:35:00 No.12473538 Report

Quoted By:

>>12473522
Ah I take that back, I think those subclasses for which your algorithm takes quadratic time also have some kind of quadratic number of edges, in relation to the nodes so its fine.

Anonymous

Anonymous Wed 16 Dec 2020 20:45:20 No.12473575 Report

Quoted By: >>12473617

>>12473532
>w is interchangeable with every vertex that is neighbor of v
i mean to say

Anonymous

Anonymous Wed 16 Dec 2020 20:56:58 No.12473617 Report

Quoted By:

>>12473575
Perfect thanks!

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches