All Questions

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

What's an upper bound for this recurrence so I can take advantage of the Master Theorem?

Let $$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\varphi(N)) + 2T(\sqrt{N}) + \lg(\varphi(N))^3 & \text{otherwise} \end{cases}$$ where $\varphi(N)$ is Euler's totient function. My ...
1
vote
0answers
4 views

What is the biggest integer path in 2D array

You are given a board of N rows and M columns. Each field of the board contains single digit (0-9). You want to find a path consisting of four neighboring if they share a common side, Also the ...
0
votes
0answers
7 views

What is difference between r, and r(R) in DBMS?

Sorry, for asking such a basic question. I am really confused between small 'r' and 'r(R)' being interchangeably denoted as 'relation' or 'relational instance'. I know, that R is a relational schema. ...
1
vote
1answer
6 views

Doubt in definition of closure under concatenation operation in Recursive Enumerative languages

I recently started studying theory of computation. Recusive enumerable language – closed under concatenation. Sir, I have a doubt regarding understanding of this. Please Note - RE shortform i am ...
0
votes
0answers
6 views

Can Inductive Logic Programming problem be recast as Relational Reinforcement Learning problem?

Inductive Logic Programming problem is to find set of formulas H (hypothesis), that satisfy logical equations: ...
0
votes
0answers
7 views

Extracting a spanning tree from a directed acyclic graph with minimum total distance between terminal nodes

I have a directed acyclic graph that has uniform edge weights. I would like to extract from this graph a spanning tree (an arborescence) with the property that the total distance between all pairs of ...
0
votes
1answer
20 views

Difference between Quick sort, Merge sort and Heap sort

We know all the above-mentioned sorting algorithms take O(nlogn). Merge sort and Heap sort algorithms take O(nlogn) time in worst-case where Quicksort takes O(n^2). So what is the main difference ...
1
vote
1answer
20 views

Counting common values in two arrays

given two arrays of integers A and B of size m, with values in the range [-n,n]. I want an algorithm to count how many common values are in A and B , if a value is repeated we only count it once , ...
2
votes
0answers
13 views

Question about the lower bound for $k \times k$-clique (under ETH) shown in “Slightly Superexponential Parameterized Problems”

I am reading the paper Slightly Superexponential Parameterized Problems at the moment and have two questions about it: First question: The paper gives a proof of the following statement Theorem ...
2
votes
0answers
15 views

Calculus of constructions, type-in-type and recursion

Does adding type-in-type to the calculus of constructions lead to (general) recursion? Such that one can write the Y combinator.
1
vote
1answer
15 views

Ford Fulkerson maximum flow for all vertices

Suppose we have a graph $G(E,V)$ with a source node $s$. Now for any $t\in V \setminus s$ I can find the maximum flow from $s$ to all possible $t$ by using the Ford Fulkerson algorithm $|V|-1$ times, ...
0
votes
0answers
5 views

How to do Distributed Job Scheduling after the Leader was elected and slaves are known - (bully)

I'm building a system that processes key,value pairs on a continuous basis in a loop, until terminated. How do I schedule tasks on the leader and make slaves execute them? This is a realm of ...
0
votes
1answer
18 views

Asymptotic Analysis

Could someone explain the following question - Given the following statement viz. Consider an input array a[1..n] of arbitrary numbers. It is given that the array has only O(1) distinct elements. ...
-1
votes
0answers
13 views

GCC compared to Clang [on hold]

What are the similarities and differences between GCC and Clang? Why would say, most Linux distributions use GCC and Macs use Clang?
0
votes
0answers
14 views

Why can't$ x^{15}+x^{14}+1$ divide any error that are next to each other or up to 32768 bits

It can divide an error having error bits at position 1, 14 and 15, cant it?
0
votes
1answer
23 views

Number of Configurations of LBA(Linear Bounded Automaton)

The lemma is: Let $M$ be an LBA with $q$ states and $g$ symbols in the tape alphabet. There are exactly $qng^n$ distinct configurations of $M$ for a tape of length $n$. I want know why LBA has ...
2
votes
0answers
19 views

Equivalence of input-restricted and output-restricted deques

There is a question in Art of Computer Programming by Knuth which needs us to prove that input-restricted deques and output-restricted deques can form the same number of (and possibly individually ...
1
vote
1answer
25 views

Intuition behind this specific algorithm for time series

Going through the EPI book and I need some help understanding this part. There's a problem, 5.7, that deals with buying and selling twice over a single time-series in order to maximise profit. The ...
0
votes
0answers
19 views

Theory of Computation Resources

I'm currently taking the theory of computation at school. Some stuff covered makes sense, but some topics I feel like I'm missing the big picture. Is there an equivalent of theory of computation and/...
0
votes
1answer
20 views

Average branching factor of an undirected graph

I'm trying to determine, given an unweighted undirected graph, the maximum number of leaves of any travelling of the graph, which means, the maximum number of leaves among all traversals of every ...
0
votes
1answer
24 views

What is the Time and Space Complexity of the 3Sum problem with the following algorithm?

There was this problem that asked to return all unique triplets of elements of an array which add up to zero (swapping two elements' places in the triplet does not count as unique). I came up with ...
0
votes
0answers
26 views

If P = NP then EXPTIME = NEXPTIME?

Are the following implications correct? If P = NP then EXPTIME = NEXPTIME If P $\neq$ NP then NEXPTIME = 2EXPTIME If so would the corresponding implications hold for N2EXPTIME, etc.?
-1
votes
0answers
17 views

How to compare different Information Retrieval Methods?

I have an algorithm that takes an user's query and include relevant terms in it to expand it and get better results in document retrieval. Now, I have to write a paper about it in which i have to ...
0
votes
0answers
12 views

confusion with worst case for direct addressing

In CLRS there is an exercise for direct address table Suppose that a dynamic set S is represented by a direct-address table T of length m. Describe a procedure that finds the maximum element of ...
3
votes
1answer
28 views

Proof of sparsification lemma: What exactly does the $\pi$ operator do?

In their proof of the sparsification lemma, Impagliazzo et. al describe the following operator $\pi$: For a familiy of sets $\mathcal{F}$, let $\pi(\mathcal{F}) \subseteq \mathcal{F}$ be the family ...
0
votes
0answers
19 views

Computational power of machine learning

In a nut shell, machine learning is a class of algorithms that can "train" data-structures. You provide a trainer with partial information, and it will produce some entity which can be queried on ...
-2
votes
0answers
20 views

How to get developers to contribute my open source project (SIMD intructions, Numerics)? [on hold]

I have a project in my mind that I have been developing on github. It's a heavily optimized numeric library that helps you to do numerical operations without lack of performance. I contest with Intel ...
0
votes
1answer
13 views

Merge nodes in a graph to form a tree

I have an undirected graph which may have 2 edges that connect the same pair of nodes. A group of nodes that don't need any bridges to go from a node to another should be merged into one node in a ...
0
votes
1answer
25 views

Estimating the range of $1$'s in an array of $0$'s and $1$'s

I have a large array $A$ that contains something like $[0..1..0..]$. It has a continuous range of $0$'s, followed by a range of $1$'s, and then another range of $0$'s. This array is large and access ...
2
votes
0answers
18 views

The No-Free-Lunch Theorem and K-NN consistency

In computational learning, The NFL theorem states that there is no universal learner. For every learning algorithm , there is a distribution that causes the learner to output a hypotesis with a large ...
1
vote
3answers
85 views

Is finding a minimal set of seed variables for a complete deduction of a system of equations NP-complete?

Suppose we have a set of variables $V$. We also have a set of equations $E$, which are sets of at least two variables. We don't know anything about these equations, except if we know all but one of ...
0
votes
1answer
28 views

Is there an algorithm to share parts of strings?

Let's say that we have the strings Hello, World, Hello and World. The algorithm I am ...
-1
votes
1answer
37 views

Artificial intelligence - Theorem proving [on hold]

This is just to make the question long as it's not accepting, my only question is that among BFS and DFS which one is used for theorem proving?
0
votes
1answer
31 views

Is Binary search tree in 1D?

This post says Binary Space Partitioning Trees are a generalization to dimensions > 1 of binary search trees which indicates the binary search trees lives in 1d space. Is my understanding right?...
2
votes
1answer
12 views

Computing epsilon-closure. What does $E(n) \leftarrow \{n\};$ and $E(p)$ mean?

I'm currently reading "Engineering a Compiler" book. In the chapter that explanes computing epsilon-closure there is listed the following algorithm: But I couldn't understand what does $E(n)$ and $E(...
0
votes
0answers
13 views

Check which interval range does a number lie in between

I have an array of time variables t(1), t(2), ..., t(n). and corresponding variables v(1), v(2), ..., v(n). Given a time ...
2
votes
1answer
36 views

Could I apply the master theorem if my $N/b$ is $\varphi(N)$?

Let $$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\varphi(N)) + \lg(\varphi(N))^3 & \text{otherwise} \end{cases}$$ where $\varphi(N)$ is Euler's totient function. Can I somehow express $\...
0
votes
0answers
17 views

Create automata from non regular grammar

I have two grammars: L → ε | aLcLc L → ε | aLcLc | LL This two grammars are equals but the first one is regular, so it produces a regular language and a ...
-2
votes
0answers
12 views

Resolving windows 7 resume [on hold]

I have a windows 7 desktop. Today when I tried to start it. A black screen appeared. With option 1) continue with resume data 2)delete restoration data and proceed to system boot menu But the ...
0
votes
0answers
7 views

What is the average time for a node to transmit on the shared medium for Ethernet? (IEEE 802.3)

Suppose a shared ethernet link L, in which for nodes T1-T4 and a router R are connected: ...
3
votes
1answer
46 views

Linear programs with strict inequalities and supremum objectives

Linear programming can solve only problems with weak inequalities, such as "maximize $c x$ such that $A x \leq b$". This makes sense, since problems with strict inequality often do not have a solution....
0
votes
1answer
9 views

Weighted graph clustering with maximum size constraint

I'm currently trying to solve a clustering problem. I need to cluster/partition an undirected weighted graph into groups that are restricted to size n. I have ...
3
votes
1answer
190 views

Basic Theta-notation question

Let $T$ be a function. Is it true that if $\exists f\forall n,m> 0.\\ \frac m {f(n)} \leq T(n,m)\leq m$ Then $\exists g.T(n,m)=\Theta(m\cdot g(n))$? In words: is such a case, is there a function ...
0
votes
0answers
8 views

Maximum space consumption of stack and queue for DFS and BFS

I'm trying to determine the maximum memory consumption of the "pending nodes" data structure (stack/queue) for both travelings: BFS and (preorder) DFS. Since BFS and DFS while traveling graphs have ...
1
vote
0answers
30 views

Algorithms of placing N weighted balls into M uniform bins while striving for balanced weight?

Suppose there're $N$ weighted balls and $M$ equal weight bins, it's guaranteed at least one placement exists that all the balls can be placed into bins. What's the right algorithm to achieve a well-...
0
votes
2answers
30 views

How can the initial “booting” state of a computer be different at different time points? [on hold]

In my experience, sometimes a computer boots normally, and in a time span of days, the computer won't boot, then again, it will boot normally again. I am not a computer science expert so I assume that ...
2
votes
2answers
55 views

Sliding Window Dictionary String Matching

Consider the following problem. We are given a set of patterns (strings) $\Pi = \{\pi_i\}$, a text $s$, and a window length $k$. We want a list of all shifts $0 \le i \le |s|-k$ such that every ...
1
vote
2answers
66 views

How do web browsers find out the MAC address?

While reading through my textbook, I discovered that if you want to access a particular web page, your web browser will find out the IP address of the web server that hosts the web page and try and ...
0
votes
0answers
30 views

How do you derive a type $∃e(e)$ in terms of universally quantified types, without invoking Void initially?

I wrote a "proof" for this, and though it was enough to convince myself, there are a few things that bother me about it. Primarily I'm not sure about the loose way in which I'm swapping between first-...
0
votes
1answer
25 views

Why does arithmetic left shift of negative number leads to positive number?

According to this Wikipedia article, when arithmetic left shift operation is applied to a signed number, the number is multiplied by 2. But there are certain situations where a negative number becomes ...

15 30 50 per page