Problem 5: Sorting Flashcards 15 points The sixth grade science teacher is helping the students learn some important science terms. She's had them write the terms on the cards. To make the learning more manageable, the class is working through all of the terms based on their first letter (they learn all of the words that start with 'A', then 'B', and so on. After 26 days, they're done learning all of the words. To get the card decks organized again, we want to sort them so that each student's deck has the cards in alphabetical order. For simplicity, let's assume that we have k flash cards for every letter of the alphabet (we have n flashcards in total). woefully out of order. Eventually, we want to design an optimal algorithm for getting all n flashcards in order (a) [10 points] First, prove a (n log k) lower bound on the number of comparisons needed to solve the problem of generating a full sorted deck of vocabulary flash cards for a given student. (Hint: In case you haven't memorized them, you may need to use the following facts: log(k!)-(k log k) and log ab-blog a.) (Another hint: while it is true that n = 26k. it's probably easier to ignore that and think of the problem generically in terms of n and k.) b) 5 points| Now, design an optimal algorithm for sorting a single student's deck of flashcards Briefly justify the runtime of your algorithm Problem 5: Sorting Flashcards 15 points The sixth grade science teacher is helping the students learn some important science terms. She's had them write the terms on the cards. To make the learning more manageable, the class is working through all of the terms based on their first letter (they learn all of the words that start with 'A', then 'B', and so on. After 26 days, they're done learning all of the words. To get the card decks organized again, we want to sort them so that each student's deck has the cards in alphabetical order. For simplicity, let's assume that we have k flash cards for every letter of the alphabet (we have n flashcards in total). woefully out of order. Eventually, we want to design an optimal algorithm for getting all n flashcards in order (a) [10 points] First, prove a (n log k) lower bound on the number of comparisons needed to solve the problem of generating a full sorted deck of vocabulary flash cards for a given student. (Hint: In case you haven't memorized them, you may need to use the following facts: log(k!)-(k log k) and log ab-blog a.) (Another hint: while it is true that n = 26k. it's probably easier to ignore that and think of the problem generically in terms of n and k.) b) 5 points| Now, design an optimal algorithm for sorting a single student's deck of flashcards Briefly justify the runtime of your algorithm
