# All Questions

47,720 questions
Filter by
Sorted by
Tagged with
4 views

...
1 vote
11 views

### Max flow, min cost with upper and lower bounds

:) I am trying to implement an algorithm that fairly distributes people into groups, given their ranking of those groups, while also taking into account their preference for partners. I have modeled ...
8 views

### Need Clarification on Storage Media Statements - Seeking Help

I am currently working on a set of questions related to storage media, and I've come across a statement that seems a bit confusing to me. The question is as follows: Mark all correct statements ...
29 views

### The second shortest path on a directed graph

The question asks to write an algorithm using Dijkstra's algorithm with time complexity of $\Theta(|E| \log |V|)$ that find the second shortest path between s∈V and t∈V. The farthest I managed to get ...
21 views

### Backpack assigment

Can you help me solve this problem. Names of items NAME, sizes SIZE and values VALUE are given. Using dynamic programming, find the optimal filling of backpacks of size M. NAME = {A, B, C, D, E}, SIZE ...
19 views

### Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)

Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element. Any subarray array[start, end] ...
29 views

### Shortest path in polygon from 2 points such that entire polygon is visible

Given an isothetic polygon (sides parallel to the x-axis or y-axis) and 2 points (start and end) on the boundary of the polygon, find the shortest path traveling only in the direction of the x or y ...
8 views

### Dynamic programming problem for minimum cost tower placement

I have an algorithmic problem in which I have a highway that is a straight line of length n and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am ...
14 views

1 vote
36 views

6 views

### Understanding atomic requests/transactions in a snooping coherence protocol

I've been reading the book "A Primer on Memory Consistency and Cache Coherency", and it contains the following paragraph: The Atomic Requests property states that a coherence request is ...
36 views

### Complexity of topological sorting with a special restriction

Let $G = (V, E)$ be a connected DAG (representing a circuit) with every vertex may be one of the following three types: Input variable, with in-degree $0$ and out-degree $\geqslant 1$. A gate, with ...
1 vote
35 views

### How do i make a 2d array as same as i possibly can with another one?

Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different. There's gonna be another nxn array B being input. I can only interchange one row ...
170 views

### Could this novel algorithm be qualified to be published in Nature or Science

I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
50 views

### Necklace Alignment Problem

We are given two cyclic $\{0,1\}$ strings $X$ and $Y$ with both length $n$, containing $k$ 0s and $n-k$ 1s. Suppose positions of 1 in $X$ are $x_0,\dots,x_{k-1}$, for $Y$ are $y_0,\dots,y_{k-1}$. We ...
14 views

### Clique to SAT example explanation

We are at college trying to implement the reduction of the clique problem to a SAT problem but I dont quite get the examples of the slides if someone can give me a not so technical explanation of what'...
29 views

### What's the Time Complexity and total no of iterations?

for a=1 to m means for(a=1;a<=m;a++) for i=1 to n for j=i to n c= c+1; The total no of iterations is O(n^2) ...
7 views

### Construct a pda

Construct the pda that accept following language L * 1 = {a ^ m * b ^ n / 2 * n <= m <= 3n, n >= 1} Trace the operation of M on the string aaaaabb
1 vote
31 views

### Why bisection width of star connected network is 1?

This may seem like a simple question, but I can neither find the answer on the internet nor AI tools can give a proper answer. I was reading a book about static networks and I saw that the bisection ...
1 vote
19 views

### How do I prove relations of two CTL formulas?

If I have two CTL equations, how do I prove they're equivalent or that one implies the other? What's the general approach? Disproving is obvious, but I am unable to figure out how to prove the ...
109 views

### Testing whether a number (N) is prime or not can be made very fast but it will require storage space

Testing whether a number (N) is prime or not can be made very fast but it will require storage space. If there is a central repository that stores all prime numbers found till now and if there is a ...
235 views

### What is the simplified form of this big o

$O(\sum_{l=0}^{log_2n} l*2^l)$. I took the integral of the term which I think is $O(n*log(n))$
10 views

### O(n^3) Algorithm for Maximum Weighted Cycle Cover for Undirected Complete Graph with Triangle Inequality

I have been trying to implement an approximation algorithm for the max traveling salesman problem with triangle inequality, and each paper I've read references the step of finding the max cycle cover ...
15 views

### better ways to integer interpolation?

I made some code about "integer interpolation" for running approximate alpha blending at FPGA which have low quantities of logic gate. Let's refer to "II" as integer interpolation. ...
9 views

### Morton-code based Linear BVH: Why do triangle's bounding boxes' centroids give higher-quality trees than triangles' centroids?

I've implemented linear BVH as described in Karras 2012, and I was using triangles' centroids for Morton Code generation. I found recent papers and implementations use triangles' bounding boxes' ...
29 views

### What is the practical use of list.clear() method in Python?

I was wondering if there is a reason behind clearing all the values in a list and reusing it, as opposed to deleting the list and creating a new one. Are there any practical advantages of using ...
109 views

### If Q* can break encryption would that prove P=NP?

At 12:11 in this video the creator talks about unverified rumors the Q* algorithm can break AES-192 encryption. If this is true, would this mean P = NP?
19 views

### Regarding CPU ILP: what actually consistitutes "the current instruction"?

If a CPU is able to execute multiple instructions in parallel, and fetching/decoding/scheduling instructions happen in batches, and there's multiple execution units, etc. What does the IP register ...