All Questions

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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

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-...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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)?

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 ...

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

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 ...

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!...

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)$. ...

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. ...

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 ...

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)$ ...

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 ...

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?

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 ...

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 ...

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. ...

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 ...

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 ...

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}...

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

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 ...

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 ...

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 ...

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.

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, ...

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 ...

How do one solve the following integer program?

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 ...

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 ...

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 ...

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 ...

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 ...

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

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.

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, ...