Answer each problem in one or two sentences.

problem 1) Compare and contrast hash tables with random access tables, when used as the dictionary data structure.

problem 2) Compare and contrast a binary search tree with the sorted array when used as the dictionary data structure.

problem 3) Compare and contrast hash tables with binary search trees, when used as the dictionary data structure.

problem 4) Compare and contrast Hash Tables with Array-Based Lists, when used as the dictionary data structure.

problem 5) Describe the major differences between Random Access Table and Hash Table.

problem 6) Compare and contrast Linked Lists with Array-Based lists, when used as the sequence data structure.

problem 7) For each problem below, describe which data structure is best for solving the problem, and describe why.

a) In many video games you require to simulate shuffling of a deck of cards. Let’s suppose that deck of cards is represented using the List abstract data type. Which List data structure will be best for representing the deck, a linked list or an array-based list? Describe your reasoning.

b) You are implementing a simple spell checker, based on a data structure full of all English words. Your spellchecker takes words as input. If the word is correctly spelled, you return the word unchanged. If the word is not in your data structure, you are to return the word in the list that comes next alphabetically. For ex, if I use the word “foocz” you will probably return “food”. Will it be best to use the array-based list sorted alphabetically, a hash table, or a binary search tree? Describe your reasoning.

c) You work for a gym that has lockers, numbered 1 up to 1000. The manager of the gym would like a data structure that allows you to, given a locker number, look up who the locker belongs to. Such as, the input will be “15” and then your data structure might return “Bob Bobson.” What data structure would be better for this: A Hash Table or a Random Access Table? Describe your reasoning.

d) You are planning to create the text-editor (like Notepad or TextEdit). You wish to represent file as a list of characters, and you wish the user to be able to move their cursor anywhere in the file, and edit the file at that point. The files being edited might be very long, for ex 10 million characters long. Should you use an array-based list or a linked-list? Describe your reasoning.