# All Questions

31,853 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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. ...
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 ...
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: ...
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 ...
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 ...
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 , ...
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 ...
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.
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, ...
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 ...
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. ...
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?
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?
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 ...
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 ...
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 ...
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/...
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 ...
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 ...
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.?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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?...
12 views

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 ...
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 ...
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: ...
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....
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...