All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
16 views

How to implement a trail for pointer on the screen like the one in fruit ninja game (image in the question)?

So I basically want to make a trail behind a cursor - I'm fairly new to coding and am more interested in the method then some exact code which will do the thing. I've attempted to solve the problem in ...
4
votes
0answers
55 views

How to prove that the problem $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ is undecidable?

Lately I came across a problem: $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ And I need to comment on its decidability. Now I know that context free ...
1
vote
1answer
52 views

What does “linear” in Linear Temporal Logic refer to?

Consider the term linear temporal logic (in the meaning of linear-time temporal logic). In linear temporal logic, what does linear refer to: to temporal or to logic? If I interpret http://en....
1
vote
2answers
63 views

Disprove sorting in O(log(n))

Assume an array $X=[x_1,...,x_n]$ is given, where each $x\in X$ is an integer. Array $X$ is sorted if $x_1 \le ... \le x_n$. Typical sorting algorithms have a worst-case performance of $\mathcal{O}(n\...
0
votes
0answers
35 views

How much byte do we need to record the route taken by a packet?

I am studying about IPV4 header. For some options, such as one that records route a packet has taken, 40 bytes is far too small, making that option useless. What does this mean? What I know? IHL ...
3
votes
1answer
35 views

Can a non deterministic finite automaton go into infinite loop?

Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and ...
0
votes
1answer
42 views

Simplifying the Language of this DFA

Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
0
votes
1answer
39 views

Constraining function inputs; what concept/terminology am I looking for?

A function takes some set of inputs and creates a set of outputs; however there will be some set of invalid inputs. For example say we have F(a,b) => a / b and we constrain 'a' & 'b' to be ...
0
votes
1answer
26 views

Checksum Algorithm that produces correct 16-bit checksum valie for any given input

I need a checksum algorithm that produces the correct 16-bit checksum value for a given input. It's a packet recording from serial communication that I would like to reverse engineer. I have two data ...
0
votes
1answer
59 views

Why XML dumps from Wikipedia are so compressed?

Few years ago I downloaded an XML dump of one of Wikipedia's fandom sites. It was the XML datadump of Marvel Fandom. The XML was zipped , size was 900 MB (approx). But when I unzipped it , it was ...
0
votes
0answers
17 views

Number of possible boolean functions in a DAG of lookup tables?

A K-input lookup table (K-LUT) can represent any function with K boolean inputs and a single boolean output. The number of possible functions represented by this LUT is $2^{2^K}$ according to this ...
1
vote
1answer
56 views

Making use of one function to recursively find n/3 of another

Given an algorithm M that computes the median of an array A in O(n) time, describe an O(n) algorithm to repeatedly call M in order to find the element of rank n/3 in A. This is a problem I am tasked ...
0
votes
1answer
60 views

Can one brute force entries to create the whole file?

I want to know if one can brute-force a large list of entries (>10,00,000) in linear time to form a whole file. For example: I have an ebook and i extract all the words and symbols from that ebook....
0
votes
0answers
50 views

Sequential Tasks with Greedy Algorithm

We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and therefore only one task can be ...
1
vote
1answer
63 views

Another version of Geography Game

The classic definition of normal “Geography Game” is the following: Each player on her turn choose a word such that starts with the last letter of the previously choosen word by another player. (...
1
vote
0answers
30 views

Filling in the image by the brain

The Cones and rods are not evenly or precisely sensitized on the retina by incoming light. Because of this, the image is formed with distortions. But the brain corrects these deformations through a ...
0
votes
0answers
34 views

How to trasnform search tree into AVL tree with constant memory and in linear time?

How to transform search tree into AVL tree with constant memory and in linear time ?
0
votes
1answer
46 views

How to use pumping lemma on languages that do not follow a strict structure?

Let me preface this by saying, I do NOT want an example of a proof, I would merely like pointers as to how I could approach this problem. For example, I have a language: $$L = \{w \mid w \in \{0, 1\}^*...
0
votes
1answer
44 views

Can a grammar that has only one leftmost derivation tree for every sentence, have more than one rightmost derivation tree for some sentence?

I'm currently studying the book Engineering a Compiler by Keith Cooper, and in chapter 3, there is the following definition: A grammar G is ambiguous if some sentence in L(G) has more than one ...
0
votes
1answer
17 views

Computation branches on NTM

I would like to run the following string $w=011101$ on the following NTM and figure out the respective computation branches and whether it accepts or rejects that string. $\text{Start: }(q_0) 011101 $ ...
0
votes
1answer
29 views

Query sum of values between lo and hi for a stream of numbers

Suppose you have a stream of incoming numbers that you're storing and at any given instant in time, you want to query the sum of values between a given lo and ...
0
votes
1answer
33 views

All 1D lines overlap each other

I want to verify the correctness of this algorithm. Problem: given a list of intervals, where the first index is greater than the second, determine if every interval overlaps with every other interval....
0
votes
0answers
19 views

Looking for a multi-processor job scheduling strategy simulator

I hope this is the appropriate Stack Exchange site for questions like this. Recently, a college student and I are looking for a robust software for simulating job scheduling in multi-processor ...
10
votes
2answers
4k views

Can I multiply Big-O time complexities?

Can I multiply Big-O time complexities? For example: $O(n) \cdot O(n) = O(n^2)$? UPDATE: The question came from my observation that different sources analyze their algorithms in different ways. For ...
2
votes
1answer
58 views

What is the computational complexity in big O notation of an algorithm computing n^n?

I have a number n of size s. What is the computational complexity in big O notation of an algorithm computing n^n? Let's assume I'm using exponentiation by squaring. The result size doubles when we ...
1
vote
1answer
50 views

Prove that the expected length $E [n_{h(k)}]$ of the list containing key $k $ is at most $1 + \alpha$

Theorem: Suppose that a hash function $h$ is chosen from a universal collection of hash functions and is used to hash n keys into a table $ T$ of size $m$, using chaining to resolve collisions. If key ...
0
votes
2answers
56 views

Can 2 files have "same" "many" "different" types of hash?

I know that hash collision is possible with large number of files. But i want to know if 2 files can share "many , different" types of hash. I have 2 hashes SHA256 and BLAKE256 (Both will ...
1
vote
0answers
24 views

Is non-equivalence of regular expressions with union, concatenation and squaring NEXPTIME-hard?

On wikipedia, page about EXPSPACE it says An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions ...
0
votes
0answers
54 views

Regular language closed under homomorphism

I am trying to solve problems from the textbook 'Introduction to the Theory of Computation' by Micheal Sisper, 3rd edition. I am attempting to show various properties of regular languages and their ...
1
vote
1answer
27 views

Test whether words of less a's than b's or c's but not at the same time is context-free

I want to test whether $L= \{w\in\{a,b,c\}^* \mid |w|_a<|w|_b \text{ or } |w|_a<|w|_c,\text{ but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so. The closest ...
1
vote
0answers
26 views

"Universe-shrinking" function in Agda

Agda does not allow datatypes in one universe to be indexed by, or non-trivially parametrized by a type in a larger universe (strangely, Coq does not appear to require this for propositional ...
4
votes
0answers
36 views

Why semaphores lead to loss of modularity?

In this article Semaphores in Operating System and other articles on the internet, they have mentioned one of the disadvantages of semaphores is that it leads to loss of modularity. They further said ...
1
vote
2answers
100 views

is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$?

is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$? I can't figure out how to prove or disprove this. if it is true, is it true only when the function $h$ is invertible?
0
votes
1answer
22 views

What's the time complexity of finding all size-$k$ combinations from a set of size $n$?

I'm wondering what's the time complexity of finding all size-$k$ combinations from a set of size $n$(note that $k$ is a known and fixed constant, say $k=3$)? How does it differ from the time ...
0
votes
0answers
14 views

Do time-constructible functions exist in relativized worlds?

I know that time-constructible functions are necessary to prove the Time Hierarchy Theorem and being computable functions they are computed by Turing Machines. I'm just confused in that since the Time ...
0
votes
1answer
53 views

How many unique Huffman codes can you make. Image I has size 256x256 and has pixels of values 50,100 and 200

Let I (M x N) be an image made only of 3 pixels, how many unique Huffman code can you make (example: Image I has size 256x256, and has pixels of values 50,100 and 200). If someone can help me how to ...
2
votes
0answers
51 views

Proving that a successful search of hash function is $\Theta(1+\alpha)$

Question: Prove that successful search of hash function with chaining (list at each slot) takes $\Theta(1+\alpha)$. Given a dictionary or hash table that has a chain at each slot in case we have a ...
1
vote
1answer
978 views

HackerRank August 2021 Coding Challenge - Minimum Time Needed to Finish All Tasks

I was doing the HackerRank Coding Challenge and ran into this problem. I thought through it a bit but wasn't able to come up with a concrete solution, and going through the solution was not very ...
2
votes
2answers
221 views

Implement a dictionary by using direct addressing on a huge array

For the following question from Introduction to Algorithms book, "We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage,...
1
vote
0answers
41 views

Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?

From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
0
votes
0answers
40 views

Analyzing Hybrid Merge and Insertion Sort

We know that merge sort takes O(n log n) and insertion sort takes (n^2) for worst case. The combination of these two algorithm is to speed up and reduce key comparisons, as for a subarray with small ...
0
votes
0answers
6 views

Are goal-reaching and optimizing the utility function special cases of performance measure?

In َArtificial Intelligence: A Modern Approach by Russell, performance measure is defined as something evaluating the behavior of the agent in an environment. Rational agents are defined as agents ...
6
votes
0answers
126 views

Counting number of swaps to make two strings equal in linear time

The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant. ...
0
votes
0answers
16 views

How to mix populations in multi population genetic algorithm?

I'm working on an optimization problem using genetic algorithm. To increase diversity of potential solutions I'm using multi-population approach: Instead of evolving one population I run 10 ...
5
votes
2answers
155 views

How does $Θ(\log(n!))=Θ(\log(n^n)$?

How does $Θ(\log(n!))=Θ(\log(n^n)$? I understand why $Θ(\log(n!))=Θ(n\log(n))$ and $Θ(\log(n^n))=Θ(n\log(n))$, therefore $Θ(\log(n!))=Θ(\log(n^n)$. But I am having trouble reconciling this with the ...
0
votes
0answers
23 views

Number partition subjected to the cardinality of subset

I hope someone can take some time to consider the following problem and welcome to discuss together. Number partition problem is one of well-known NP-hard problems. Now I am considering the hardness ...
3
votes
2answers
127 views

Hamiltonian cycle in $C_n^k$ in polynomial time for constant $k$?

Let $C_n$ denote the cycle graph over $n$ vertices. Let $C_n^k$ denote the $k$-th power of the cycle graph, or namely that for two vertices $i,j$, $(i,j)\in Edges(C_n^k) \iff |i-j|\leq k$ for a ...
-1
votes
0answers
22 views

Need help with a Minimum Window problem using the python language. Only the min_window function needs fixing

The "contains"function is used to determine if a string contains all of the letters a, b, and c. This function works fine. ...
0
votes
0answers
12 views

Mechanism of improved version of Howard's algorithm

For Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems , could anyone advise how the following Howard's algorithm works to compute minimum mean cycle path ?
0
votes
0answers
27 views

Is this language in RE?

Given the following language: $$L=\left \{ <M> | \exists L \in R \quad s.t \quad L(M)\subseteq L \right \}$$ I need to determine it's compuation class(R or RE). I used Rice Theorem as follows to ...

15 30 50 per page
1
5 6
7
8 9
840