CSC3030 Programming Paradigms Practical Exercises (30%) 1994. You must write J programs to solve the problems below. The single source file containing your solution to a particular exercise, Ex1 to Ex4, must be submitted electronically, using the Unix `submit' command (not using mail) before the end of the appropriate deadline. Submit will not accept solutions after the deadline. If there is any problem with the submit command near to a deadline then give a paper copy of your solution to me (or hand it in to the Dept. office) before the deadline (!) and also submit it electronically later - I will check that the copies are identical. The objective is for you to become familiar with the features of J and to get an idea of the J style of programming. J is very different from languages like C and Pascal. I do not expect you to become an expert in J but you should make a serious attempt to get into the J way of thinking and should not just recode C into J. *** Do not use any of the J features associated with `workspaces', `systems' *** `locales', `profile.js' and `foreign conjunction' (!:) Unix calls except *** for file read (1!:1 < 'filename') and possibly write screen (1!:2) 2. ------------------------------------------------------------------------------- Ex1: by end of week 3: Friday 18 March 1994 ********************************** Submit a text file containing the J function pascal: . Pascal's Triangle. Write a function `pascal n' which will print Pascal's triangle down to the n-th row, n>=0. (NB. Each number is the sum of the 1 or 2 numbers above it in the previous row.) 1 1 1 1 2 1 1 3 3 1 is ok for pascal 3 0: 1 1: 1 1 2: 1 2 1 3: 1 3 3 1 is better Your function will be tested with different values of n. ------------------------------------------------------------------------------- Ex2: by end of week 5: Friday 1 April 1994 *********************************** Submit a text file containing J functions ms, readmatrix & paths: . ms 'filename' should read a list of numbers from file `filename' and print their mean and standard deviation. . readmatrix 'filename' should read a matrix from the file `filename', one row per line, and return a matrix of numbers. eg. `fn': 1 2 3 4 5 6 7 8 9 readmatrix `fn' --> 1 2 3 4 5 6 7 8 9 . All-pairs shortest paths. `paths m' should calculate the all-pairs shortest paths matrix, given a square matrix m of edge-lengths, using Floyd's algorithm. (An absent edge is represented by _ for infinite length.) NB. paths readmatrix `filename' should operate on data from a file. ------------------------------------------------------------------------------- Ex3: by end of week 7: Friday 22 April 1994 *********************************** Submit a text file containing the J functions queens and ED: . N-queens problem: place N queens on an NxN chess-board so that no 2 queens threaten each other. `queens N' should print all solutions and count them eg. N=5 . Q . . . . . . . Q . . Q . . Q . . . . . . . Q . one solution. . 'stringA' ED 'stringB' should calculate the edit distance of two strings. eg. 'ACGTACTACTGT' ED 'ACCTACGTACGT' --> 3 define D[i, j] = edit distance of A[1..i] and B[1..j] then D[0,0] = 0 D[i,0] = i, i=1..|A| D[0,j] = j, j=1..|B| D[i,j] = if A[i]=B[j] then D[i-1,j-1] for i=1..|A| else 1+min( D[i,j-1], D[i-1,j], D[i-1,j-1] ) and j=1..|B| and D[|A|,|B|] is the edit distance of string A and string B. ------------------------------------------------------------------------------- Ex4: by end of week 9: Friday 6 May 1994 ************************************** Submit a text file containing the J functions BST, show, infix, prefix, postfix & bfirst: . Binary search tree (hint use boxes). Write a function `BST' so that `T BST L' inserts the list of items L into the tree T, returning a larger binary search tree. eg. T =. empty BST 5 6 3 9 8 1 0 2 7 4 a possible format for printing a tree T, show T: |-9| | |-8| | |-7 |-6| T----->5-| | |-4 |-3| | |-2 |-1| |-0 prefix T --> 5 3 1 0 2 4 6 9 8 7 infix T --> 0 1 2 3 4 5 6 7 8 9 postfix T --> 0 2 1 4 3 7 8 9 6 5 bfirst T --> 5 3 6 1 4 9 0 2 8 7 ------------------------------------------------------------------------------- All exercises will be marked at demonstrations lasting 20 to 30 minutes at times to be arranged starting week 10: *** Monday 9 May 1994 *** onwards. You will be marked on your understanding of both J and your solutions to the exercises. You will be asked about alternative solutions to the exercises and also about *** different problems altogether *** such as those in the J Introduction and Dictionary. Be sure to review all exercises and your solutions before the demonstration. ------------------------------------------------------------------------------- L. Allison, Dept. Computer Science, Monash University, 1994