All Questions

Filter by
Sorted by
Tagged with
2
votes
2answers
413 views

Proving that finding wheel subgraphs is NP-complete

Can you help me with this problem ? Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ ...
4
votes
1answer
5k views

Shortest path with exactly $k$ edges

From Skiena's book The Algorithm Design Manual, chapter 6, problem 22: Let $G = (V,E,w)$ be a directed weighted graph such that all the weights are positive. Let $v$ and $u$ be two vertices in $G$ ...
8
votes
5answers
10k views

How to tell if a language is recognizable, co-recognizable or decidable?

If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable? Basically any hints or tricks that can be used to tell. Or maybe the ...
1
vote
2answers
134 views

How to distinguish empty cells from cells outside of the input cells?

Setup I need to develop a Turing Machine that accepts a string m that has the same number of a's and b's. My alphabet is {a,b}, and we use a diamond in class to represent an empty space. Problem ...
0
votes
3answers
13k views

Internal and External Fragmentation [closed]

I am working over a homework problem and am confused on how to determine whether there is internal and external fragmentation given the following table: ...
4
votes
1answer
177 views

Computing number of block reads given relational algebra statement

So I'm just starting to learn about query processing and such in databases and I'm having some trouble. I don't really understand how to compute the minimum number of block reads given a relation and ...
3
votes
1answer
649 views

Identifying an object in an image based on color (AI ?)

First off, I am not sure if this is the correct stackexchange site to ask this question on, so moderators can feel free to move it. I am working on an application that identifies an object in an ...
2
votes
1answer
724 views

The List functor

I have been reading some notes on Category Theory. One question that is posed is to verify the definition of $\operatorname{List}$ is a functor... $\operatorname{List}(g \circ f) = (\operatorname{...
1
vote
0answers
91 views

Terminology for vertices in graph connecting vertices “in” and “outside of” a given component

Basically, I am looking for a (well-defined) term for some "borderline" vertexes interconnecting other vertices in and outside of a given connected component. More specifically, given directed graph $...
0
votes
1answer
2k views

Algorithm to determine if a number is perfect on a Turing Machine

I've been trying for a while now to find a solution for the problem in the title: determining if a number is perfect using a Turing Machine. I only had one class on the TM and while I did "get" how it ...
2
votes
2answers
422 views

Show the problem of a machine visiting infinitely many tape cells on some input is undecidable

I am attempting to prove the following problem is undecidable. Given a Turing machine $M$ and input $x$, does $M$ visit infinitely many tape cells on input $x$? I am considering a reduction from the ...
8
votes
5answers
13k views

Are all Integer Linear Programming problems NP-Hard?

As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
3
votes
4answers
3k views

The difference between a bit and a Qubit

Ok, I have done a lot of research on Quantum computers. I understand that they are possibly the future of computers and may be commonplace in approximately 30-50 years time. I know that a Binary is ...
1
vote
0answers
120 views

LInear time algorithm to find the diameter of a tree [duplicate]

This is NOT HW, this is from Skienas book, and I just couldn't solve it at all. Please give me a hand here, in understanding and solving it, thanks. Let G = (V, E) be a binary tree. The distance ...
2
votes
2answers
2k views

Is there a difference between pure binary and binary?

In some books and on the internet I occasionally find "pure binary" and "binary" on its own, is there a difference between these two terms? If so, can someone describe briefly what they are?
1
vote
1answer
91 views

Prove NP-completeness of deciding whether there is an edge-tour of at most a given length

We are given a graph G, integer b < |E|, and subset F in E. The problem is to detect whether there is a cycle in the graph with length at most b and includes each edge in F. Prove that this is NP ...
3
votes
1answer
244 views

How to distinguish between the different frequency domains?

Sometimes the terms 'Fourier domain', 'complex frequency domain', 'Frequency domain' and 's domain' are used interchangeably. Take these answers here for example. Can you really use them ...
82
votes
2answers
58k views

Quicksort Partitioning: Hoare vs. Lomuto

There are two quicksort partition methods mentioned in Cormen: ...
4
votes
1answer
123 views

NP hardness through Restriction

Let's say I have a decision problem $P$ on graphs for which I know that it is NP-hard on graphs with maximum degree $d$. Does this then imply that it is NP-hard on $d$-regular graphs? Although it ...
10
votes
1answer
913 views

Pebbling Problem

Pebbling is a solitaire game played on an undirected graph $G$ , where each vertex has zero or more pebbles. A single pebbling move consists of removing two pebbles from a vertex $v$ and adding ...
2
votes
2answers
3k views

Converting CFG to PDA

I have the following CFG, $S \rightarrow CB$ $C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$ $B \rightarrow AB \text{ }|\text{ } \varepsilon$ $A \rightarrow a\text{ }|\text{ }b$ ...
6
votes
3answers
16k views

Why does DFS only yield tree and back edges on undirected, connected graphs?

Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge. Now, from intuition and in class lectures by Steven Skiena, I know ...
2
votes
1answer
187 views

Negative lookahead in LR parsing algorithm

Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.): Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ; ...
10
votes
2answers
1k views

What makes lambda calculus relevant to study?

I'm starting an undergraduate computer science course next fall, but I can't really understand λ-calculus in the context of functional programming. I may be misinterpreting this completely, but based ...
1
vote
1answer
490 views

Bellman-Ford parent pointer (?) negative cycle

First of all, let me preface by saying that this question is not completly new but the original question hasn't been answered. More important, this is only basic question on understanding the proof ...
5
votes
1answer
615 views

Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves

This problem is about finding a route on a square grid. The starting point is $(1,1)$ and the target point $(n,m)$. I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$. ...
4
votes
2answers
871 views

Parallel Computing: Past Vs Present

Parallel computing is not new but it is becoming common now a days. This is essentially driven by the need of the users (they need to process more data now) and also because of physical limitations on ...
6
votes
1answer
261 views

Time Complexity of a selection problem

I wonder what's the time complexity of the following selection problem I found while thinking of a string-matching problem. [Assuming operations on integers take $O(1)$ time] We are Given $m$ sets, ...
6
votes
2answers
3k views

Best problems that are prone to parallelization?

What are some problems that are prone to parallelization? When I think about this, the first thing that comes to my mind is matrix multiplication, which yields to faster calculations, meaning you can ...
14
votes
1answer
2k views

FFT-less $O(n\log n)$ algorithm for pairwise sums

Suppose we are given $n$ distinct integers $a_1, a_2, \dots, a_n$, such that $0 \le a_i \le kn$ for some constant $k \gt 0$, and for all $i$. We are interested in finding the counts of all the ...
2
votes
1answer
27k views

How to perform bottom-up construction of heaps?

What are the steps to perform bottom-up heap construction on a short sequence, like 1, 6, 7, 2, 4? At this link there are instructions on how to do for a list of ...
4
votes
1answer
2k views

What is the difference between the semantic and syntactic views of function types?

Edit: My original question referred to nonconstructive and constructive definitions of function types. I changed the terminology in the question and the title to semantic and syntactic, which the ...
4
votes
1answer
3k views

Proving ALLTM complement not recognizable

A few definitions.. $$ \begin{align*} \mathrm{ALL}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) = \{0,1\}^{*} \Bigr\} \\[2ex] \...
4
votes
1answer
206 views

Asymptotic bounds on number of 3SAT formulas with unique solutions

A set is sparse if it contains polynomially bounded number of strings of any given string length $n$ otherwise it is dense. All known NP-complete sets are dense. It was proven that P=NP if and only if ...
1
vote
1answer
1k views

What is Pointer Jumping ?

Studying parallel algorithms for CLRS, old edition Chapter 30. Can some one explain with a simple example what is pointer jumping and how exactly it works ?
3
votes
3answers
1k views

Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?

Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free ? If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \ j\neq ki \} $ is ...
1
vote
1answer
1k views

Set cover problem and the existence of such cover

In the set cover problem we want to find in the $\mathbb{S} \subset 2^\mathbb{U}$ the subset $\{s_i\}_{1..k}$, such that $\cup s_i = \mathbb{U}$ for given $K$, where $k \le K$. But how to reduce the ...
6
votes
4answers
3k views

Solving system of linear inequalities

I am trying to solve a system of inequalities in the following form: $\ x_i - x_j \leq w $ I know these inequalities can be solved using Bellman-Ford algorithm. ...
5
votes
1answer
241 views

How does the problem of having a coffee-machine close relate to vertex cover?

Meeting rooms on university campuses may or may not contain coffee machines. We would like to ensure that every meeting room either has a coffee machine or is close enough to a meeting room that ...
4
votes
2answers
529 views

Introduction to complexity and computability

I'm looking for a good book that explains these subjects in a readable way. Any suggestions ? I currently pursuing my BSC in computer science, and I just failed to pass the course introduction to thr ...
2
votes
3answers
2k views

Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0?

In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph ...
0
votes
1answer
58 views

Why isn't set $\{ \langle i, j \rangle \mid W_i = \overline{W_j}\}$ a recursively enumerated set?

Why isn't the set $\{ \langle i, j \rangle \mid W_i = \overline W_j\}$ a r.e. set? Note: $W_x = L(M_x)$
4
votes
1answer
691 views

Are there a lambda-mu expression equivalent to the yin yang puzzle?

The yin yang puzzle was written in Scheme. Since it uses call/cc, it is not possible to express it in a pure lambda expression, unless we do a CPS transform. However, given the fact that $\lambda \mu$...
4
votes
1answer
698 views

Prove that the Language is Recognizable

I got stuck on this question while studying for final exam. I thought about reducing L' to L to prove that L' is recognizable since L is recognizable. I am not 100% sure if that is correct.
4
votes
2answers
470 views

From Whence the Randomization in Randomized Quicksort

Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph): Using a random number generator to choose the positions is ...
1
vote
0answers
48 views

Is it possible to discern the quality of web data from networks derived from it?

One topic I've recently looked at is co-occurence networks formed from Twitter tweets. This is how I felt after looking at the tweets of random people: This leads me to the question: Question: Is ...
5
votes
2answers
277 views

Is a language with only a stack of fixed-size integers Turing-complete?

I encountered the brainfuck programming language which I know is turing complete. However I then decided to create a high level language that gets compiled to brainfuck code. There is only one data ...
3
votes
1answer
2k views

FFT implementation using Danielson-Lanczos Lemma

I am trying to understand FFT algorithm explained here ...
6
votes
4answers
13k views

Explaining why FFT is faster than DFT for the general public?

How would you explain why the Fast Fourier Transform is faster than the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?
1
vote
1answer
113 views

How to sample uniformly from a stream of elements, some of which are unsuited?

I get values $x_t$ in an online fashion and want to buy "good" ones, where "good" means that some measure $P(x_t) >T$. Consider the following simple algorithm. ...

15 30 50 per page