All Questions
44,282
questions
0
votes
0
answers
12
views
Search algorithm with at most a constant $k$ failed accesses
Let $A$ be an array sorted in non-increasing order. Let $m$ be a natural number. For example, let $m = 10$. We want to find the index $i$ such that $A[:i]$ contain elements less than or equal to $m$, ...
0
votes
0
answers
8
views
Pipeline and interrupts
Does interrupts ease the pipeline process, or is it the opposite?
How pipeline is affected by interrupts in MIPS processor?
- 1
1
vote
1
answer
11
views
Finding bits per address in memory
I dont know if this is any important IRL, but I am trying to understand lines below.
4K words of main memory (this implies 12 bits per address).
4M X 16 means the memory is 4M long (4M = $2^2 \times
...
- 11
0
votes
2
answers
32
views
Java | If a=250, b=3, c=(a + b/2)/b * b, Why doesn't c equal 251 but rather 249?
If
int a = 250;
int b = 3;
int c = (a + b/2)/b * b;
Why doesn't c equal 251, but rather 249?
How is it that ...
- 115
0
votes
0
answers
17
views
How to solve Advanced Databases Exercises [closed]
Hello I am not able to solve this problem, can someone help me with this:
I've tried reading from books but they don't explain how to do examples like this so if someone can solve this please solve ...
- 1
0
votes
0
answers
10
views
CPU benchmark test depending on motherboard?
I have a question if a motherboard is important for a cpu benchmark test? I know it is important for a GPU but what is the case with a CPU? Or is a CPU benchmark test independent from a motherboard?
- 1
-2
votes
0
answers
13
views
Calculating augmenting graph for anti parallel edges
Suppose in a network an edge from a to b has capacity 8 and current flow 3. And the
edge from b to a has capacity 7. What will be the augmenting graph for this edge?
My Thoughts:
In the network flow ...
-1
votes
1
answer
8
views
Modified knapsack problem with multiple boxes to choose from
I have seen the solution to the knapsack problem and understand it. But I am trying to
come up with a dynamic programming solution to the following problem, which is a modified
a version of the ...
0
votes
0
answers
14
views
Expressing polynomial time in terms of first order logic
A problem is said to be computable in polynomial time if its run time is a polynomial
function in input size n. This is the standard definition.
Is there a way to express this using first-order logic?
- 23
0
votes
0
answers
12
views
Circuit Complexity of Permutation
We are here considering permutations of the form $F_2^n \mapsto F_2^n$. I am interested in the $AC^k[2]$ circuit complexity of such functions. What are the upper and lower bounds in this context? Does ...
- 101
0
votes
0
answers
21
views
If verify() -> valid, then validate() -> what?
Invalid blocks will be detected and rejected because it is difficult to compute a valid block, but computationally easy to verify one.
From: p. 23 of ‘Blockchain Technology Overview’ National ...
- 101
1
vote
1
answer
66
views
Covering all colors with unit intervals
Suppose we are given $n$ points on the real line, where each point is colored with a color from set $C=\{c_1,c_2,\ldots,c_k\}$ that contains $k$ distinct colors. We try to cover the $k$ distinct ...
- 11
0
votes
1
answer
28
views
Interpreting the time complexity of a program from function
$T(n)=5T(n/3)+n^2$ Consider this to be the running time of a program. How could we interpret
then numbers 5 and 3.
My Thoughts:
5 times will mean that the problem is divided into 5 subproblems each of ...
- 23
1
vote
1
answer
28
views
MAX-SAT 2-Approximation algorithm
I have the two following questions:
I know SAT -> MAX-SAT but how can I show that if MAX-SAT is solved in polynomial time then SAT is solved in polynomial time as well?(I guess using approximation ...
- 37
0
votes
0
answers
16
views
Avoid for-loops in numpy calculation [closed]
I'm writing a Python function to integrate a vector field on a high-dimensional matrix space. A, shape (n, m), is a matrix whose ...
- 111
0
votes
1
answer
23
views
Finding smallest triangle to fit all points
I'm supposed to find an algorithm that, given a bunch of points on the Euclidean plane, I have to return the tightest (smallest) origin centered upright equilateral triangle that fits all the given ...
- 221
0
votes
0
answers
17
views
Does MFLO instruction in MIPS causes conflict?
Does MFLO instruction in MIPS causes Data conflict, and how to check that?
Example:
sll $s1, $s1, 1
div $s0, $s1
mflo $s2
lw $t0, $s1
add $s1, $t0, $t1
- 1
0
votes
0
answers
16
views
Correctness implication graph for 2-sat
i want to proof some stuff for the 2-sat problem.
So we have something like this:
$\varphi$ = (x$_{1}$ $\lor$ y$_{1}$) $\land$ (x$_{2}$ $\lor$ y$_{2}$) $\land$ ... $\land$ (x$_{n}$ $\lor$ y$_{n}$). We ...
- 11
0
votes
0
answers
9
views
Why does this program give the right answer when main and bin are static, but gives 0 other wise? [closed]
When I remove the two words in bold, the program prints 0 instead of the binary equivalent of the decimal number I enter. Why is that??
...
- 1
0
votes
0
answers
6
views
How to arrange web scraped data in a table using R? [closed]
Below is the code used to scrape data regarding movies from IMDB.I'm struggling to arrange it in a table
Original Code:
library(netstat)
library(RSelenium)
library(tidyverse)
obj<-rsDriver(browser=&...
1
vote
0
answers
14
views
Long and short memory in reinforcement learning Connect 4 AI
I'm writing an AI based on reinforcement learning to play Connect 4. That's my second bot and attempt to RNN and AI (first was copy a code of snake RNN AI from youtube) and I'm looking for some ...
- 11
-2
votes
1
answer
27
views
determining the relationship between two regular languages using the myhill nerode theorem
For a regular language $A$ with an alphabet $\Sigma$, define an equivalence relation for strings $x,y \in \Sigma^*$ by $x\equiv_A y\Leftrightarrow \,\forall w\in \Sigma^*, xw, yw\in A$ or $xw, yw\not\...
-2
votes
0
answers
22
views
Moore law prediction
Is Moore's law is about hardware or is it also about the computation power of CPU? or whole system?
I went through link here and it looks its more about CPU but can we apply it for whole system? Is it ...
- 83
0
votes
0
answers
9
views
Cutting stock problem upper bound with gilmore and gomory
I am trying to implement this article https://arxiv.org/pdf/1905.04897.pdf (the article is there only for information, no need to read it to answer my question)
At some point they say when talking ...
- 1
-4
votes
0
answers
24
views
Hard Disc Drive [closed]
who can help to Identify the main functions used in the hard disc system to store and retrieve data. and Identify the main components used in hard disc drives. also to Explain how the main components ...
0
votes
1
answer
33
views
Determine if string can be constructed from given building blocks
Let's say building blocks are X, Y, XX, YY, XY and YX. Each building block has an associated count ($c_X, c_Y, c_{XX}, \ldots$, $c_i$ can be 0).
Given a string $s$ and building block counts, figure ...
- 143
1
vote
1
answer
29
views
A red-black full tree where every black node has at most 1 red child has at most (n-1)/4 red nodes
Let us call a red-black tree strict when every black node has at most one red child.
Show that a strict red-black full tree has at most $(n − 1)/4$ red nodes; a binary tree is full when every node has ...
- 369
0
votes
0
answers
9
views
Why do we talk of Affine Subspaces in terms of their codimension more than their dimension?
We know that the dimension of an affine subspace $U=H+a, (a \in V)$ equals the dimension of subspace $H$ of vector space $V$. But whenever I read about affine subspaces, I find it mentioned with its ...
- 11
1
vote
1
answer
18
views
Proving that the greedy algorithm for job scheduling has a 2 - (1/m) approximation ratio
In the scheduling problem, the input is a sequence $T_1,T_2,...,T_n$ which are the times of $n$ jobs to be executed in m identical machines. A schedule is an assignment of the jobs to machines.
The ...
- 369
-2
votes
1
answer
45
views
Approximate x*(a/b)^(c/d) using integer arithmetic only (assembler)
0 < x,a,b,c,d < M are all positive integers (uint64).
also, a<b if that helps.
we have assembler (integer only) operations available (e.g. division only yields integers).
we want to ...
- 1
-2
votes
0
answers
18
views
SQL query problem: Only first 3 active affiliate commision out of 10000 recruits is calculated and only for first 3 sales from each recruits?
Create a database query to recruit Mike in the business and they recruited 200 individuals as their business affiliates the first active individual who made their $100.00 monthly membership fee would ...
- 1
1
vote
1
answer
43
views
Why is the certificate version of NP so ubiquitous?
I've noticed that the certificate/verification version of the definition of the class NP is much more popular online than the Turing machine version. In particular, the Wikipedia page has the ...
- 111
0
votes
1
answer
36
views
Does a closed formula exist for each recurrent formula?
I'm interested in a question that probably lies close to the very concept of recursion. I have no idea whether my statement is true or false, neither I have tools to check it, so I'll just ask the ...
- 11
-1
votes
1
answer
18
views
How to prove non-regularity with Myhill-Nerode theorem?
I have a problem in proving of nonregularity of EQ_n = {u = v2v : |v| = n}. I just dont know how to start. Can you help me?
3
votes
0
answers
23
views
Polynomial multiplication in finite field without smooth-order roots of unity
I am working in a finite prime field $\mathbb{F}_p$ that does not have primitive $n$-th roots of unity for any large smooth integer $n$, which makes FFTs a bit difficult.
If I need to compute a ...
- 43
1
vote
1
answer
54
views
Exact formulation of definition of $NP$, in relation to $R$
One definition for $P$ is the set of all languages that have a deterministic turing machine $M$ s.t. if $x\in A$ the machine accepts in polynomial time and otherwise it rejects, also in polynomial ...
- 153
2
votes
0
answers
16
views
Algorithm to find best alignment of one curve onto another
So I've boiled a certain problem I have down to the point where I have two images of (approximately) the same scale. One which contains a closed curve, and one which is a partial curve. I want to ...
- 21
-1
votes
0
answers
26
views
how would i reduce from 3sat
A set 𝐴 of vertices in a graph is well-positioned if every vertex in 𝐺 has distance at most 1 from some vertex in 𝐴. (So 𝐴 could be where we build our new chain of coffee-shops. Distance at most 1 ...
- 21
0
votes
0
answers
37
views
I need to show that the problem is NP-complete
Double-SAT = {𝜓: 𝜓 has at least two satisfying truth assignments}. Hint: reduce from SAT. Start with a formula 𝜑 and modify it to get a formula 𝜓 so that 𝜑 is satisfibale if and only if 𝜓 has at ...
- 21
0
votes
0
answers
17
views
Learner Algorithm Time & Sample Complexity
Let $X=R^{2}$. Let $u=\left(\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\
w=\left(-\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\ v=\left(0,1\right)$
and $C=H=\left\{h\left(r\right)=\left\{\left(x_{1},x_{2\ }\...
- 221
2
votes
1
answer
16
views
Graph Layout Algorithm that optimizes only `x` (not `y`) of nodes?
I have a hierarchical graph structure on a vertical timeline with nodes that have a fixed y coordinate. I am now looking for:
an algorithm (suggestions, any ...
- 131
0
votes
0
answers
47
views
Complexity of finding the kth smallest element of all the elements in two order statistics binary search trees
What is the time complexity of finding the kth smallest element of all the elements in two order statistics binary search trees? An order statistics tree is a binary search tree where the size of a ...
-1
votes
0
answers
15
views
How to create database query to calculate automated commision for each associate?
The following queries required:
1] Provide the commission tabulations due each month to associates
2] Along with the commissions for each associate provide the actual number of active memberships that ...
- 1
-1
votes
0
answers
15
views
Why does the error :"name lambdify' is not defined" come? [closed]
I wish to convert the partial derivative expression from symbolic form to ordinary python function. I used the Lambdify function. But error is coming. May I know why do i get error.
I followed the ...
- 99
-1
votes
0
answers
18
views
1
vote
1
answer
48
views
Enumerating through Turing Machines That Solve Same Problem
Is it possible to enumerate through all the Turing Machines that solve the same given problem? For example, we know that there exists a Turing Machine that finds a satisfying assignment given a 3SAT ...
- 11
0
votes
0
answers
24
views
How will changing the splitting point in merge sort affect the algorithm and its time complexity
Everyone knows that merge sort will continuously divide the array into halves until they are small enough to (like 2 elements per block or so) be able to be sorted quickly, hence its time complexity ...
- 1
2
votes
1
answer
49
views
Solution Verification: How does the postorder traversal of a BST change after rotating left?
Given a BST $T$, $x$ is a random node in it and $y$ is the right child of $x$.
How does the PostOrder traversal of BST $T$ change after we rotate the tree left on node $x$? In which cases does the ...
- 165
0
votes
0
answers
83
views
DenseSet with at most k subset [closed]
For a Theory of computation homework, I'm assigned to prove that the following language is NP-complete:
$$DenseGraph = \{\langle G, k \rangle : G\text{ has a dense set of size at most $k$}\},$$
where ...
- 23
-1
votes
0
answers
16
views
From $m mod n = m', 0 \leq m' \leq n-1$ I want $min_ \leq m' \leq n$ [closed]
Can anybody get an inclusive modulo ring [min_, n]. My attempt so far is...
m mod n = m' where 0 <= m' <= n-1
then
m' + min_ = min_ <= m' <= n-1 + min_
and...stuck
Again I'm trying to get
...
- 153