Data structure | aws代做 | AI | 代写assignment – CSCI3180 Principles of Programming Languages Spring 2022

2023-07-21

CSCI3180 Principles of Programming Languages Spring 2022

Data structure | aws代做 | AI | 代写assignment – 这是利用aws进行训练的代写, 对aws的流程进行训练解析, 是有一定代表意义的Data structure/aws/AI等代写方向, 这个项目是assignment代写的代写题目

数据结构代写 代写数据结构 Data structure代写 算法代写

 assignment 4  Declarative Programming

1 Introduction

Declarative programming is a programming paradigm that emphasises the expression of what the problem is over how to solve the problem. You will gain experience of declarative programming with Prolog (Logic Programming) and ML (Functional Programming) in this assignment. You are supposed to test your work on the machinesolar1.cse.cuhk.edu.hkusing

  • SICStus 3.12.
  • Standard ML of New Jersey, Version 110.0.

They can be invoked using the commandssicsandsmlrespectively.

2 Logic Programming

Implement the predicates of the following problem in a Prolog program file named asg4.pl. You should clearly indicate usingcommentsthe corresponding problem number. Note that you are not allowedto use any built-in predicates in Prolog. Recall the example of the binary tree in the lecture. You will be practising classic binary tree questions using the successor notation. In the following, we assume that all nodes in a binary tree are natural numbers with the successor notation, as shown in Figure 1. Remember that all numbers your predicates use should also be in the successor notation.

Figure 1: A Binary Tree Example.
  1. Define predicateisbinarytree(T)which is true ifTis a binary tree. Example: ?- isbinarytree(bt(bt(bt(nil,0,nil),s(0),bt(nil,s(s(s(0))),nil)), s(s(s(s(0)))), bt(nil,s(s(0)),nil))). yes
  2. A binary search tree is a rooted binary tree Data structure each internal node of which stores a key greater than all the keys in the nodes left subtree and less than those in the nodes right subtree. a) Definelt(X,Y)which is true ifXis less thanYin the successor notation. b) Usinglt(X,Y), definebstree(T)which is true ifTis a binary search tree. Example: ?- bstree(bt(bt(bt(nil,0,nil),s(0),bt(nil,s(s(s(0))),nil)),s(s(s(s(0)))), bt(nil,s(s(0)),nil))). no ?- bstree(bt(bt(bt(nil,0,nil),s(0), bt(nil,s(s(s(0))),nil)), s(s(s(s(0)))), bt(nil,s(s(s(s(s(0))))),nil))). yes
  1. Defineparent(T, P, C)is true if nodeCis a child of nodePin a binary treeT. Example: ?- parent(bt(bt(bt(nil,0,nil),s(0), bt(nil,s(s(s(0))),nil)), s(s(s(s(0)))), bt(nil,s(s(0)), nil)), s(s(s(s(0)))), C). C = s(0)? ; C = s(s(0))? ; no ?-parent(bt(bt(bt(nil,0,nil),s(0), bt(nil,s(s(s(0))),nil)), s(s(s(s(0)))), bt(nil,s(s(0)), nil)), P, 0). P = s(0)? ; no
  2. Definedescendent(T, A, D)is true if nodeDis a descendent of nodeAin a binary treeT. Example: ?- descendent(bt(bt(bt(nil,0,nil),s(0), bt(nil,s(s(s(0))),nil)), s(s(s(s(0)))), bt(nil,s(s(0)), nil)), s(s(s(s(0)))), D). D = s(0)? ; D = s(s(0))? ; D = 0? ; D = s(s(s(0)))? ; no ?- descendent(bt(bt(bt(nil,0,nil),s(0), bt(nil,s(s(s(0))),nil)), s(s(s(s(0)))), bt(nil,s(s(0)), nil)), P, 0). P = s(0)? ; P = s(s(s(s(0))))? ; no
  3. Definecountnodes(T, X)which is true ifXis the total number of all non-empty nodes in a binary treeT. Example: ?- countnodes(bt(bt(bt(nil,0,nil),s(0), bt(nil,s(s(s(0))),nil)), s(s(s(s(0)))), bt(nil,s(s(0)), nil)), X). X = s(s(s(s(s(0)))))? ; no
  4. Definesumnodes(T, X)which is true ifXis the sum of all nodes in a binary treeT. Example: ?- sumnodes(bt(bt(bt(nil,0,nil),s(0), bt(nil,s(s(s(0))),nil)), s(s(s(s(0)))), bt(nil,s(s(0)), nil)), X). X = s(s(s(s(s(s(s(s(s(s(0))))))))))? ; no ?- sumnodes(T, s(s(s(s(s(s(s(0)))))))). T = bt(nil,s(s(s(s(s(s(s(0))))))),nil)? ; T = bt(nil,s(s(s(s(s(s(s(0))))))),bt(nil,0,nil))? ; T = bt(nil,s(s(s(s(s(s(0)))))),bt(nil,s(0),nil))? ; T = bt(nil,s(s(s(s(s(0))))),bt(nil,s(s(0)),nil))? ; T = bt(nil,s(s(s(s(0)))),bt(nil,s(s(s(0))),nil))? ; T = bt(nil,s(s(s(0))),bt(nil,s(s(s(s(0)))),nil))? yes
  5. Using theappend(L1,L2,L3)predicate, definepreorder(T, X)which is true ifXholds the results from a preorder traverse of a binary treeT. Example: ?- preorder(bt(bt(bt(nil,0,nil),s(0), bt(nil,s(s(s(0))),nil)), s(s(s(s(0)))), bt(nil,s(s(0)),nil)), X). X = [s(s(s(s(0)))), s(0), 0, s(s(s(0))), s(s(0))]? ; no

3 Functional Programming

Implement the required functions of the following problems in aStandard MLprogram file named asg4.sml. You should clearly indicate using comments the corresponding question number of

each problem. We design a card game, based on the popular Black Jack game, for the practice of functional programming. A set of functions should be implemented to help you finish the main program step by step. The card game is designed for two players:Player 1andPlayer 2. The two players draw cards from a common card list in turn, following the order of the cards in the card list. The number of drawn cards is determined by each player. Player 1dr aws cards first. In this card game, only the ranks of cards are considered. The joker cards are not included. Each rank has its corresponding point. To increase the interest of this game, we design two versions: the basic version and the magic version. In the basic version, the point of each rank is unique: 1) the point ofJack,Queen, and Kingis 10; 2) the point of the cards with ranks 2 to 9 is the same as the corresponding rank; and

  1. the point ofAceis 1. In the magic version, the point ofAcecan be either 1 or 11, as determined by the players to maximize their chance of winning. The points of other ranks are the same as those of the basic version. In this game, the total point (T P) of the drawn cards of each player is computed as below:
T P=
(
21 if sp mod 21 = 0and sp > 0
sp mod 21 otherwise
(1)

wherespis the sum of the points of all drawn cards. After theT Pof each player is computed, the result of the game can be determined. If theT PofPlayer 1is larger than that ofPlayer 2 ,Player 1wins the game. If theT PofPlayer 1is smaller than that ofPlayer 2,Player 2 wins the game. Otherwise, the game ends in a tie. In the ML implementation, the type definition of ranks is shown below: datatype rank = Jack | Queen | King | Ace | Num of int;

We will use some examples to illustrate the rules of the games, first for drawing cards. Assume the card list is[Num 1, Num 2, Num 3, Num 4, King, Jack, Queen, Ace, Num 9, Num 10]. Player 1andPlayer 2draw cards from the same card list in turn.Player 1always goes first.

  • AssumePlayer 1draws 3 cards andPlayer 2draws 3 cards. Player 1will get[Num 1, Num 3, King].Player 2will get[Num 2, Num 4, Jack].
  • If the numbers of drawn cards are different for the two players, one player stops drawing cards when the player gets enough cards while the other player continues to draw cards one by one from the remaining cards in the card list. AssumePlayer 1draws 5 cards andPlayer 2 draws 3 cards.Player 1will get[Num 1, Num 3, King, Queen, Ace].Player 2will get [Num 2, Num 4, Jack].
  • AssumePlayer 1draws 3 cards andPlayer 2draws 5 cards. Player 1will get[Num 1, Num 3, King].Player 2will get[Num 2, Num 4, Jack, Queen, Ace].

Then, we will use an example to explain the calculation ofT Pfor the basic version and the magic version. AssumePlayer 1gets[Ace, Ace, 3]. In the basic version, the point ofAceis 1. Therefore,T Pcan be computed as 1 + 1 + 3 = 5. In the magic version, the point ofAcecan be 1 or 11. Players should choose the proper point of eachAceto makeT Pthe largest. Therefore,T P can be calculated by a divide-and-conquer method. In this case, the bestT Pis 1 + 11 + 3 = 15. The functions you should implement in the submitted file are given below. Note that the introduced order of input values should also be the implemented order in your submitted file. In implementing the following functions, you should usepattern matchingandletinwherever possible for tidier codes.

  1. Write an ML functiongetbasicpoint, which takes arankas input and returns the point (int value) of the rank for basic version. For example, the return value ofgetbasicpoint(Ace)is 1. The return value ofgetbasicpoint(Num 5)is 5. The return value ofgetbasicpoint(Jack)is 10.
  1. Write an ML functiongetcards. The function takes as input the number of cards for Player 1(int value,n1), the number of cards forPlayer 2(int value,n2), and the common card list for the two players (rank list,cardlist). The function returns a pair of card lists to the two players: (player1cards, player2cards) (rank list * rank list). You can assume that n1andn2are positive, andn1 + n2is smaller than the number of the cards incardlist. For example, the return value of getcards(2, 2, [Num 5, Num 2, Num 3, Num 4]) is ([Num 5, Num 3], [Num 2, Num 4]).
  2. Write an ML functioncalTP. This function is a tool for the game, and takes the sum of points for all drawn cards, which isspdefined above (int value), as input. The function returnsT P(int value). For example, the return value ofcalTP(22)is 1. The return value ofcalTP(21)is 21. The return value ofcalTP(0)is 0.
  3. Write an ML functiongetbasicTP. The function takes arank listas input and returns theT P(int value) value of the input for the basic version. Therefore, the calculation rules follow the basic version, whereAceis equal to 1. For example, the return value ofgetbasicTP([Ace, Num 2, Num 3, Num 4])is 10.
  4. Write an ML functiongetTP. The function takes arank listas input and returns theT P (int value) value of the input for the magic version. Therefore, the calculation rules follow the magic version, whereAcecan be 1 or 11. For example, the return value ofgetTP([Ace, Num 10])is 21.
  5. Write an ML functionjudgewinnerbasicfor the basic version. The functions takes as input the drawn cards ofPlayer 1(rank list) and the drawn cards ofPlayer 2(rank list). The function returns the result (int value) of the game: a) ifPlayer 1wins, the function returns 1; b) ifPlayer 2wins, the function returns 2; and c) the function returns 0 for a tie.
  6. Write an ML functionjudgewinnerfor the magic version. The functions takes as input the drawn cards ofPlayer 1(rank list) and the drawn cards ofPlayer 2(rank list). The function returns the result (int value) of the game: a) ifPlayer 1wins, the function returns 1; b) ifPlayer 2wins, the function returns 2; and c) the function returns 0 for a tie.
  7. Write an ML functionbasicresultfor the basic version. The function takes as input the number of cards forPlayer 1(int value,n1), the number of cards forPlayer 2(int value, n2), and the common card list for the two players (rank list,cardlist). The function returns the result (int value) of the game: a) ifPlayer 1wins, the function returns 1; b) ifPlayer 2wins, the function returns 2; and c) the function returns 0 for a tie. You can assume thatn1andn2are positive, andn1 + n2is smaller than the number of the cards in cardlist.
  8. Write an ML functionresultfor the magic version. The function takes as input the number of cards forPlayer 1(int value,n1), the number of cards forPlayer 2(int value,n2), and the common card list for the two players (rank list,cardlist). The function returns the result (int value) of the game: a) ifPlayer 1wins, the function returns 1; b) ifPlayer 2 wins, the function returns 2; and c) the function returns 0 for a tie. You can assume thatn andn2are positive, andn1 + n2is smaller than the number of the cards incardlist.
  9. Write an ML functioncallargestTPfor the magic version. This function is designed for calculating the largestT Pwhich can be gotten byPlayer 2with any legal number of cards. The function takes as input the number of cards forPlayer 1(int value,n1) and the common card list for the two players (rank list,cardlist). The function returns the largestT Pfor Player 2out of all the possible numbers of drawn cards from the card list. You can assume thatn1is positive, and the total number of drawn cards for the two players must not be larger than the number of the cards incardlist. For example, the return value ofcallargestTP(1, [Ace, Num 10, Ace, Num 3, Ace]) is 21 when Player 2 gets[Num 10, Ace].

4 Submission Guidelines

Please read the guidelinesCAREFULLY. If you fail to meet the deadline because of submission problem on your side, marks will still be deducted. So please start your work early!

  1. In the following,SUPPOSE
your name isChan T AI Man,
your student ID is 1155234567 ,
your username istmchan, and
your email address [email protected].
  1. In your source files, insert the following header.REMEMBERto insert the header accord- ing to the comment rule ofPrologorStandard ML.
/
CSCI3180 Principles of Programming Languages

--- Declaration ---

I declare that the assignment here submitted is original except for source
material explicitly acknowledged. I also acknowledge that I am aware of
University policy and regulations on honesty in academic work, and of the
disciplinary guidelines and procedures applicable to breaches of such policy
and regulations, as contained in the website
http://www.cuhk.edu.hk/policy/academichonesty/

Assignment 4
Name : Chan Tai Man
Student ID : 1155234567
Email Addr : [email protected]
/
  1. Late submission policy: less 20% for 1 day late and less 50% for 2 days late. We shall not accept submissions more than 2 days after the deadline.
4.Taryour source files totmchan.tarby

tar cvf tmchan.tar asg4.pl asg4.sml

5.Gzipthetarredfile tousername.tar.gzby

gzip tmchan.tar

6.Uuencodethegzippedfile and send it to the course account with the email title HW
studentID yourName by

uuencode tmchan.tar.gz tmchan.tar.gz \
|mailx -s "HW4 1155234567 Chan Tai Man" [email protected]
  1. Please submit your assignment using your linux accounts.
  2. An acknowledgement email will be sent to you if your assignment is received. PleaseDO NOT delete or modify the acknowledgement email. You should contact your TAs for help if you do not receive the acknowledgement email within 5 minutes after your submission. DO NOT re-submit just because you do not receive the acknowledgement email.
  3. You can check your submission status at
http://course.cse.cuhk.edu.hk/~csci3180/submit/hw4.html.
  1. You can re-submit your assignment, but we will only grade the latest submission.
  2. Enjoy your work :>