All Questions

1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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-...
-4
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
1
vote
0answers
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 ...
3
votes
2answers
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)?
-1
votes
0answers
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 ...
0
votes
1answer
20 views

Understanding access and insertion time of arrays

Why do most implementations of arrays have constant access time and linear insertion time?
0
votes
0answers
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 ...
2
votes
1answer
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!...
0
votes
1answer
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)$. ...
0
votes
0answers
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. ...
0
votes
0answers
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 ...
10
votes
7answers
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)$ ...
0
votes
0answers
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 ...
0
votes
0answers
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?
0
votes
0answers
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 ...
0
votes
0answers
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 ...
5
votes
3answers
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. ...
-3
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
25 views

What is the meaning of max() in intro. to algorithms?

I'm reading chapter 3(growth functions) of CLRS and in giving an example of proving theta for a standard quadratic function the book gives the following value for $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a}...
1
vote
1answer
25 views

How does this use of “apply” in Coq work?

I'm working my way through software foundations. In the Chapter titled "Tactics", I'm able to prove this theorem in Coq: ...
1
vote
0answers
30 views

Roadmap to formal verification

I would like to learn about different approaches to formal verification of software programs that goes beyond what Wikipedia has to offer. Ideally one would not only get an overview but also ...
0
votes
0answers
15 views

Partial Recursive Functions of Kleene [on hold]

I am writing and asking for your help, if you could give me any good sources for the topic which is in the title. I have to do a powerpoint presentation this week and I really couldn't find any ...
0
votes
0answers
17 views

Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#…#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]

Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
-1
votes
0answers
54 views

prove that the language {x y x^R | x, y ∈ {a, b} ∗} is context free [duplicate]

If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping lemma.
0
votes
0answers
11 views

Finding the intervals containing the query interval

Intervals are represented by two numbers, let's say integral numbers. At the beginning we have sequence of given intervals, for example [1, 5], [4, 8], [3, 5]. After that, we have sequence of queries, ...
1
vote
1answer
163 views

Define a DFA that accepts all even length binary strings that don't contain the substring “111”?

I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly ...
0
votes
1answer
16 views
0
votes
1answer
23 views

Why is Byzantine Generals Problem with traitors possible?

My question is what makes the Byzantine Generals Problem possible to solve in some cases where traitors exist, for example in the case where there are 4 generals with 1 traitor? If the generals must ...
0
votes
1answer
13 views

n-DNF boolean formula k satisfiability

Given an n variable boolean DNF formula and a number k, does this formula has satisfying input combination greater than k?. (0<=k<=2^n). Where input is infinite number of n tuples where ...
2
votes
1answer
17 views

How does hashed inverted page table work?

I understand hash function and inverted page table, but then the book I read describes something called hashed inverted page table (use hash to accelerate the finding because IPT is large), with TLB ...
0
votes
1answer
16 views

Is this language recognizable?

Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable. I don't think it's even recognizable, but I'm not sure. Regardless, I ...
0
votes
1answer
11 views

Possible complement of $L =\{a^n b^{n+1} : n\geq0 \}$

The language was $L =\{a^n b^{n+1} : n\geq0 \}$. This is my attempt: I believed $L$ can also be expressed as: $L =\{a^n b^{n}b : n\geq0 \}$ This implies that the number of $b$'s is always greater ...
1
vote
2answers
51 views

Validity of □(P→ Q) → (◊P → ◊Q) in linear temporal logic

How can I prove that $\Box(P\rightarrow Q)\rightarrow (\Diamond P\rightarrow\Diamond Q)$ is valid in linear temporal logic (LTL)?
0
votes
0answers
12 views

contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2} [duplicate]

Is this language contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2}. I think it's not but can't prove it.
1
vote
0answers
22 views

How to find corresponding points between two photos when there's a repeated pattern?

Suppose that I have two photos, I1 and I2 and I want to find a set of corresponding points between the two photos to define a homography between them. There are many algorithms for this purpose, ...

15 30 50 per page