All Questions

0
votes
0answers
6 views

Renaming registers

I have this code ...
-1
votes
0answers
5 views

What is the difference between equals () and == in Java?

Islamic pic of khana kaba (https://i.stack.imgur.com/PiiMS.jpg)
0
votes
0answers
3 views

Computing Nash equilibria in discrete auctions

I am trying to compute the (pure strategy) Nash equilibria of some discrete auctions. More precisely, let us define the strategy of each player as a function mapping from every valuation that they ...
0
votes
0answers
4 views

Difference between present - absent bit and valid - invalid bit in a page table?

while reading I found this: Present/Absent bit – Present or absent bit says whether a particular page you are looking for is present or absent. In case if it is not present, that is called Page ...
3
votes
1answer
9 views

Length of shortest codeword in Huffman encoding

Under Huffman Encoding, if one character occurs more than 1/3rd of the time, is it guaranteed that there will be at least one character whose codeword is of length 1? I thought of 2 cases where this ...
0
votes
0answers
19 views

How can I find a language from a given PDA

I have the following PDA: And a given solution for his languages ${L}_{\mathrm{End}}(M_2)$ and ${L}_{\mathrm{PDA}}(M_2)$ with $ \mathrm{L}_{\mathrm{End}}\left(\mathrm{M}_{2}\right)=\left\{\mathrm{a}^{...
0
votes
0answers
16 views

How to train this neural network?

I seek the neural network (NN) which satisfies the 100 equations (i=1,2...100) $\sum_{j=1}^{2000} NN(A_{ij},B_{ij},C_{ij})=Q_i$. Where A,B,C are 100x2000 matrices So I know Q, A, B and C How can ...
0
votes
0answers
11 views

Concrete/theoritical center of a cluster in a general metric space

What i call center is the point which minimize the distance to every points of a specific cluster. From what i know we can look for a concrete point in the cluster get an approximation of the center. ...
0
votes
0answers
15 views

Pipelining and five stage of pipelining

I have a question did I write a good table for next code add r3,r2,47 sw r2,0(r1) lw r1,0(r2) lw r2,100(r1) sw r1,200(r2) sub r3,r5,r6 is this ok? I am not so ...
0
votes
0answers
19 views

Clique number of a graph given its order and average degree

Let $G$ be simple graph of order $N$, and let $\bar{d}$ be its average degree. Find the maximum value of $\omega(G)$ (the clique number of $G$) as a function of $N$ and $\bar{d}$. Find the ...
0
votes
0answers
10 views

Is there any optimization technique for DP with $f[i][j] = \min_{z<j}{f[i-1][z] + G[i][j-z]}$ where G[i] is increasing and positive?

Given a dynamic programming formula like $f[i][j] = \min_{z<j}{f[i-1][z] + G[i][j-z]}$ where $G[i][j]$ is positive and increasing along $j$ for all $i$s. Is there any optimization to make it ...
1
vote
0answers
23 views

From nand to numbers

My understanding is that computers are basically made of nand gates, and that all other gates, such as and, or, etc, can be made from nand gates. So far so good, but how do we get from nand gates to ...
0
votes
0answers
8 views

a key step in speech processing is to extract the “words” appeared in the conversation?

You overheard a computer engineering student saying that a key step in speech processing is to extract (or “tokenize”) the “words” appeared in the conversation, pretty much like what a compiler needs ...
0
votes
0answers
9 views

Bi-criteria combinatorial approximation algorithms for min k-vertex cover

Min k-vertex cover: Given a graph $G = (V,E)$, the goal of the min k-vertex cover problem is to output $k$ vertices from $V$ such that the number of uncovered edges in $E$ is minimized. It is easy to ...
2
votes
2answers
456 views

Easy instances of the coloring problem on graphs with degree at most 4

Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color. In ...
0
votes
0answers
13 views

Optimize an underdetermined system with quartic constraints [on hold]

I encountered an optimization problem which does not belong to any well-known category of optimization. The system has $M$ (typically $M=120$) real variables and $N$ (typically $N=100$) constraints (...
1
vote
1answer
30 views

Proof of undecideability that one state is reached before another

I'm trying to show that, for a deterministic Turing machine $M=(Q,\Gamma,\Sigma,\delta,q_0)$, the language $K$, which includes all of the words $w \in \Sigma^\ast$ where the calculation of $M$ on $w$ ...
-3
votes
0answers
15 views

Turing Machine, basic level [on hold]

write a Turing machine program that recognizes palindromes. For an extra challenge, ensure that when the machine either accepts or rejects, the head is in the start cell and the contents of the tape ...
-1
votes
0answers
30 views

Does $f(x) \not\in O(g(x))$ imply $f(x) \in \Omega(g(x))$? [duplicate]

Does $f(x) \not\in O(g(x))$ imply $f(x) \in \Omega(g(x))$ for all $f$ and $g$? And does $f(x) \in O(h(x))$ where $h(x)$ is at least $g(x)$ imply $f(x) \in \Omega(g(x))$?
2
votes
0answers
15 views

Using exponential penalty functions in constrained nonlinear optimization

Background: penalty functions Penalty functions convert a constrained optimization problem \begin{equation}\begin{split} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & g(x) \leq 0 ...
0
votes
0answers
12 views

How do you handle over half of traffic view a single page? [on hold]

I have a Django web application with Mysql, Nginx. Is there a way to increase performance for a certain page? All I know about increasing performance is using Nginx Caching, DB Caching. Thanks
1
vote
0answers
15 views

What's the problem with deletion in FKS perfect hashing?

In FKS perfect hashing we construct two levels of tables. To lookup an element we first check in the first table which points us to the correct second level table that will contain the element if it ...
0
votes
0answers
9 views

Conventional triangularization approach in computer vision?

m new in learning image processing in openCV concepts ;can somebody help me to understand "Conventional triangularization approach " in computer vision ?
1
vote
1answer
30 views

An algorithm to drop low-priority items from a heap-based priority queue

I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value. (Or, equivalently, to drop from a priority queue realised by such a heap ...
0
votes
0answers
10 views

Understanding hintedhandoff in amazon dynamodb [on hold]

From the dynamodb paper, I see Consider the example of Dynamo configuration given in Figure 2 with N=3. In this example, if node A is temporarily down or unreachable during a write operation then a ...
0
votes
0answers
16 views

How can I express “if at least one element in a certain state exists in set A, then…” in pseudocode? [on hold]

I'm using algorithm2e to write out some pseudocode, and I've come across this condition I'm checking for, and it seems like there should be a more mathematically concise way of writing this out other ...
0
votes
0answers
19 views

Proving Goldbach conjecture in C [on hold]

Our computer teacher gave me an assignment to write a program in C using only loops and if else statements to prove Goldbach conjecture says that every even integer n greater than 2 has the property ...
1
vote
0answers
22 views

Appreciating the concept behind file reading from terminals [migrated]

I am starting out in Operating Systems module and these question really caught me off-guard. These questions have no solutions. (a) In Windows, start a command line shell, eg. cmd. Assuming that you ...
0
votes
0answers
22 views

Would Schmidhuber's theories of everything be capable of performing hypercomputation?

Jürgen Schmidhuber pointed out that a simple explanation of the universe would be a Turing machine analogy programmed to execute all possible programs computing all possible histories for all types of ...
5
votes
1answer
109 views

How does treewidth behave under graph minor operations?

It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq_m G$), the treewidth of H is smaller than or equal to that of G. Minors of a graph are created through the ...
1
vote
0answers
30 views

Confusion about the geometric interpretation of the simplex method for linear programming

In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of ...
2
votes
1answer
36 views

Appreciation of the 5 state process model

I'm starting out in an Operating Systems module. I have a few understanding questions to think about, which will not be gone through in class. A process state model is an abstraction (or model) which ...
0
votes
1answer
41 views

Let u and v be two strings. What about the reverse order of their concatenaited string?

let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$? Note: The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.
0
votes
0answers
23 views

Time complexity of quicksort for arrays in increasing or descreasing order

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order. Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
1
vote
1answer
13 views

When is a root node an articulation point in a graph?

I am trying to find the articulation points in a connected undirected graph and I'm finding it difficult to figure out if the root node of the DFS is an articulation point. Based on the literature I'...
1
vote
1answer
25 views

Recognizer to check if the language of a Turing machine contains a finite subset

Let $B = \{ 123 \}$. Note that $B$ is finite. Let $L = \left \{ \left\langle M \right\rangle | M \text{ is a Turing machine such that } B \subseteq L(M) \right\}$. Is it sufficient to show that $...
0
votes
0answers
32 views

What is the time complexity of the below algorithm?

Below I have two algorithms for finding the maximum 2 numbers from an array of numbers of size>=2. n=Size of the array Algorithm 1:- 1. Loop through the array, find the index of max number. (n ...
-2
votes
0answers
27 views

What are expanding opcodes? What are they good for? What would be a simple example?

I really am in need of some thorough explanation here. A little bit simpler and more understandable than in the textbooks or youtube slides lectures. Turned out to be slightly more complicated to ...
0
votes
0answers
27 views

Does a Turing complete set of invertible combinators exist?

We'll say that a combinator A is invertible if there exists A' s.t. A'(Ax) = A(A'x) = x For example, Sxyz = xz(yz) is clearly invertible in this sense because we ...
1
vote
0answers
16 views

Computing a shortest $M$-alternating walk (for the Blossom algorithm)

When explaining the Blossom algorithm for maximum (nonbipartite) matchings, Shrijver describes, given a simple graph $G = (V,E)$, a matching $M \subseteq E$, and the set $X \subseteq V$ of nodes ...
0
votes
1answer
27 views

Is this problem hard? Finding all the subsets of size k from a sequence of n numbers

I want to know the hardness of finding all subsets of size k from a sequence of n numbers. There is an algorithm based on recursion: Print all possible combinations of r elements in a given array of ...
0
votes
0answers
13 views

What year exactly did Dijkstra distribute EWD682?

The Dijkstra's archive says EWD682 was written or distributed between 1976--1979. I wonder if you can tell the exact year. It might not be easy since the archive itself didn't make it.
0
votes
0answers
11 views

How could the Cuckoo Search be implemented into Python? (Presumably a solver) [on hold]

I was looking to do this for just a fun project, and maybe mine some GRIN coin.The proof-of-work for GRIN is the cuck(ar)oo29 algorithm, with 29 nodes in each graph. There is also an ASIC chain, for ...
0
votes
1answer
51 views

What are the axioms of automata theory?

Every theory has axioms and theorems derived from axioms. How many axioms are there for automata theory? What are the axioms of automata theory?
3
votes
1answer
41 views

Small space hash functions that are weakly but not strongly universal

This is a follow up to this this question about weakly universal hash functions A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ : $$P_{h \in H_w}(h(x) = h(y)) \...
1
vote
1answer
27 views

Minimum Spanning Tree with one particular edge minimised(continued)

I have recently encountered a coding problem, specifically, the CCC problem S4. In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each ...
5
votes
1answer
36 views

Mildly context-sensitive grammar

Consider a context-sensitive grammar $G$, such that all the productions of $G$ have the form $A\to \alpha$ or $Ab \to \alpha b$ (in other words, the left context is always empty and the right context ...
1
vote
1answer
16 views

Converting CFG from GNF to CNF

I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is ...
0
votes
1answer
28 views

Recursively edit 2-D array using backtracking

I have a 2-D array which contain 3 types of elements: C (Contaminant) R (Rock) W (Water) The rule is that: contaminant can seep through water but not through rocks. Let's say I have the ...
0
votes
3answers
24 views

Relative efficiency of n tasks in 1 loop vs. 1 task each in n loops?

Say I have 3 simple tasks, to find the min, the max, and the average of an array of numbers. A modular approach would be to write one function for each, thus iterating over the array thrice. However, ...

15 30 50 per page