All Questions

Filter by
Sorted by
Tagged with
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$, ...
user avatar
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?
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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?
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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
user avatar
  • 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 ...
user avatar
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?? ...
user avatar
  • 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=&...
user avatar
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 ...
user avatar
  • 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\...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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?
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
  • 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\ }\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
-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 ...
user avatar
-1 votes
0 answers
18 views

Computer Architecture MIPS assembler with predictors

This MIPS code is given: ...
user avatar
  • 1
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 153

15 30 50 per page
1
2 3 4 5
886