CSE 130 
Sample Solutions: Individual Assignment 1

Problem 1
a) 
{ Type
	- primitive or composite?
	- typical operation
	- not so meaningful operation }

Boolean 
	- primitive
	- b1 AND b2 , NOT b1, b1 OR b2, IF b1 THEN x ELSE y, ...
	- b1 / b2, b1 ^ b2, ...

Char 
	- primitive
	- lowerToUpper c, is_whitespace c, ...
	- c1 minus c2, ... 

Integer 
	- primitive
	- i1 *_int i2, i1 +_int i2, i1 div i2, 
          i1 mod i2, sign i1 (i.e., +1/0/-1) ...
	- float operations 

Real 
	- primitive
	- r1 *_float r2, sqrt r1 (r1>=0),...
	- div, mod, ...

String 
	- primitive/composite (depending on the language)
	- s1 < s2, concatenate s1 s2 (in Haskell: s1 ++ s2), reverse s1, ... 
	- s1 div s2, 

Record 
	- composite
	- r.x (access argument/component x of r), r1 <> r2, ...
	- r1 / r2

Array of T 
	- composite
	- retrieve/update a[i], sort asc/desc a, search x in a[..]
	- a1 mod a2

Set of T 
	- composite
	- s1 UNION/INTERSECT s2, s1 MINUS s2, MEMBER x IN s1...
	- sort s1 (no order is assumed on sets...)

Associative Array from T1 to T2
	- composite
	- return/update a.k (operate on value of key k in assoc array a)
	- sqrt a


b) 
String: 
	Integer -> Char 
or	[Char]

associative array from string to integer: 
	String -> Integer

Array of Records: Te -> (Real x String)


Problem 2:
a) 
Leaf = String
Innernode = string x (Tree1 x Tree2 x ... x Treek)
Tree = Leaf | Innernode

alternatively: in Haskell:
Tree = Leaf String | Innernode String [Tree]

b)
{ Lots of answers different answers can be given here. Here an example
from a student...} 

(JAVA implementation)

public class Tree {
  private final static int K=?; //number of child nodes per inner node
  private Tree[] children; //leaf nodes have all children[i] values set to null
  private String tag;
 
  public Tree(String newTag) {
	tag = newTag;
	children = new Tree[K];
  }

  public void addChild(int childNum, Tree child) {
	children[childNum] = child;
  }

  public void deleteChild(int childNum) {
	children[childNum] = null;
  }
}

Usage:
To create a tree:	n1
		       /  \
		      n2   n3

Tree n1 = new Tree("root");
Tree n2 = new Tree("lchild");
Tree n3 = new Tree("rchild");
n1.addChild(0,n2);
n1.addChild(1,n3);