# All Questions

31,823 questions
Filter by
Sorted by
Tagged with
1answer
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", "...
0answers
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 ...
1answer
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 ...
1answer
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
1answer
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 ...
1answer
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).
0answers
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
1answer
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 ...
0answers
12 views

0answers
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 ...
1answer
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 ...
0answers
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) { ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
1answer
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 ...
0answers
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 ...
0answers
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" ...
0answers
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 ...
0answers
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 ...
1answer
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 ...
1answer
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 ...
0answers
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.
0answers
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 ...
1answer
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,...
0answers
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 ...
2answers
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 ...
0answers
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 ...
0answers
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: ...
2answers
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 ...
1answer
36 views

### What is a 'dynamic entity' in computer science?

I am doing some reading into computer science and how the computing system works in order to be ready for my 1st year at university doing a Computer Science degree. I came across a term within the ...
0answers
27 views

### Linked List implementation with Priority Queue [closed]

If priority queue can implement a stack, why a linked list cannot implement with priority queue??

15 30 50 per page