340Material

pdf

School

University of Saskatchewan *

*We aren’t endorsed by this school

Course

340

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by ananddiya80

Assignment-2 Scala programming [Do not use any other advanced features of Scala not covered in class prior to release of this assignment. You must provide a signature for every function, including the return type. Whenever meaningful, use type variables instead of types. Finally, ensure that the parameters passed to the functions are of the correct types and are passed in the correct order.] Problem 1 [45 Points]. The following set of problems is about shuffling of cards, particularly something called the Faro shuffle, where the stack is broken up into two, and then combined so that a card from one sub-stack is followed by one from the other, and so on. A perfect Faro shuffle breaks up the stack into two sub-stacks of exactly the same size, and then combines them in the manner described above. An out-shuffle results in the top and the bottom cards of the stack remaining the same after the shuffle; an in-shuffle results in these cards becoming the second and the second last cards of the shuffled stack. [Note: Do not use built-in higher-order functions for this problem] (a) [10 Points]. Write a polymorphic function, shuffle, which takes two lists l1 and l2 representing decks of cards, and returns the result of a combining of the lists. Particularly, the returned list contains the first element of l1, followed by the first element of l2, followed by the second element of l1, and so on. If one of the lists ends before the other, the other list’s remaining elements are simply added to the end. (b) [7 Points]. Write a polymorphic function, split, which takes as parameters a list and an Integer n, indicating the splitting point. It splits the contents of the provided list into two lists, the first with the first n elements of the list (in order), and the second with the remaining elements (again, in order). These two lists are then returned as a list of two lists. (c) [8 Points]. Write two polymorphic functions, outshuffle and inshuffle, which use shuffle and split functions described above (and possibly additional intermediary functions), and carry out perfect Faro shuffles of the out-shuffle and in-shuffle type. In other words, they take a single stack of an even number of cards, break them up and return the result of applying the required type of Faro shuffle exactly once. (d) [10 Points]. Write a polymorphic function, nshuffle, which takes three parameters, a shuffle function (such as outshuffle or inshuffle), an integer indicating how many shuffles to carry out, and a list to shuffle, which is of even length. It then carries out the required number of shuffles on the list, and returns the result. (e) [10 Points]. Write a polymorphic function, howManyShuffles, which takes three parameters: a shuffle function (such as outshuffle or inshuffle), and two lists of even size. It keeps applying the shuffle function on the first of the two lists, until it becomes identical to the second list, and returns the count of the number of shuffles that were required.

As part of your testing of howManyShuffles, try to find out: i) How many out-shuffles are required to return a stack of 52 cards to its original ordering? ii) How many in-shuffles are required to completely reverse a stack of 52 cards? Problem 2 [35 Points]. Define a polymorphic Tree data type, where a Tree is either a Node with a left subtree, a value, and a right subtree; or it is a Leaf with just a value. [10 Points] Also define a companion object for the Tree data type, with the following functions: (a) [15 Points]. Three polymorphic functions -- inOrder, preOrder, and postOrder -- to traverse the tree in-order, pre-order, and post-order. Each function takes a tree and returns a list with the contents of the tree when traversed in that order. (b) [5 Points]. A polymorphic function, search, which takes two arguments — a Tree and a key — and returns a boolean result based on whether the key is found in the tree. (c) [5 Points]. A polymorphic function, replace, which takes three arguments — a Tree t, a value before, and a value after — and returns t with ALL instances of before replaced with the value after. [Hint: Model your Tree data type after the List data type presented in class.] Problem 3. [20 Points]. The Luhn algorithm is used to check bank card numbers for simple errors such as mistyping a digit, and proceeds as follows: - Consider each digit as a separate number - Moving right-to-left and beginning at the second last digit, double every other number - Subtract 9 from each number that is now greater than 9 - Add all the resulting numbers together - If the total is divisible by 10, the card number is valid a) [3 Points]. Define a function luhnDouble that doubles a digit and subtracts 9 if the result is greater than 9. For example:

scala> luhnDouble(3) res0: Int = 6 scala> luhnDouble(6) res1: Int = 3 b) [10 Points]. Define a function altMap, which takes as parameter a list of functions to apply to a list. altMap applies the functions in the functions list to the elements of the list in order. In other words, it applies the first function to the first element, the second function to the second, and so on, until it is time to go back to applying the first function to the next element. For example, altMap (List(_ + 10, _ + 100), List(0, 1, 2, 3, 4)) evaluates to List(10, 101, 12, 103, 14). Do not use built-in higher-order functions to implement altMap. c) [7 Points]. Define function luhn for checking the validity of card numbers of arbitrary lengths using altMap. luhn should accept a list of Int values to represent the digits of the card. Submission: Create a directory with your nsid as its name. For each problem, place your code in a Scala source file called problem<number>.scala. Create a second text file problem<number>.txt to show transcripts of your testing of the code. Place all files in the directory named for your nsid, and create a zip file for the directory. If your nsid is <your_nsid>, the zip file should be called <your_nsid>.zip. When opened, it should create a directory called <your_nsid>. Submit the zip file. You may submit multiple times before the deadline, so you are advised not to wait till the last minute to submit your assignment to avoid system slowdown. You are encouraged to submit completed parts of the assignment early.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Assignment-3.1 Functional Error Handling Total: 50 Points Problem 1 [25 Points]. Scala supports a way to keep track of key-value pairs using Maps. For example, you can create a Map mapping digits to their string equivalents as follows: val digMap = (0 -> "zero", 1 -> "one", 2 -> "two", 3 -> "three", 4 -> "four", 5 -> "five", 6 -> "six", 7 -> "seven", 8 -> "eight", 9 -> "nine") Research functions (particularly, get, keys and apply) available on Map. Consider the following slightly out-of-date Map for the British royal family, showing gender and parentage information for individuals. For example, the information for Prince Harry is represented using the "Harry" -> ("m", "Diana", "Charles") mapping. The Map is based on an earlier version of the tree shown on this webpage: https://www.bbc.com/news/uk-23272491 Links to an external site. val royalParent = Map("George" -> ("m", "William", "Catherine"), "Charlotte" -> ("f", "William", "Catherine"), "Louis" -> ("m", "William", "Catherine"), "Archie" -> ("m", "Harry", "Meghan"), "Lilibet" -> ("f", "Harry", "Meghan"), "Savannah" -> ("f", "Autumn", "Peter"), "Isla" -> ("f", "Autumn", "Peter"), "Mia" -> ("f", "Zara", "Mike"), "Lena" -> ("f", "Zara", "Mike"), "Lucas" -> ("m", "Zara", "Mike"), "Sienna" -> ("f", "Beatrice", "Edoardo"), "August" -> ("m", "Eugenie", "Jack"), "Beatrice" -> ("f", "Andrew", "Sarah"), "Eugenie" -> ("f", "Andrew", "Sarah"), "Louise" -> ("f", "Edward", "Sophie"), "James" -> ("m", "Edward", "Sophie"), "Peter" -> ("m", "Mark", "Anne"), "Zara" -> ("f", "Mark", "Anne"), "William" -> ("m", "Diana", "Charles"), "Harry" -> ("m", "Diana", "Charles"), "Charles" -> ("m", "Elizabeth", "Philip"), "Anne" -> ("f", "Elizabeth", "Philip"), "Andrew" -> ("m", "Elizabeth", "Philip"), "Edward" -> ("m", "Elizabeth", "Philip"), "Elizabeth" -> ("f", "", ""), "Philip" -> ("m", "", ""), "Diana" -> ("f", "", ""), "Mark" -> ("m", "", ""), "Sophie" -> ("f", "", ""), "Sarah" -> ("f", "", ""), "Mike" -> ("m", "", ""), "Autumn" -> ("f", "", ""), "Meghan" -> ("f", "", ""), "Catherine" -> ("f", "", ""), "Timothy" -> ("m", "", ""), "Jack" -> ("m", "", ""), "Camilla" -> ("f", "", ""), "Edoardo" -> ("m", "", "")) Notice that because of the primary focus on direct descendants of Queen Elizabeth, the amount of information available depends on whether one is a descendant of Queen Elizabeth or not. Particularly, note that there there is no parentage information available for the Queen, Prince Philip, and for spouses of their descendants. Now, implement the following functions to extract information about particular family relationships from this Map.

a) [5 Points] def children(parent1: String, parent2: String): Option[List[String]] // the potential parents can be in either order b) [5 Points] def grandparents(p: String): Option[List[String]] c) [5 Points] def sisters(p: String): Option[List[String]] d) [5 Points] def firstCousins(p: String): Option[List[String]] e) [5 Points] def uncles(p: String): Option[List[String]] // both uncles who are brothers of a parent, and parent's sisters' spouses Implement (a) and (b) directly; the remaining problems may assume existence of correct implementations of (a) and (b). (e) may assume correct implementation of (d). You may also implement additional helper functions. The Option return values are meant to capture situations where information is unavailable, such as about parents, grandparents, sisters, etc. of spouses of direct descendants of Queen Elizabeth. For example, if there is parentage information about a person, but no sisters can be found, the sisters function (c) should return Some(Nil); if parentage information is unavailable, it should return None. If the parent names provided to the children function (a) do not appear as a couple, a None should be returned because returning Some(Nil) would imply that they are a couple with no children; couples without children are not represented here because the data representation does not record marriages (or equivalent). Problem 2 [25 Points]. Recall that unlike Options where multiple errors are simply subsumed by a None, when we deal with multiple errors in Eithers, all but one are lost. Implement a datatype to return back multiple errors. Pay close attention to situations which do and do not require recording of multiple errors. You may use the following definition for the purpose of defining your data type. trait Partial[+A,+B] case class Errors[+A](get: Seq[A]) extends Partial[A,Nothing] case class Success[+B](get: B) extends Partial[Nothing,B] Now, implement the following functions for this datatype, accumulating errors when meaningful to do so: a) [3 Points] map b) [3 Points] flatMap

c) [3 Points] getOrElse d) [3 Points] orElse e) [5 Points] map2 f) [6 Points] traverse Finally: g) [2 Points] Implement the Try function to convert a possible exception into a Partial Submission: Create a directory with your nsid as its name. For each problem, place your code in a Scala source file called problem<number>.scala. Create a second text file problem<number>.txt to show transcripts of your testing of the code. Place all files in the directory named for your nsid, and create a zip file for the directory. If your nsid is <your_nsid>, the zip file should be called <your_nsid>.zip. When opened, it should create a directory called <your_nsid>. Submit the zip file. You may submit multiple times before the deadline, so you are advised not to wait till the last minute to submit your assignment to avoid system slowdown. You are encouraged to submit completed parts of the assignment early.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Assignment-3.2 Strictness and Laziness Total: 50 Points For these problems, use the following implementation of unfold: def unfold[A, S](z: S)(f: S => Option[(A, S)]): LazyList[A] = f(z) match { case Some((h, s)) => h #:: unfold(s)(f) case None => LazyList() } [Note: #:: is the Cons constructor of LazyLists] Problem 1 [25 Points] A triple (x, y, z) of positive integers is pythagorean if x2 + y2 = z2. Using the functions studied in class, define a function pyth which returns the list of all pythagorean triples whose components are at most a given limit. For example, function call pyth(10) should return [(3, 4, 5), (4, 3, 5), (6, 8, 10), (8, 6, 10)]. [Hint: One way to do this is to construct a list of all triples (use unfold to create a list of integers, and then a for-comprehension to create a list of all triples), and then select the pythagorean ones. Problem 2 [25 Points] A positive integer is perfect if it equals the sum of all of its factors, excluding the number itself. For example, 6, 28, 496, and so on. Define a LazyList to generate an infinite list of perfect numbers. Use higher-order functions whenever possible. [Hint: One way to do this is by (1) having one function construct a list of factors (use unfold and filter for this), (2) having another function which folds the list of factors into their sum, and (3) creating a LazyList using unfold, filter and the previously constructed functions.] Submission: Create a directory with your nsid as its name. For each problem, place your code in a Scala source file called problem<number>.scala. Create a second text file problem<number>.txt to show transcripts of your testing of the code. Place all files in the directory named for your nsid, and create a zip file for the directory. If your nsid is <your_nsid>, the zip file should be called <your_nsid>.zip. When opened, it should create a directory called <your_nsid>. Submit the zip file. You may submit multiple times before the deadline, so you are advised not to wait till the last minute to submit your assignment to avoid system slowdown. You are encouraged to submit completed parts of the assignment early.

Assignment-4 Concurrent Programming with Actors Total: 100 Points Solve the following problems using Scala with Classic Akka Actors. For each problem, also implement client actors for sending the messages required for beginning the required computation. Use these client actors for testing your application actors. Read the submission instructions carefully. Problem 1 (50 Points): Sorting. It is possible to sort a number of values using a pipeline of filter actors, each responsible for one value: the first actor picks the smallest value, the second the second smallest and so on. Particularly, the first actor receives all the values, one by one. If there are more than one values received by an actor, it creates another actor; it keeps the smallest value received so far for itself, and sends all other values forward to the actor it created. Each filter actor does the same thing. Assume that each filter actor has local storage for only two of the values to be sorted: the next incoming value and the minimum value seen thus far. A sentinel is used to indicate the end of the values to be sorted. The sentinel is then sent down the pipeline to inform all actors of the end of the input. On receiving the sentinel, each filter actor replies to the sender of the sentinel with its smallest value. All actors simply forward back the values they receive from actors down the pipeline from them, so that the first actor receives all the values in a sorted order, and sends them forward to the original requester, one value at a time. Develop actor code to implement this for sorting positive integers. Use 0 to indicate the end of the values to be sorted. Problem 2 (50 Points): Recall the card shuffling problem from Assignment 2. In a Faro shuffle, a stack of cards is broken up into two, and then combined so that a card from one sub-stack is followed by one from the other, and so on. A perfect Faro shuffle breaks up the stack into two sub-stacks of exactly the same size, and then combines them in the manner described above. An out-shuffle results in the top and the bottom cards of the stack remaining the same after the shuffle; an in-shuffle results in these cards becoming the second and the second last cards of the shuffled stack. Implement a shuffler actor which accepts a message containing a deck of cards as a list of even length, an integer indicating the number of times that the deck is to be shuffled, and a boolean indicating whether the shuffles should be in-shuffle (false) or out-shuffle (true). Once it is done shuffling the deck, it returns the shuffled deck to the sender of the message.

The shuffler shuffles with the help of two other actors -- splitter and faroShuffler. The shuffler sends a message to the splitter containing the deck of cards, and the name of faroShuffler. The shuffler also sends a message to faroShuffler with a boolean indicating whether in-shuffle or out-shuffle is required. On receiving the deck, the splitter evenly splits the deck of cards into two lists, and sends the two lists to faroShuffler, one at a time. Once faroShuffler has received the two lists, and once it knows what type of shuffle is to be carried out, it first tells a cardCollector actor the shuffler's name and the number of cards to expect to receive; next, it begins sending the cards from its two decks to the cardCollector actor -- one card at a time, alternating between the two lists, beginning with the list required for the correct type of shuffle. The cardCollector actor simply collects the cards in the order in which they are received in a list, and when it has received all of them, it sends the list of cards to shuffler. Only the shuffler keeps track of how many shuffles have been completed, and when the required number of shuffles are done, it sends the shuffled deck to the actor requesting it. Develop code to implement these actors for shuffling a deck of cards. Submission: Create a directory with your nsid as its name. For each problem, place your code in a Scala source file called problem<number>.scala. Create a second text file problem<number>.txt to show transcripts of your testing of the code. Place all files in the directory named for your nsid, and create a zip file for the directory. If your nsid is <your_nsid>, the zip file should be called <your_nsid>.zip. When opened, it should create a directory called <your_nsid>. Submit the zip file. You may submit multiple times before the deadline, so you are advised not to wait till the last minute to submit your assignment to avoid system slowdown. You are encouraged to submit completed parts of the assignment early.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Assignment-5 Prolog Programming Total: 100 Points It turns out that most family relationships can be defined in terms of a few simple predicates. Here is a set of predicates sufficient for many families: a) ever_married_to(person1, person2) % person1 is married to person2, or was married to person2 at some point in time b) child_of(person1, person2) % person1 is a child of person2 c) male(person) % person is male d) female(person) % person is female e) deceased(person) % person is no longer alive For each predicate involving two people, assume that the functor describes how person1 relates to person2. Now, consider the royal family. In addition to the above, the following additional predicate may also be meaningful: f) senior_royal(person) % person is a senior royal. All in the graph below except Harry, Meghan and their children, are senior royals. Diana (d) --- Charles ----- Camilla |____| ____|_________ | | William ---- Catherine Harry ---- Meghan |___| |___| __|______ ___|__ | | | | | George Charlotte Louis Archie Lilibet Note that Diana is deceased. 1. [12 Points] Represent the facts in the graph shown above using facts in Prolog, limiting yourself to the six simple predicates listed above.

2. [63 Points] Write Prolog rules for the following additional relationships. Your rules for the relationships should not rely on the correctness of other rules; they should be independent. Your rules should work correctly for more complex family relation structures involving the same predicates; they should not be such that they work only on this small family tree. (Note: You may need to use not, where not(p) says that p cannot be proved): a) uncle_of(person1, person2) b) grandmother_of(person1, person2) c) grandson_of(person1, person2) d) parent_of(person1, person2) e) mother_of(person1, person2) f) stepmother_of(person1, person2) g) son_of(person1, person2) 3. [25 Points] Write Prolog queries to ask the following questions. You may use all thirteen predicates above; assume that you have correct solutions to Problems 1 and 2. Your queries should work correctly for more complex family relation structures involving the same predicates; they should not be such that they work only on this small family tree. a) Is Camilla the step mother of Louis? [should respond with no] b) Who are the grandchildren of a deceased person? [should respond with George, Charlotte, Louis, Archie and Lilibet] c) Who are the senior royal step children of Camilla? [should respond with William] d) Who are the parents of both William and Harry? [should respond with Charles and Diana] e) Who are the males with a female cousin? [should respond with George, Louis and Archie] Submission: Submit your solutions to Problems 1 and 2 as a single Prolog file named 5-1-2.pl. Submit your solution to Problem 3 as a plain text file containing a transcript of the program file being queried with your queries; name this file 5-3.txt

Create a directory with your nsid as its name. Place both files in the directory, and then submit a zipped version of this directory (i.e., nsid.zip). You may submit multiple times before the deadline, so you are advised not to wait till the last minute to submit your assignment to avoid system slowdown. You are encouraged to submit completed parts of the assignment early. Late submissions will not be accepted.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

340Material

Related Documents