# All Questions

28,408 questions
5 views

### What is the relationship between “model of computation” and “algorithm”?

Traditionally, the usual definition you find for model of computation is "an abstract description of how a computation may be carried out". To me, this seems really close to the informal notion of ...
4 views

### How can I find an object with a certain property value in a recursive branched nest of objects?

In my example, all objects represent layouts with arrays of components where components can have arrays of components themselves. A component does not always have an array of components and it also ...
3 views

### How to compute the sample update error?

In the book Reinforcement Learning An Introduction，Chapter 8.5，there is an example that compares the efficiency of expected and sample updates: According to the author, "In this case, sample updates ...
4 views

### Approximation factor shorthand clarification

I'm starting to dabble in the world of approximation algorithms and had a question about the convention many papers will use when talking about the approximation factor. I know that an approximation ...
16 views

### Branch Prediction question

My question relates to a video I watched on YouTube. The pipeline is a 5-stage pipeline which include fetch, decode, ALU, Mem (data), and Write. It mentions that nothing is fetched until we're sure ...
12 views

### Determining a value in an algorithm on its first run

I was given the following algorithm as a solution to one of my problems. However, I am baffled at understanding how c' is ever initialized. The first if statement can never be reached, as c' is never ...
45 views

### Determine wether a set of sets contains a partition of a given set

Consider the following problem : Given a set of sets of integers, $\Sigma = \{S_i, i \in I\}$, and a set G, determine wether $\Sigma$ contains a partition of G, i.e. a set $J \subseteq I$ such that ...
20 views

### Get / Head request methods HTTP protocol

can the information retrieved via HEAD also be retrieved via GET ? That's a basic question than I need to understand, I know ...
21 views

### What is the computational complexity of intuitionistic propositional logic?

Consider the decision problem: given formulas of propositional logic $\phi_1, \ldots, \phi_n, \psi$, determine whether $\phi_1, \ldots, \phi_n \vdash \psi$ intuitionistically. This problem is well-...
28 views

### Test if code contains sequence in Array (IM DESPERATE PLEEEEAAASE!!) [on hold]

Directions: Write a code that determines whether A, B, and C appear consecutively and in order exactly once in the numbers array and return the result. Example: Suppose A is 1, B is 2, C is 6 Sample ...
7 views

### How do you prove that a kernel trick can be used on a particular problem?

In the following SVM classifier optimisation problem, is there a way to show that a kernel trick can be used? I have tried showing that this fits the Representer theorem, however, I'm not sure how to ...
10 views

### Reducing weighted linear threshold gate to unweighted one

Reading "On the power of threshold circuits with small weights" by Siu and Bruck I have faced several problems understanding how unweighted linear threshold element can be built efficiently from the ...
40 views

### Minimum Distance Spanning Tree Dijkstra

I would like to construct a Minimum Distance Spanning Tree (Dijkstra) for the graph below: MDST: {(a,c), (c,h), (c,f), (a,d), (h,g), (a,b), (d,e), (h,j), (h,i), (j,k), (e,m), (i,l)} Is my ...
28 views

### Why category theory has that name?

I am studying category theory, I have no problems with the definitions but I wonder why it is called Category, I cannot find a connection between the definition and ...
11 views

### Java.NoSuchElementException Error [on hold]

I’m using a iOS compiler app called JedonaCompiler and I am currently trying to code a small text based rpg. I’m adding in a “cmd prompt” of sorts so when I transfer the code to NetBeans I can ...
26 views

### Halting problem of TM which recognize recursive languages is undecidable?

I am preparing for an exam and I came across this question in one of the tests. Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False) The solution ...
16 views

### If problem A is logspace reducible to 2-SAT, is A in NL?

I'm trying to prove that some problem, A, is in NL. I have found a logspace reduction from A to 2-SAT - am right in thinking that this is not sufficient to prove that A is in NL? If so, how does one ...
63 views

### Is it possible to write a program that calculates an algorithm's time complexity? [duplicate]

Title is self explanatory. I have searched here on this site and haven't found any discussion about this. Is it somehow related to Turing's Halting problem (which is undecidable)?
16 views

### when importing natural language tool kit have not attribute '_file_'? [on hold]

When i install the python 3.7.1, and after that i am trying to import nltk natural language tool kit library in command prompt then the Command prompt screen generating the error and the error is ...
20 views

### Understanding access and insertion time of arrays

Why do most implementations of arrays have constant access time and linear insertion time?
11 views

### Distribution of pointer keys in a Skip-list node

Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$. We construct a skip list over the keys. Now if I pick a key (e.g. 31 in the ...
23 views

### Mean geodesic distance between two points in Delaunay Graph

If I have a Delaunay Graph, what is the mean geodesic distance between two randomly chosen nodes. I know that in a small world network, it is in O(log(N)), with N being the number of nodes. Thank you!...
30 views

### Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?

Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is? My attempt: Lets $f(n)=g(n)=n$, then $f(n).g(n)+h(n)=\Omega(n^2)+\theta(n)=\Omega(n^2)$ But given answer is $O(n)$. ...
9 views

### Define a heuristic function in Prolog Programming

I'm working on writing a prolog programming to simulate the sliding-tile puzzle games through best first search algorithm with a heuristic function: the counts of the number of tiles out of place. ...
12 views

### Numbers lying between single and double precision

The IEEE floating point number format is defined as $$s\underbrace{c_1\dots c_m}_\text{exponent}\underbrace{f_1\dots f_n}_\text{fraction}\text{ (*)}$$ with $s, c_i, f_j$ being either $1$ or $0$. The ...
4k views

### O(·) is not a function, so how can a function be equal to it?

I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$. I understand semantics of it. But $T(n)$ ...
21 views

### Joint Probabilistic Data Association Filter (JPDAF)

I am trying to learn about data association algorithms, and I came across the Joint Probabilistic Data Association Filter (JPDAF). I have read about the algorithm from multiple papers, and am looking ...
13 views

### Co-routines and Threads are same?

Everyone say both Threads and Co-routines are similar to each other. Actually what is difference between Co-routines and Threads? How they work in a program?
15 views

### How to prove that a language is sparse?

I have a decision problem. I feel like the problem has very limited expressive power so that it can not be NP-complete. What are the reasonable ways to try to prove the rough statement "it has limited ...
19 views

### cache coherence: false sharing vs. memory coalescing CPU vs GPU

False sharing is defined on CPU as when atleast two cores write to the same cache line. If the two cores have their own private caches, one will invalidate the other's cache line when they write to ...
930 views

### Relation between Undecidable problems and NP-Hard

I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly. And then, I realized that it is not certain where undecidable problems should be placed. ...
16 views

### Need algorithm to determin whether A>B>C>D expressions are legal [on hold]

I need to define function parameter priority, such as function Func(A, B, C, D, E) Others can write rules to define this priority, I need a algorithm to check ...
26 views

### Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process

The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;( Problem: We implement a merge sort algorithm to sort $n$ items. The ...