All Questions

Filter by
Sorted by
Tagged with
0
votes
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", "...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
3
votes
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 ...
1
vote
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 ...
4
votes
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 ...
1
vote
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).
0
votes
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
1
vote
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 ...
1
vote
0answers
12 views

Definition of liveness property in model checking

A property $P$ is simply a set of sequences of states and a certain program is characterized by its set of sequences of states, let's call it $T$. A program is compliant to a specific property P if $T\...
-2
votes
0answers
28 views

C programming : Stackoverflow is a cause of abrupt termination [on hold]

In case of stack overflow in C programming, why do we tell it abrupt termination of loop. Shack-overflow is not a cause of infinite looping. But causing abrupt termination, though we cannot see, ...
0
votes
2answers
38 views

What makes a common programming language non-context-sensitive but RE?

I have a vague understanding that a (sane) programming language is RE as they are Turing-complete, being able to describe any Turing machine. But I cannot pinpoint what aspect makes a programming ...
-4
votes
0answers
8 views

python programming [on hold]

please anyone help with this python code : You are provided with the number of rows (R) and columns (C). Your task is to generate the matrix having R rows and C columns such that all the numbers are ...
0
votes
0answers
37 views

Algorithm for partitioning connected paths in an Array of 0s and 1s

I am trying to create a lattice and create random connections and I want to calculate the number of points in a connected component. I am starting at the origin of lattice and I am trying to add the ...
0
votes
0answers
8 views

What is the difference between Instance of a relation and Instance of a relation schema?

Following question was asked in the exam. The correct answer to this question is 2. But, I feel that it is a wrong answer. Option 2 is an example of instance of a relation and not an example of ...
0
votes
0answers
27 views

A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$

I read some computation theory lecture notes and after citing and proving the proposition: $\emptyset \in S \Rightarrow L_S = \{\langle M \rangle : L(M)\in S\} \notin RE$ it says that $\emptyset\in S$ ...
-3
votes
0answers
24 views

Number of swaps and comparisons in sorting algorithms [on hold]

i was reading the comparison algorithms(bubble,insertion and selection). i followed this linklink1,but if someone asks what is the number of comparison and swap in these algorithms, what should i say ?...
-3
votes
0answers
16 views

From Harris's “DDandCA” book [on hold]

Does it mean that 2^n-1 and 2^(n-1)-1 are the same things?
0
votes
1answer
20 views

Binary Search Symbol Table

Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across the following problem: ...
-1
votes
0answers
19 views

How to know a specific coordinate on Google maps is in a road or a building? [on hold]

Is it possible to know if a specific coordinate is located in road or a building? For example, if I take this coordinate 52.5047252, 13.3569516 do I need to type it on Google and verify it's position ...
0
votes
0answers
14 views

Recurrence Formula for Bitonic Sorter Runtime

A Bitonic sorter takes a bitonic sequence as an input and the output is a sorted list. I want to analyse Bitonic Sorter by knowing its depth/runtime. Can anyone give an idea on its recurreence formula?...
0
votes
2answers
19 views

How to do a reverse topological sort using depth first search?

I'm doing a replacement for the venerable make utility that will support, among other things, automatic cleaning. The utility figures out automatically what files ...
-2
votes
0answers
11 views

How to count this Conditional Probability [on hold]

Iam not good in math, especially for conditional probabilities please help me for this : How do you count to get the values in the table?
0
votes
1answer
48 views

Are every problems in EXP karp reducible to any EXP-Complete?

According to wikipedia and other references there exists complete language $L \in EXP$ such that for every languages $L'$ in $EXP$ there exists a polynomial reduction $f$ that converts instance of $L'$...
0
votes
0answers
21 views

Efficient method of representing bijections

Let's say I have to map the elements $\{1,2,3,4,5\}$ to $\{a,b,c,d,e\}$ as follows. $\{ \space \{\space(1,a) , (2,b) , (3,c)\space\} \space , \space \{\space(1,a) , (2,c) , (3,b)\space \} \space \} \...
0
votes
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 ...
4
votes
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 ...
-3
votes
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) { ...
-2
votes
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 ...
-1
votes
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 ...
-3
votes
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 ...
0
votes
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 ...
-1
votes
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 ...
-1
votes
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" ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
-1
votes
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.
0
votes
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 ...
0
votes
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,...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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: ...
2
votes
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 ...
0
votes
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 ...
-1
votes
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