ANONYMOUS wrote:

Hi, the lecture covering the DP to find all hamiltonian cycles included bitmasking for states of the DP. I was unaware of bitmasking until recently researching on it, if we have a question in the exam where there is a similar answer to hamiltonian cycle DP required, are we able to simply say the states are subsets of a set rather than the mask? I don't really understand bitmasking fully so sorry if this doesn't make that much sense. Cheers

A bitset is an implementation detail to represent sets efficiently in memory. I cannot make an explicit statement about the content of the exam, and so cannot tell you whether you will need to be familiar with this, but I believe from the format of the sample exam you should be able to make your own judgement on what you may or may not need to understand.

Having said that: Bitsets are pretty simple. An element is either in the set or it is not. This is a binary choice and can be represented by a single boolean. For some known "universe" of possible elements, we can therefore just assign each element an integer id 0, 1, 2, etc., and we can represent a subset of these elements as a list of booleans recording whether each element is in the set. So [True, False, True, True] would represent the set {0, 2, 3}. Bitsets just allow us to represent (small) lists of booleans more efficiently: Using each bit of a 64-bit integer (for example) as a boolean means we can represent a list of 64 booleans using a single integer. The operations to then manipulate the elements of this list are then just however the language you are using implements bitwise operations to read or write individual bits. That is an implementation detail that just requires you to be familiar with the language's operations.

We like this because it lets us use a single integer to represent a set that would otherwise be a much larger more complex object. In particular, and the reason I used it in that lecture, is it means you can just use the integer directly as an index into a list. Meanwhile if we were using actual set objects, Python doesn't even let you use them as keys in a dictionary because sets aren't hashable by default to avoid Problems, so you would have to juggle using frozenset instead, and all this is going to come with an O(N) overhead. Computers love working with integers though. It's basically all they do.

Notably, the size of a bitset is not proportional to the number of elements it contains, but to the size of the universe of elements it could possibly contain, so it's only really useful when we know the universe is small.

Note also that since Python integers can grow arbitrarily large, you are not limited to 64 bits, but above 64 bits Python starts using a much more complex big integer representation that has its own complications. Generally this should not matter, though, as by that point you are talking about representing more than 2^64 subsets, so your time complexity probably has bigger problems.

Hopefully that helps you understand the computational properties of working with sets, and helps you see that bitsets are mostly just an implementation detail of how we actually represent the concept of a set.

Cheers, Gozz