# All Questions

44,282 questions
Filter by
Sorted by
Tagged with
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$, ...
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
11 views

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

• 221
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
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 ...
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 ...
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 ...
18 views

### Computer Architecture MIPS assembler with predictors

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