# All Questions

28,864 questions
0answers
2 views

### Banker's algorithm - additional allocation

I have a problem with the banker's algorithm. There are 6 processes and one type of resources. The allocation is (0, 29, 35, 10, 25, 35) and the MAX need is ...
0answers
3 views

### Understanding Hough transform examples in python

I have been reading up about the Hough transform recently, but I want to implement the algorithm (or a follow an existing algorithm such that I understand it) in python. I can't find many resources to ...
0answers
3 views

### NP-hardness does not imply lower bound, strictly speaking?

A problem is NP-hard iff every NP problem can be polynomially-time reduced to it. Hardness is often intuitively explained as a lower bound. But it isn't, strictly ...
0answers
5 views

### How to understand out of bound in the following theoretical context?

Consider the following initialization step of loop invariant for merge procedure Initialization: Prior to the first iteration of the loop, we have $k=p$, so that the subarray $A[p .. k - 1]$ is ...
1answer
12 views

### How to generate a grammer from this language? [duplicate]

I'm trying to generate a grammar from this language: L={a^i b^j c^k d^l : i+j=k+l} to be clear its a in the power of i and b in the power of j... and so on, so ...
0answers
10 views

### Proof of heuristic function in A star algorithm

Maybe I am missing something very easy and obvious. But, I don't understand why estimate cost of source vertex is subtracted from the overall estimate cost, if heuristic function $h$ is monotonic: ...
0answers
8 views

### Is there any relationship between grammar being ambiguous and the language itself?

According to my understanding, a grammar is ambiguous if it generate strings which can be interpreted in more than one ways ( that is , more than one parse tree), but when it comes to the language ...
0answers
9 views

### Stop and Wait Efficiency

A sender uses Stop and Wait protocol for transmission of 8000K bits size frames on a 1Gbps satellite channel with a propagation delay of $400ms$.What will be the link utilization(in percent),if ...
1answer
21 views

### Is it possible that $L=NP$?

According to Wikipedia and other sources, the question whether $L=P$ is an open problem, and of course everyone is familiar with the problem of whether $P=NP$. However, I found absolutely no ...
1answer
14 views

### What Are the Ideas Behind Variations of the Coin Change Problem?

Problem: given a set of n coins of unique face values, and a value change, find number of ways of making change for ...
0answers
7 views

### Algorithm for Team Meetings scheduling optimization

Consider persons P (about 100) and teams T (ca 20), where each person is member of 2-3 teams. Schedule succession of meetings M of teams where each P can attend and optimize waiting time by running M ...
1answer
17 views

### Expectation for the number of leaf nodes in a randomized tree construction

Consider this procedure for building a tree from $v_1, v_2, ..., v_n$: insert $v_1$ insert $v_2$ and connect it to $v_1$ via a directional edge from $v_2$ to $v_1$ insert $v_3$ and with a uniform ...
0answers
5 views

### What is the practical limit to how many object classes you can detect with Faster RCNN?

I am trying to follow this tutorial where the Faster-RCNN-Inception-V2-COCO model from TensorFlow's model zoo is used to detect playing cards. I was wondering what is the practical limit to the number ...
1answer
11 views

### T&PL: Language grammar with terms

I'm autodidacting Pierce's Types and Programming Languages. On page 27 he states a definition for "terms, concretely" in constructing a language of terms, thus: For each natural number $i$, define a ...
0answers
7 views

### Convert Subdivision Curve to Bezier Curve

Wondering if there is a way technically to convert a Subdivision Curve into a Bezier Curve.
0answers
13 views

### #P=NP: All satisfying solutions are valid answers by programs for NP [on hold]

In fact, the implication looks like an equivalence too. All satisfying solutions to a boolean formula are valid answers by programs for NP is equivalent to saying the class #P equals the class NP. ...
0answers
28 views

### What is the state of the algorithmic art for floating point arithmetic on complex numbers?

Most modern compilers and processors implement the IEEE 754 binary formats for floating point numbers. IEEE 754 guarantees that the addition, subtraction, multiplication, division, and square root ...
0answers
19 views

### What are resources in computer networks? [on hold]

Examples of resources in computer networking are printers,file servers,internet and others. What is the definition of resources?
1answer
47 views

### Is ∅ ∈ {{∅}} true? [on hold]

I learned that the empty set is not an element of every set unless the empty set is explicitly included in the set like {∅}, so I believe it is false because it is not ∅ ∈ {∅}.
0answers
14 views

### Definition of multiprogramming

Which combination of the following features will suffice to characterize an OS as a multi-programmed OS? a. More than one program may be loaded into main memory at the same time for execution b. If ...
0answers
18 views

### What are resources in computer networking? [on hold]

What is the definition of resource in computer networking?
0answers
24 views

### Complexity of multiplying two integers of size $n$ and $m$

The multiplication of two integers of size $n$ can be done in time $O(n \cdot \log n \cdot \log\log n)$ using FFT method. If the two integers have different sizes $n$ and $m$, does an upper bound ...
1answer
28 views

2answers
30 views

### Terminology for worst-case N-complexity on $O(1)$ insert after amortisation

Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews ...
1answer
51 views

### Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
0answers
10 views

### Complexity of STRIPS planning for finding optimal solution: PSPACE-complete or NP-complete?

I am reading the two articles below to try to figure out whether STRIPS are NP-complete or PSPACE-complete. Specifically, I am trying to figure out the complexity of finding optimal solutions using ...
0answers
6 views

### How to implement a customize loss function in scikit learn? [on hold]

How to implement a customize loss function in scikit learn? For instance instead of using mean squared error. I want to use mean squared error multiplied by the true value of the sample.
1answer
44 views

### Proof of QuickSort algorithm correctness

Recently I’ve studied QuickSort and understood its general idea. Basically, we do the following: Pick an element from the array (no matter which one and how in this context) Rearrange elements in ...
3answers
69 views

### Does undecidability violate Turing completeness? Shouldn't “complete” include “decidability”?

Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"? That is, if one has a language that's Turing complete, but expresses infinite computation (i.e. may not ...
1answer
34 views

### Split a list of elements into sub lists, each with different criteria

I have a list of elements of different values, say 0 to 3. I want to split it into a certain number of sub lists, each accepting only certains elements. The sub lists may not always have the same ...
1answer
26 views

### Proving NP hardness about graph creation problem with triangle number

I have graph creation problem. Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in ...
1answer
14 views

### Binary Floating Point Range/Precision for 4-bit Mantissa and 4-bit Exponent

I'm trying to understand binary floating point and using just a 4-bit mantissa and a 4-bit exponent (both 2s compliment) to keep things simple. As far as I can tell, the largest denary number I can ...
0answers
27 views

### Decidablity of time complexity

Let $t:\mathbb{N}\rightarrow\mathbb{N}$ be a time constructible function with $t(n)\geq n + 100$. Show that there is no TM $T$ that given the gödel number of another TM $M$, decides wether or not M is ...
1answer
32 views

### Are $A$ and $B$ necessarily be decidable if $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable and $A$ & $B$ being exhaustive?

I found the following question Suppose A and B are recursively enumerable languages such that $A∪B=Σ∗$. Further, suppose $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable. Which of the following is ...
1answer
35 views

### Is the complexity of this algorithm O($\sqrt{n}$) or linear?

Let's say I have two identical jars and I want to find the height that the jars will breaks when dropped from various heights. I can drop the jars from height increments using steps on a staircase. I ...

15 30 50 per page