[ Problem 1 ]
10 points
Malicious Madame Monica has a strange fascination with the (in)famous fibbonacci sequence. Since Monica has a reputation for being Malicious, she is going to make you code this in scheme for her own good pleasure. For review, this is how the fibbonacci sequence works:
fib(0) = 1 fib(1) = 1 fib(n>1) = fib(n-1)+fib(n-2)In this problem, you shall write a function called x-fib-ag that when given a number, will return a dotted pair of that number with the fib of the number. You must write the fib portion of the problem using augmentive recursion. Example:
(x-fib-ag 0) => (0 . 1) (x-fib-ag 1) => (1 . 1) (x-fib-ag 2) => (2 . 2) (x-fib-ag 3) => (3 . 3) (x-fib-ag 4) => (4 . 5)[ Problem 2 ]
Now rewrite the first problem, writing the fib portion using tail recursion. Call this x-fib-tr.
[ Problem 3 ]
15 points
James-the-evil-monkey-manager onboard the ship is trying to keep track of all of the monkeys he brought onboard the good CS1311X ship. He's having a hard time keeping track of them, especially since they're monkeys and hard to control. To aid in his quest to inventory all of the monkeys running amok on the deck of the ship, he wants to keep their names in a list. Your job is to write the my-append function to help him keep a list of the monkeys he has counted and put each new monkey on the end of the list.
Write a function called my-append that mimics the functionality of the built in append function. You may not use append in your code.
Examples:
(my-append '(a b) '(c d)) => (a b c d) (my-append '() '()) => ()
[ Problem 4 ]
10 points
Malicious Madame Monica seems to be up to it again. She's hopelessly interested in mathematics, and she has now decided that she needs a way to square a large amount of numbers without having to make separate scheme calls for each one of them. To do this she has decided to use her favorite data structure, lists. Your mission is to write her a function to keep her happy and hopefully get yourself promoted sooner.
Write a function called square-items-ag that will take a list and return the list with every element inside it squared. You must use augmentive recursion for this problem.
Examples:
(square-items '(4 3 2 5 6)) => (16 9 4 25 36) (square-items '()) => ()[ Problem 5 ]
Now rewrite the previous item using tail recursion. Name this function square-items-tr.
[ Problem 6 ]
15 points
Dan, the pirate formerly known as the sailing man, has been trying to keep track of the monkeys on the ship along with James the evil monkey manager. James has compiled a list of all of the monkeys on the ship, but he fears that there are duplicates. Since there are so many monkeys on the ship, and a recount would be too tedious, Dan has been assigned the task of cleaning up the list and removing all duplicates. Your job is to aid Dan, the pirate formerly known as the sailing man, by writing a function to remove the duplicates from the list.
Write a function called remove-duplicates that when given a list, returns the list with all duplicates removed.
Examples:
(remove-duplicates '(1 1 2 1 4 3)) => (2 1 4 3) (remove-duplicates '(1 2 3 4 5 6)) => (1 2 3 4 5 6) (remove-duplicates '(1 1 1 1 1 1 1)) => (1) (remove-duplicates '()) => ()
Association Lists:
While our Good Captain, Kurt the Balding, is quite the fan of lists,
be them flat or nested, there is one type of list that's near and dear
to his heart, and that's the association list. An association list is
a list that looks like this:
((key-1 associated-data-1) (key-2 associated-data-2) ... (key-n associated-data-n))It's a list of lists, where the first element of each nested list is a unique key, and the rest of the nested list is some data associated with that key. These lists are sometimes called a-lists, for short. There is a built in function called assoc which will retrieve data from an association list. It takes in two parameters: the key to look for and the list to look for the key in. If the key exists in the association list, then it will return the list that the key is the car of; otherwise it returns #f. For example, in the interactions window:
> (assoc 'key-1 '((key-1 associated-data-1)
(key-2 associated-data-2)
(key-n associated-data-n)))
(key-1 associated-data-1)
> (assoc 'pirate '((key-1 associated-data-1)
(key-2 associated-data-2)
(key-n associated-data-n)))
#f
[ Problem 7 ]Being the newest senior member of the CS1311X ship, Malicious Madame Monica has decided to earn brownie points with the the fearless captain Kurt the Balding that she lost when she forgot to attend the pirate meetings. However, being the Malicious Madame, she dosen't want to have to do it herself. She has assigned you the task of writing your own version of assoc, so she can use it and impress Kurt the Balding in hopes of getting a nicer cabin, farther away from the racket of James the Monkey Manager's cabin that is always full of noisy primates.
Write a function called my-assoc that mimics the functionality of the built in assoc function. As usual, you may not use assoc in your code for this problem.
[ Problem 8 ]
15 points
Monica has decided that to better impress Kurt the Balding and get her cabin reassignment, she is going to have to do something useful with assoc lists. She knows that Kurt the Balding loves the nightlife, and he's got to boogie on the disco round. Since there is no disco on the good ship CS1311, he can only boogie when the pirates go into port and have the weekend off. Monica's a pretty smart cookie and she knows that the nightlife is better in large cities. Therefore, she wants to have a function that will take in an list of nearby ports of call and their populations, and have it tell her which city will be the best place to decide to come ashore so Kurt can satisfy his urge. Since she's so Malicious, she has decided to make you, her faithful "assistant", write this function for her.
Write a function called greatest-population that, when given a list of city names and populations, will return the city name and population of the most populated city.
Examples:
(greatest-population '((Devidia 1000)(Nnexus 333)(Aiur 2030))) => (Aiur 2030) (greatest-population '()) => ()
[ Problem 9 ]
10 points
Now that Dan, the pirate formerly known as the sailing man, and James the monkey manager have finally cleaned their monkey list of duplicates, they need to know how many there are causing havoc on the ship. To aid them in their counting, they have decided that you will write a function that will tell them how many monkeys they have on board by counting how many elements there are in a list.
Write a function called my-length that mimics the functionality of the built in length function. It will return the length of a list.
Examples:
(my-length '(1 2 3 4)) => 4 (my-length '()) => 0
[ Problem 10 ]
20 points
By this time, Malicious Madame Monica has gained the reputation for never tiring, no matter how much work "she" does. (Little does the ship know that she's making you do all of the work for her) In the spirit of not working, Malicious Monica has now decided that she wants to be able to add up a list of numbers. However, since she's so Malicious, she has decided that your function should be able to handle nested lists. Your next assignment is to write a function that sums all elements in a list, even if they are nested.
Write a function called sum-elements that will sum all elements in a list, including nested elements.
Examples:
(sum-elements '(1 2 3)) => 6 (sum-elements '((1) 2 (3) 4)) => 10 (sum-elements '((((10 10 (10) 10 10))))) => 50 (sum-elements '()) => 0
[ Problem 11 ]
15 points
While the rest of the ship members are busy keeping the rabid monkeys in line and Malicious Madame Monica is making you work, Vinnie "break your knees" Fiano has been devising ways to make more money in his underground gambling operation on the ship. He has decided to make you write a function that will remove the most likely winner from a list (the most likely winner is the one with the biggest number), so nobody ever bets on the likely winner. Since you're well aware of Vinnie's connections to the pirate mafia, you decide to help him out.
Write a function called remove-largest that given a list of numbers, will remove the largest number and return the rest of the elements. Note that in the examples, there are no duplicates in the list... the same case should exist in your function. You may assume that the list will not be empty.
Examples:
(remove-largest '(1 2 3 4 5 6 21 499)) => (1 2 3 4 5 6 21) (remove-largest '(3)) => () (remove-largest '(1 1 1 1)) => () (remove-largest '(1 2 3 4 1 2 3 4 1 2 3 4)) => (1 2 3)
[ Problem 12 ]
10 points
Dan and James the monkey manager are still having problems with their monkeys. Now they're having problems finding out if the one they want is still onboard the ship. In order to help them find their monkeys, you need to write a function that will find an element in a list and tell them where it is located.
Write a function called find-element that will search through a list and return the position of the element if it exists or #f if it doesn't.
Examples:
(find-element 'a '(b c d e a)) => 5 (find-element '(a) '(b (c) d (a) f)) => 4 (find-element 'z '()) => #f
[ Problem 13 ]
25 points
Kurt the balding had such a good time boogie'ing when out on liberty at the last port of call, he lost his log of your actions whilst on the good ship CS1311X. Since he doesn't know what you have and have not done, he has decided to make you re-code the pascal's triangle function. However, this time he has decided to do tree recursion. Since Kurt is the captian of the good ship CS1311X, you have no other choice than to code this function or walk the plank. Being the good deckhand you are, you accept the task.
Remember the function you wrote in the last homework that returned the element of pascal's triangle at a given row and position? Well, here's your chance to write it again. This time, rather than use nCr, you are to use tree recursion. Call the function pascal-element-at like last time.
Examples:
(pascal-element-at 1 1) => 1 (pascal-element-at 3 2) => 2 (pascal-element-at 6 4) => 10
[ Problem 14 ]
25 points
Vinnie "break your knees" Fiano has decided that he is going to expand his gambling enterprise on-board and start running poker games. To make his job as dealer easier, he wants you to write a function to deal cards to the players. Since he's made you an "an offer he/she can't refuse," you decide to help him out and write a function that take sin a number of players and returns their hands as a list of lists.
Write a function called deal-cards that will take two arguments: the number of players and the deck of cards. It should return a list of lists, each sub-list should be the hand of cards dealt for each player. Note that the order of the cards that the player gets isn't important, but mkae sure that each player gets their correct cards.
Example:
(deal-cards 4 '(2D 9S 6H 6D)) => ((2D)(9S)(6H)(6D)) (deal-cards 2 '(3S 9D 8D 3D 10C QH AS JC)) => ((3S 8D 10C AS)(9D 3D QH JC))You may assume tha the number of players will not exceed the number of cards and that the cards will be evenly divisible by the number of available players.
[ Problem 15 ]
10 points
With all of this monkey sorting and finding trouble, combined with a little of their favorite CS1311X beverage, Dan and James the monkey manager are a little loopy. Now they want to reverse all of the elements in their monkey list. Since you're worried about their mental health, you decide to help them out.
Write a function called my-reverse that, given a list, will reverse it and return the reversed list.
Examples:
(my-reverse '(a b c d e)) => (e d c b a) (my-reverse '((a b c)(d e f))) => ((d e f)(a b c))
[ Problem 16 ]
25 points
Your first function got Vinnie by for a little while. However, people are now catching on to your method of "dealing" and are learning how to cheat the system. In order to eliminate this drain on Vinnie's precious income, he has assigned you to write a new function that will deal the cards the way they are dealt in a real casino.
Now write a function called a-better-card-dealer that will deal cards like a real human would. This allows for 3 players to play with a deck of 52 cards, etc. For those of you who haven't played cards, essentially, player one gets the first card, player two the second, until all the players have gotten one card, then the first player gets his second card, and so on.
Examples:
(a-better-card-dealer 3 '(2D 9S 6H 6D)) => ((2D 6D)(9S)(6H)) (a-better-card-dealer 2 '(2D 3S 5H 6H)) => ((2D 5H)(3S 6H))
[ Problem 17 ]
15 points
Every once and a while something happens to one of the monkeys on the ship. In order to smoothly transition from one monkey to his/her replacement, Dan and James the monkey manager need you to write one more function. Help them replace all instances of a monkey's name with the new one.
Write a function called replace-items that takes in the original element, the element to replace it with, and a list. Replace all occurrences of the first item with the second.
Examples:
(replace-items 'halflife 'quake3 '(halflife rox)) => (quake3 rox) (replace-items 'hate 'love '(I hate cs)) => (I love CS)