All Questions

0
votes
1answer
5 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
3 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 ...
0
votes
1answer
26 views

Bytes addressable processor

In MIPS processor, address bus is of 32 bits. So on addressing an instruction, a whole 32 bit instruction is fetched. How is it byte addressable then? I mean if on addressing a particular address, the ...
0
votes
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 ...
0
votes
1answer
13 views

Superposition calculus: Elimination of redundant atoms

Bachmair and Ganzinger (1991), 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', section 5.2, 'Simplification and Deletion Techniques', page 17, 'Elimination of redundant ...
0
votes
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 ...
6
votes
2answers
120 views

Why Church-encoded types aren't sufficient to express inductive proofs?

I've heard some claims that the calculus of constructions without inductive types isn't powerful enough to express proofs by induction. Is that correct? If so, why isn't the Church-encoding sufficient ...
1
vote
1answer
41 views

Reducing subset sum to even subset sum

I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are even ...
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

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 ...
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
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: $$...
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 ...
2
votes
1answer
83 views

What is the point of traversing a binary tree in preoder, inorder or postorder?

Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?
0
votes
1answer
20 views

How to draw a parsing tree according to syntax diagram?

I would really appreciate if someone can explain the syntax diagram itself and can help to build the parsing tree.
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 ...
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 ...
-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
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 ...
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 ...
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 \...
0
votes
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 ...
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 ...
4
votes
1answer
451 views

Operator overloading: Java vs. Python

Why operator overloading was included in Python and not in Java? How does one decide to include or exclude operator overloading in a programming language? It is said here that operator overloading is ...
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
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.
0
votes
1answer
30 views

Regular expression or automata for language with odd number of 0's and odd number of 1's

Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I ...
-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. ...
-4
votes
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 ∅ ∈ {∅}.
5
votes
1answer
258 views

Mean and median distance in unweighted graph

I have a very large graph of ~7 million vertices and ~100 million edges. One dfs run in my current implementation runs in 30 seconds. The graph is an unweighted directed strongly connected graph. I ...
3
votes
0answers
29 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 ...
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 ...
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?
5
votes
2answers
548 views

Pumping lemma: if you can keep pumping, what does this tell you?

Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation,...
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?
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 ...
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
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 ...
0
votes
1answer
15 views

Algorithm for blending/merging shapes together like liquid

This is a basic example of how 2 circles would come together: A more complex example would be an arbitrarily shaped polygon like a country on earth, merging with another one or a circle. All of the ...
1
vote
2answers
196 views

Are there pseudorandom number generators (PRNG) with no finite period?

The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period? For this question it is not ...
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 ...
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 ...
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
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
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
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 ...

15 30 50 per page