Main homework topics:
Welcome to training for the People in Black Suits (PIBS), no relation to Mr. Pibb. PIBS is a secret government organization whose true mission is.. well, we can't really tell you yet. Before you can become an official agent of PIBS and know the true purpose of this organization, you must carry out a mission.
Your training mission (if you choose to accept it, and we suggest that you do):
Before we can let you out on the field, we need to verify your skills.
You see, the only thing that can save this world is mad-scheme skills.
So, show us your tail recursion skills!
(Note: For the first two problems, the same restrictions given in hw1 still apply.)
Problem 1: On the last homework, we asked you to write sum-between, which, given two integers, returns the sum of those two integers as well as all the integers inbetween. However, this time, you need to do so tail-recursively. And, yes, you may still assume the first integer is less than or equal to the second integer.
(sum-between 2 5) -> 14
(sum-between 2 2) -> 2
Problem 2: Our leader, Agent K, has but one weakness: anime. He can only watch so much anime before he breaks (especially if it's Dragonball Z). The amount of anime Agent K can watch on day n before he breaks is represented by the equation anime(n) = n + anime(n-1). On the first day, it takes only one episode to break him (so, anime(1) = 1).
(anime 1) -> 1
(anime 3) -> 6
Unforunately, we have to cut short your training and go straight to the field work. Why? Our leader, Agent K, has been taken hostage by pirates and forced to watch anime! Your mission is to free our hairless leader (and then, if you like, to watch the anime).
Are you ready to rescue Agent K? Your mission will revolve mainly around lists, and you need to do all your work augumentive recursively: for you see, these pirates have tail-recursion alarms! Also, the only list functions you can use are cons, car, cdr, and null?. Using any other list functions will set off the pirates' alarms, trapping you into the horrible hall of zero!
Problem 3: Unfortunately, we're not sure where the pirates are. We have separate pieces of directions, and you need to put them back together. Scheme provides a function called append, but, without our fearless leader, it needs to be done manually. So write a function called my-append, that takes two lists and combines them into one.
(my-append '(a b) '(c d)) -> (a b c d)
(my-append '(a b) '()) -> (a b)
(my-append '() '(c d)) -> (c d)
(my-append '() '()) -> ()
Problem 4: We've found the pirates lair, but unfortunately there's more than one ship. We know which ship Agent K is on, and fortunately enough, there's a nice big directory of which ship is parked in which dock. Write a function called my-assoc, which takes a symbol and a list of lists: each inner list contains two or more elements, the first being a key. Given a key, return the list that begins with that key. If no such list exists, return #f.
(my-assoc 'a '((c d) (a b) (e f))) -> (a b)
(my-assoc 'c '((c d) (a b) (e f))) -> (c d)
(my-assoc 'e '((c d) (a b) (e f))) -> (e f)
(my-assoc 'd '((c d) (a b) (e f))) -> #f
Problem 5: We arrived on the ship, and there are a lot of pirates. The pirates, being in a list and not in a set, are very order based. If you turn them all around, they will become disoriented, allowing you just enough time to get to Agent K! Write a function called my-esrever, which given a list, returns a new list that contains the same elements as the first list, but in the opposite order.
(my-esrever '(a b c)) -> (c b a)
(my-esrever '(a (b c) d) -> (d (b c) a)
(my-esrever '(they have come for the balding one)) -> (one balding the for come have they)
(my-esrever '()) -> ()
Problem 6: Inside the ship, you discover the ship is a pirate cruise ship -- well, that's its front, anyway. Agent K is being held in the back of the casino. To escape detection, you need to disguise yourself as a card dealer. Can you do it? Write a function called card-divy that takes a number of players and a list of cards, and divides the cards evenly amongst the players. (You can assume the number of cards is evenly divisible by the number of players.)
(card-divy 4 '(2D 9S 6H 6D)) => ((2D)(9S)(6H)(6D))
(card-divy 2 '(3S 9D 8D 3D 10C QH AS JC)) => ((3S 8D 10C AS)(9D 3D QH JC))
Problem 7: After a few hours, the casino shuts down. All the dealers are now merging their piles of money to take into the vault in the back -- which is where Agent K is stored! Write a function called merge, that takes two lists of numbers in ascending order and merges them into one list, which is also in ascending order.
(merge '(1 2 3) '(4 5 6)) => '(1 2 3 4 5 6)
(merge '(1 3 7) '(2 4 6)) => '(1 2 3 4 6 7)
(merge '() '()) => '()
Problem 8: You've pooled your money, and you are heading back to the vault. The pirates now suspect that one of Agent K's PIBS agents may be on the way, and have instituted checks to ensure that only members of the pirate clan can enter the vault. The pirates have an encryption system for their vault combination that is fairly easy to break: you just have to put all the numbers in ascending order. Write a method called selection-sort that, given one list of numbers, returns a new list of the same numbers in ascending order. The selection sort algorithm works by having a new-list and an old-list. At each step, you remove the smallest (or largest) number from the old-list and insert it at the beginning of the new list, like this:
old new (7 3 1 4 8 6 2 5) () (7 3 1 4 6 2 5) (8) (3 1 4 6 2 5) (7 8) (3 1 4 2 5) (6 7 8) (3 1 4 2) (5 6 7 8) (3 1 2) (4 5 6 7 8) (1 2) (3 4 5 6 7 8) (1) (2 3 4 5 6 7 8) () (1 2 3 4 5 6 7 8)
(selection-sort '(5 4 3 2 1)) => '(1 2 3 4 5)
(selection-sort '(99 42 86)) => '(42 86 99)
Problem 9: You attempt to open the vault, only to find that it does not open and an alarm has been set off! Lo and behold, next to the vault door is a bunch of keys. But which key opens the vault?! Many of the keys appear to be duplicates, and so you must remove the duplicates! Write a function called remove-duplicates that takes all the duplicate keys out of the list of keys, leaving only the first. The pirates have determined that you've been using augumented recursion to escape detection, so now you must reverse tactics and use tail recursion instead!
(remove-duplicates 'vault-key '(bathroom-key vault-key other-key vault-key)) => '(bathroom-key vault-key other-key)
(remove-duplicates '2 '(1 2 3 2 1 2 3)) => '(1 2 3 1 3)
What will happen to Agent K? Will Mario discover that the princess is actually in another castle? Stay tuned for homework 3! (Submit this one first, though.)