Most Popular

more tags
1500 questions
11
votes
3 answers

Graph find all vertices that are part of a cycle

I was wondering how I can find all the vertices in a graph that are part of a cycle. To determine this for one vertex, I could just start a DFS from that vertex, but this seems unefficient to me when I want to know for all vertices. Thanks for your…
Tschösi
  • 213
  • 1
  • 2
  • 6
11
votes
0 answers

Advantages of algorithm W over algorithm J for type inference in Hindley-Milner type system

According to A modern eye on ML type inference Furthermore, for some unknown reason, W appears to have become more popular than J, even though the latter is viewed—with reason!—by Milner as a simplification of the former. Jones’ presentation of type…
Alexey Romanov
  • 3,227
  • 20
  • 23
11
votes
0 answers

Is Agda sound as a proof system?

I was browsing Agda's stdlib source code, since I was trying to get into it seriously and therefore wanted to know more. I was amazed at that Agda is way more developed than I thought and it's significantly much closer to Haskell than Coq. However,…
Jason Hu
  • 652
  • 3
  • 14
11
votes
2 answers

Theoretical minimum number of registers for a modern computer?

I took a course on compilers in my undergraduate studies in which we wrote a compiler that compiles source programs in a toy Java-like language to a toy assembly language (for which we had an interpreter). In the project we made some assumptions…
BlueBomber
  • 1,337
  • 12
  • 15
11
votes
2 answers

Why do we need so many sorting algorithms?

We have some best sorting methods like quick sort, merge sort etc., then why we need other sorting methods which perform poor?
user82923
11
votes
1 answer

Intuition behind the Master Theorem

The Master Theorem provides a method of solving recurrence relations for divide-and-conquer algorithms. It was first presented to me in my intro algorithms class as the following: For a recurrence of the form $T(n) = aT(\frac{n}{b})+f(n)$ with…
roctothorpe
  • 1,178
  • 8
  • 20
11
votes
3 answers

Polymorphism and Inductive datatypes

I'm curious. I've been working on this datatype in OCaml : type 'a exptree = | Epsilon | Delta of 'a exptree * 'a exptree | Omicron of 'a | Iota of 'a exptree exptree Which can be manipulated using explicitly typed recursive functions (a feature…
Stéphane Gimenez
  • 1,490
  • 1
  • 14
  • 29
11
votes
3 answers

Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?

Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?
Death_by_Ch0colate
  • 369
  • 1
  • 2
  • 8
11
votes
2 answers

Is there any standard for comparing runtimes experimentally?

My situation I am writing a paper presenting a software module I developed and I want to compare its runtime to other modules for the same task. I am aware of the drawbacks of runtime experiments , but please assume as given that there is no way…
Wrzlprmft
  • 245
  • 1
  • 9
11
votes
2 answers

Find largest and second largest elements of the array

So here is a HW problem I have been working. On I was wondering if anybody could give me a hint of what I am doing wrong. I don't want to be given the answer just hints and advice on how to solve it. I am given this simple algorithm that finds the…
SPD
  • 211
  • 1
  • 2
  • 4
11
votes
2 answers

Name of this rearranging/sorting problem?

You are given an array of length $n$. Each element of the array belongs to one of $K$ classes. You are supposed to rearrange the array using minimum number of swap operations so that all elements from the same class are always grouped together, that…
Marko Bukal
  • 141
  • 4
11
votes
1 answer

Proving that directed graph diagnosis is NP-hard

I have a homework assignment that I've been bashing my head against for some time, and I'd appreciate any hints. It is about choosing a known problem, the NP-completeness of which is proven, and constructing a reduction from that problem to the…
user8879
  • 113
  • 5
11
votes
2 answers

What is instruction throughput and instruction latency?

I was reading an article on an alternative method of modulo reduction and i couldn't understand the following excerpt (Those in bold) : "A single 32-bit division on a recent x64 processor has a t hroughput of one instruction every six cycles with a…
Karim Manaouil
  • 330
  • 1
  • 2
  • 12
11
votes
1 answer

How does Stack Inspection work?

This is precursor to my other, more advanced question about Stack Inspection. Stack Inspection is a security mechanism introduced in the JVM to deal with running code originating from locations having different levels of trust. This is question aims…
Dave Clarke
  • 20,375
  • 4
  • 72
  • 114
11
votes
1 answer

Is there a dual concept to "Turing Complete" in logic?

Two computing models can be shown to be co complete if each can encode a universal simulator for the other. Two logics can be shown to be co complete if an encoding of the rules of inferences (and maybe axioms if present) of each be shown to be…
DanielV
  • 526
  • 3
  • 12
1 2 3
…
99
100