1. All Categories
2. Computer Science

# Computer Science : Recent Questions and Answers

## Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1?

I'm interested in creating a graphs whose vertices are strings, and whose edges represent the relation of having an edit distance of 1 under a given string metric. An obvious...

## I'ld like a better algorithm for scheduling tutors to fill a set of shifts

My problem is as follows:I have a set of shifts at various locations that need to be filled by tutors. A simple example would be basic math in room...

## If $Ain RE$ then $f(A)in RE$

Let $Ain RE$, and define$f(A) = {y | y= f(x), xin A}$ for some computable function $f$. Then $f(A)in RE$. I can't figure out why this...

## reduction of independence problem and cluster problem

independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them. cluster problem...

## How is CPU different from GPU?

A central processing unit offers to handle various operations like calculating, watching movies, making presentation etc. While a graphics processing unit is majorly used for the purpose of video rendering or playing...

Asked on 12/31/2021 by Tejal Barnwal

## Mathematical limits on lossless data compression

Let's say Bob wants to send a particular binary sequence to Alice. Imagine that Bob and Alice both have powerful machines but slow Internet connections. Bob could just send the...

## Rice's Theorem for Turing machine with fixed output

So I was supposed to prove with the help of Rice's Theorem whether the language:$L_{5} = {w in {0,1}^{*}|forall x in {0,1}^{*}, M_{w}(w) =x}$ is decidable. First of...

## What is the significance of negative weight edges in a graph?

I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles....

## How can I create 10-character, unique codes with no collisions, but without being predictable?

If we are using numbers and letters, there are $36^{10}$ unique combinations. Collision is already unlikely, but I need it to be impossible, so using hashing is out of...

## What is the upper and lower bound for $T(n) = T(sqrt{n}) +3$, assuming that $T(n)$ is a constant for $nleq 10$

By unrolling the recursion,begin{equation*}begin{split} T(n) &= T(sqrt{n}) + 3 = T(n^{frac{1}{2}}) + 3 \ &= (T(n^{frac{1}{4}})+3) +3 = T(n^{frac{1}{4}})...