# All Questions

31,820 questions
Filter by
Sorted by
Tagged with
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$ ...
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$ ...
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 ...
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 ...
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: ...
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 ...
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 ...
724 views

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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
58k views

### Quicksort Partitioning: Hoare vs. Lomuto

There are two quicksort partition methods mentioned in Cormen: ...
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 ...
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 ...
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$ ...
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 ...
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 ; ...
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 ...
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 ...
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)$. ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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] \...
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 ...
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 ?
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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)$
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$...
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.
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 ...
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 ...
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 ...
2k views

### FFT implementation using Danielson-Lanczos Lemma

I am trying to understand FFT algorithm explained here ...
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. ...