The tag has no wiki summary.

learn more… | top users | synonyms

-1
votes
1answer
20 views

Why do I not get the correct smallest possible value in 2's complement?

When using 2's complement with 4 bits, the largest positive int I can represent is 0111. The smallest negative one is 1000. The smallest int should intuitively be the negative of 0111 - 1 = 0110 ...
2
votes
1answer
36 views

A string representation of any Turing machine

The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble ...
0
votes
1answer
77 views

Precise definition of term: *schema*

Does the term schema, in the context of describing a structure, refer to the actual structure of the data, or the description of this structure? I.e. can I talk about the schema of an entity without a ...
10
votes
1answer
172 views

How do I find the shortest representation for a subset of a powerset?

I'm looking for an efficient algorithm for the following problem or a proof of NP-hardness. Let $\Sigma$ be a set and $A\subseteq\mathcal{P}(\Sigma)$ a set of subsets of $\Sigma$. Find a sequence ...
2
votes
1answer
80 views

Encoding algorithms better than or equivalent to Run Length Encoding

I have a table in which some values are repeated often as shown in the figure below. I want to encode that table such that it makes use of less memory. I have heard about run length encoding (RLE) but ...
-2
votes
2answers
135 views

Finding the difference between two number in a sorted list using divide-and-conquer

How to find the smallest difference between two numbers in a sorted list using divide-and-conquer approach? For example, ...
-1
votes
1answer
176 views

Decoding a binary message with LZW dictionary

I have the following exam question for a multimedia exam in college and I have absolutely no idea where to start. I know how the decoder algorithm should work but I have no idea how to do it on ...
2
votes
2answers
113 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
3answers
738 views

What are two's complement integers?

Can someone explain in plain English what "two's complement integer" means? I read this: in Java long is a 64-bit signed two's complement integer
2
votes
3answers
162 views

Reconstructing files from binary

Popular view tells us that any kind of information is just a collection of bits, that is zeroes and ones placed in a particular order. I was thus having this thought. Suppose that I have some kind of ...
0
votes
1answer
301 views

Jamming signal useless in CSMA / CD?

I'm looking at collision detection in communication protocols, in particular Carrier sense multiple access with collision detection (CSMA/CD). According to what I've read on Wikipedia, a collision ...
3
votes
1answer
117 views

Polynomially related lengths under two different encodings

I'm reading through "Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20 and I came across this ...