# All Questions

31,823 questions
Filter by
Sorted by
Tagged with
31 views

### Finding the last substring in lexicographical order in O(n) time

Given a string s, return the last substring of s in lexicographical order. Example 1: Input: "abab" Output: "bab" Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "...
4 views

### DEs with fixed solution involving difference of ratios with tiny denominators

I'm trying to numerically solve coupled DEs of the form: a'(t) = b(t) / b0(t) - a(t) / a0(t) b'(t) = a(t) / a0(t) - b(t) / b0(0) where the functions ...
17 views

### AVL tree balance property states for the two subtrees of a node, their height can differ at most one. Why can't it be zero?

I was thinking that if they were equal, say they are required to be zero this would be enforce the balance property more effectively. Can anyone explain why 1 is a satisfactory rather than just them ...
24 views

### Algorithm to find repeated patterns in a large string

For optimization purposes I'm trying to analyze a large list of executed program commands to find chunks of commands that are executed over and over again. This problem is similar to searching ...
9 views

### How Spark Works with RDD [on hold]

suppose I am using Hadoop on top of the spark, and Hadoop contains a text file of 256MB (128,128MB) now I want to Process Some operation on that file how could I achieve it with Spark? How it will be ...
19 views

### Bounded treewidth implies bounded clique-width

We have a graph G of treewidth $\operatorname{tw}(G)\leq k$, for some $k\in\mathbb{N}$. I've seen a claim that that implies that the clique-width of the same graph is at most $k \cdot 2^k$. This ...
20 views

### Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy?

When defining $\Sigma_i^P$ or $\Pi_i^P$ completeness, we want to use a reduction that fulfills the following property: If $L' \leq_p L$ and $L \in \Sigma_i^P$ or $\Pi_i^P$ respectively, then $L'$ is ...
98 views

### What does canonicity property mean in Type Theory?

The "Computational Component" section of the Type Theory - Wikipedia (as well as a few papers about cubical type theory and 2d type theory) talk about canonicity property. Would you please explain ...
28 views

### What is the worst case time-complexity of removing the root of a Binary Search Tree?

My answer is constant time O(1) since an implementation would naturally have the pointer to the root. However, the solution guide I am looking at argues it is O(logN).
20 views

### Safety property vs Liveness property

If i take a safety property $SP$ and a liveness property $LP$, is it true that the result of their intersection is a safety property (and not a liveness property) ? Why ? Thanks
46 views

### Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states

So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you ...
12 views

16 views

### Intuition Behind Moore's Law

I recently read a Quora Answer (The one by Richard Muller) by a reputed author who said that how Moore's Law still holds when people expected it to deviate and had given explanations as to why it ...
54 views

### Perfect Probabilistic Encryption still requires key length about as long as message

Let $(E,D)$ be a probabilistic encryption scheme with $n$-length keys (given a key $k$, we denote the corresponding encryption function by $E_k$) and $n+10$-length messages. Then, show that there ...
30 views

### What is the space complexity of the following procedure? [duplicate]

Please help me calculate the space complexity of the following program: int Sum(int A[ ], int n) { ...
25 views

### What is the running time of the following procedure? [duplicate]

Please help me calculate the time complexity of the following procedure. Power(n) 1:If n=0 then 2: return 1 3:else if 4: return Power(n-1) + Power(n-1) Explain ...
13 views

### What recursive T(N) function typically can conclude the algorithm is O(n ^ 2), O(n log n), O(n), and O(log n)?

Is it true that some common forms of recursive T(n) can give the following conclusions? When T(n) = T(n/c) + b where c is a constant > 1, b is any constant ...
18 views

### Unable to debug my code [closed]

Problem is MARCHA1 of Codecehf . HERE is link :https://www.codechef.com/problems/MARCHA1 IN SHORT I'LL SUMMARISE THE QUESTION : we are given n number of notes of any denominaton and m is required ...
14 views

### Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?

Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. This algorithm is theoretically interesting, but in practice ...
13 views

### How to prove of disprove the following Control Flow Graph theory

See the attached image for some background on Control Flow Graph In a single-entry, single-exit control flow graph (CFG), a node u post-lead v if every path from v to the exit includes 𝑢. Let q be ...
28 views

### Is optimizing from O(n log n) to O(n) considered to be premature optimization? [on hold]

For example, the 2-sum problem: given an array of N distinct numbers, find all possible pairs of numbers that add up to K. Sedgewick's Algorithm book seems to stop at O(n log n), while the "best" ...
8 views

### Graph with arboricity a, all verteces are marked active

So I came across this problem that I would like help solving/explaining: We have a graph with arboricity a (can be partitioned to a min of a trees). We run the following algorithm on the graph: - All ...
9 views

### Algorithmic question: distribute balls, optimise for balancing (i) weights (ii) probabilities of picking balls

I have an algorithmic problem that requires some lengthy explanation, which follows below. tl;dr: distribute balls with weights among bags, optimise for balancing both (i) the weights between the ...
34 views

### Solving/mitigating the free rider problem without requiring identification?

Is there any algorithm/protocol out there to solve/mitigate the free rider problem without requiring identification? In a web system, I want to distribute exactly one virtual dollar per day to each ...
37 views

### Are chatbots a good example of overfitting?

In my highschool class we are learning about Artificial Intelligence, and especially the problems that come with machine learning. I was wondering if chatbots like cleverbot were good examples of ...
16 views

### Construct an NFA over {0,1}* such that every string contain exactly two occurrence of 10

NFA is always a bit tricky than DFA atleast in the case of mine. Anyways, this problem seems easy but I just can't figure it out. I've tried it but the solution doesn't seem right.
7 views

### Complement of avoidable pattern

The definition of avoidable pattern is : An avoidable pattern is one for which there are infinitely many words no part of which match the pattern is it true to say that the complement of avoidable ...
25 views

### Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s

Design a Pushdown Automata, accepting either by final state or by empty stack to accept the set of all strings of 0’s and 1’s such that no prefix has more 1’s than 0’s This is a homework question,...
13 views

### Breadth-first traversal: difference between generation and expansion

The question here is to find a path from A(rad) to B(ucharest). I'll be using the initials of the cities in the picture instead of their full names. Some ground-rules: we're traversing in ...
34 views

### Time complexity of finding predecessor for a dictionary implemented as a sorted array

I'm currently reading "The Algorithm Design Manual" by Steven Skiena. On page 73, he discusses the time complexity of implementing $Predecessor(D, k)$ and $Successor(D, k)$ and suggests that it ...
17 views

### Python program not working accurately [closed]

First I wanna tell I am beginner and this is among my first program: def square_area(side): return (side * side) def rectangle_area(length, breadth): return (length * breadth) def ...
8 views

### AMAT using Local miss rate, global miss rate, local hit rate, global hit rate

Consider the following scenario as shown in image: I have summarized the above Memory layout in terms of Miss rates and hit rates: ...
72 views

### For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Traditionally, the traveling salesman problem has you visit a city at least once and at most once. However, if you were an actual traveling salesman, you would want the least cost route to visit each ...