The question: https://www.cs.princeton.edu/courses/archive/spring03/cs226/assignments/password.html

Input files: ftp://ftp.cs.princeton.edu/pub/cs226/password/

The question asks to use a symbol table for faster decryption. The implementation of symbol table can be either using hash table or BST. I am pretty sure we have to use a hash table as each element in the table can contain linked lists for sums that can be obtained using every subset. There are 5c possible subsets (given in the txt file) and 2^(5c) possible ways of adding these subsets.

I am not sure if this is efficient enough. The linked lists will be extremely toward the top of table and get exponentially smaller (by power of 2) toward the bottom. Lookup time will definetely not be constant.

This question is part of the creative assignments released by Princeton from their COS226 course. The links are given above.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.