ilyaraz's blog

By ilyaraz, history, 9 years ago, In English

Hi all,

Can you help me test our implementation of the Fast Hadamard Transform? It will take you a couple of minutes provided that you have modern enough C and C++ compilers. I'm especially interested in testing it under OS X and 32-bit systems.

You would need to have gcc that would compile C99 and g++ that would compile C++11. Also, you would need make to build everything.

What you need to do:

  1. Tell me your OS and CPU.
  2. Download the code from http://ilyaraz.org/fht.zip and unzip.
  3. Run "make", tell me if something does not compile.
  4. Run "test", make sure it does not fail. Tell me, if it fails.
  5. Run "best_chunk" with n = 1024, 1048576, 134217728 and send me the outputs.

Thanks! Ilya

Full text and comments »

  • Vote: I like it
  • +45
  • Vote: I do not like it

By ilyaraz, history, 9 years ago, In English

Hi all,

I'm about to teach AVL trees for a section of 6.006, and while thinking it through, I came up with the following question, which, I strongly suspect, should be well-understood.

Say one wants to maintain a binary search tree with height , where n is the total number of nodes, under insertions. How quickly can one insert? Is time per insert possible?

For instance, AVL trees achieve height around and red-black trees — .

What do you think?

Full text and comments »

  • Vote: I like it
  • +37
  • Vote: I do not like it

By ilyaraz, 11 years ago, In English

Hi everyone!

We have just started a student blog of MIT Theory of Computation Group. If you are curious to read or gossip about "real" research in Theoretical Computer Science or life of graduate students, feel free to sign up!

The blog is run by:

Full text and comments »

  • Vote: I like it
  • +73
  • Vote: I do not like it