All Questions

0
votes
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 ...
0
votes
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 ...
0
votes
1answer
9 views

How to generate a grammer from this language?

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 ...
1
vote
0answers
6 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: $$...
1
vote
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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.
-4
votes
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. ...
3
votes
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 ...
0
votes
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?
-4
votes
1answer
45 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 ∅ ∈ {∅}.
0
votes
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 ...
0
votes
0answers
18 views

What are resources in computer networking? [on hold]

What is the definition of resource in computer networking?
2
votes
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 ...
1
vote
1answer
28 views

Which word could I use for the pumping lemma?

I have a problem to start my proof because I do not find a word $w$ where I can use the pumping lemma. Task: Be $\sum { =\left\{ a,b,c \right\} } $ and $S=\left\{ bx{ c }^{ m }|x\in { \left\{ a,b \...
1
vote
0answers
22 views

Complexity of generating non-uniform random variates

What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) ...
-2
votes
0answers
24 views

Which is the best scheme for memory management

For each of the four processes P1, P2, P3, and P4. The total size in kilobytes (KB) and the number of segments are given below. ...
0
votes
0answers
13 views

Set List Queue Deque Map these are Collection frameworks of Java but can anyone differentiate the unique features among each of them [on hold]

We are know Set List Deque Map Queue are all a part of java collection framework but can anyone please tell me how are the unique in terms of Memory management Fetching Data When is the particular ...
0
votes
0answers
28 views

How do I show that an iterative solution to Tower of Hanoi performs the same exact steps as a recursive solution? [duplicate]

So given the typical recursive solution to the Tower of Hanoi problem wherein you reduce the n-disk tower to two instances of an (n-1)-disk tower i.e move (n-1) disks from start to auxiliary. move ...
2
votes
1answer
11 views

Using LP to prove the max matching - min cover theorem

Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following ...
0
votes
0answers
21 views

Where is kruskal algorithm used in real time? [on hold]

Kruskal algorithm comes under algorithms in which we can be able to jot down the points in favour of the predestination but in real life where are these algorithms used why we have to study those in ...
1
vote
1answer
15 views

Is there any implementation of AO* algorithm?

I'm trying to solve And-Or Graph, and I find AO* algorithm can handle it. Someone said it's already used in AI, but I can't find it in detail. Have it implemented? Or it's just a pseudocode that can'...
0
votes
0answers
13 views

interrupts in operating system

Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instruction ...
0
votes
1answer
21 views

Can you connect an output from a logic gate to 2 or more logic gates or inputs?

I have been given this diagram of a circuit: https://www.google.com/search?q=full+adder+logic+gate&rlz=1C1CHBF_enCA831CA831&source=lnms&tbm=isch&sa=X&ved=...
0
votes
1answer
18 views

Shortest path in graph by flipping binary colored nodes to one color

Given a graph consists of two-colored nodes(e.g. white and black) and a starting node, and every time you visit a node, its color is switched(from black to white, or, white to black), how to find the ...
0
votes
0answers
19 views

Can a Neural Network be Created to Identify the Composer of a Single Song with Python and Tensorflow? [on hold]

I would like to propose a theoretical question. Recently, I have been attempting to complete an experiment involving a neural network. Here are the parameters for my experiment and the specifications ...
9
votes
2answers
1k views

How can you find all unbalanced parens in a string in linear time with constant memory?

I was given the following problem during an interview: Gives a string which contains some mixture of parens (not brackets or braces-- only parens) with other alphanumeric characters, identify all ...
-1
votes
0answers
19 views

How do I read in a txt file into c++ so I can test each character line by line? [on hold]

I am currently trying to figure out how to read in a text file and be able to read in each character line by line, character by character. I am doing this to determine what character is where on a 9 x ...
0
votes
1answer
10 views

How to calculate a direct mapped chace capacity with tag and valid bits?

I've seen some very useful posts about this, but none took into consideration both the tag and valid bits. This is a question I took from a notebook in my computer engineering course. Consider a ...
2
votes
1answer
44 views

How to prove a language is not regular using the Pumping Lemma?

I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult. Task: Prove that $M = \left\{ a^...
0
votes
2answers
29 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 ...
2
votes
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....
2
votes
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 ...
0
votes
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.
0
votes
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 ...
-3
votes
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 ...
2
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
1answer
21 views

Tailrecursive definition for a function

In an exam I took we were asked to provide a tailrecursive definition of a recursive function. I failed miserably and the provided solution makes absolutely no sense to me. If anyone could explain ...
2
votes
0answers
41 views

Update each element to product of all others in linear time, constant additional space, no division

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. There is no solution for this question in the book. I have only been able to ...

15 30 50 per page