1. Get user accounts on ccsun50 (see you medical booklet for account and initial password)
2. Learn to connect to ccsun50 (IP address given on medical booklet sticker)
3. Change password to a safe password. Do not tell anyone including TA and instructor what it is.
4. Disconnect and reconnect to ccsun50
5. Learn to use the Unix shell commands: ls, mkdir, cd, ...
6. Learn to create a file using emacs or vi or pico
7. Learn to invoke sml (need to set up path variables)
8. Read course web page
9. Send mail to your TA (find his or her email address from home page).

1. Try out all the SML programs discussed in class: unary notation natural numerals nat, the value of a nat, successor, addition, multiplication and exponentiation, the BoolExp data type, and the truth function.
2. Define a function complement which takes a BoolExp and returns the BoolExp that is the negation of the given BoolExp using DeMorgan's laws.
3. Define a function equiv that given two BoolExp's determines if they are equivalent boolean expressions (have the same truth value).
4. Define a recursive function size that counts the number of constants (T or F) and connectives (Conj, Disj, Neg, Implies) in an input BoolExp.

1. Try out all the SML programs discussed in class: lists of integers, list of other types; length, head, tail of lists, summation, product.
2. Define a function max that given a list of non-negative integers, returns the largest integer in the list. What should max return when given the empty list? (Note: think of max as a generalization of a two-way comparison "greater than or equal")
3. Define a recursive function eq_length that given two lists determines if they are of the same length. Can the two lists be of different types? Does one need to determine the length of the two lists if the answer is true? What if the answer is false?
4. Define a recursive function shuffle that given two lists L1 and L2, returns a list that consists of the first element of L1, then that of L2, then the second element of L1, then that of L2 and so on. Should the input lists be of the same type? What should one do if one of the lists is exhausted?

We move to the next level in our course. You will have to do two kinds of activities -- building packages based on the exercises, examples etc. done in class, as well as a "project" type assignment.

1. Complete the programs related to lists discussed in class.
2. Implement a package for sets represented as lists. You should implement the following functions on sets:
   • empty which returns true if the given set is empty.
   • member which returns true if the given element is in the given set.
   • union
   • intersection
   • difference
   • powerset
   • cartesian which implements the cartesian product of two given sets.
   It is a good idea to use curry-ed forms for implementing these function. Also you MUST write down a representational invariant, and specifications for each function, checking that the representational invariant is maintained. Also try to profile the efficiency of the programmes.
3. We will start implementing Tic-Tac-Toe, or "Noughts and Crosses", a game played on a 3X3 grid, in which two players write X and O respectively in the empty squares, with the objective being to get three symbols of the same type in a row or a column or a diagonal.
   • Design a datatype for the contents of the square (X, O or empty)
   • Represent the 3x3 grid using lists
   • Write a routine for displaying the grid
   • Write a program to fill in a given symbol (X/O) in a given square (whose index (i,j) is given, disallowing overwriting of one symbol by another.
   • Write a function that checks if a row or column or diagonal is filled with the same symbol
   • Write a function that implements strict alternation of turns of the players
   It is necessary to completely document your program. You MUST write down a representational invariants, and specifications for each function, checking that the representational invariant is maintained, characterize valid configurations, winning configurations etc. Also try to profile the efficiency of the programmes.

We will now represent m X n matrices of real numbers (the ML type is real) as lists of m (row) lists, each of which has n entries.

You have to implement a Matrix package, where you support the following operations:

1. similar: Determining if two given matrices are of the same dimensions m X n.
2. Finding if a matrix is square.
3. Adding two matrices (if they are of similar dimension, raising an exception otherwise)
4. Returning Identity (square) matrices of a given dimension.
5. Scalar multiplication of a matrix by a real constant
6. Determining if two matrices A and B are compatible for being multiplied.
7. Multiplying two given matrices (if compatible, raising an exception otherwise).
8. Finding if two matrices are equal
9. Finding the determinant of a matrix
10. Finding, if it exists, the inverse of a matrix.

Remember to write an appropriate signature, and present your programs as a structure.

Continue the Tic-Tac-Toe problem with trying to integrate all you did the previous week to implement a computer supported two-player game, where a winning position is detected automatically.

Start thinking of how you will implement strategies for a player-vs-computer version of Tic-Tac-Toe. Think of efficient data structures for maintaining likely positions for putting a symbol to win or prevent the other from winning.

First of all, you must complete and demonstrate the Tic-Tac-Toe game to the TAs. Failure to do so this week means no marks for this assignment.

Programs on trees

Implement a Bintree package for binary trees, giving a signature and appropriate structure, in which the following operations are supported:

1. a parameterized datatype 'a bintree
2. height of a tree, as discussed in class.
3. numnodes which finds the number of nodes in a given tree
4. maptree, as discussed in class
5. ziptree, which given an 'a bintree and a 'b bintree that are of exactly the same shape, returns an ('a*'b) bintree and an exception NotIsomorphic otherwise.
6. foldtree, discussed in class as foldtreer
7. preorder pre-order traversal of the tree, returning a list, as discussed in class.
8. inorder in-order traversal of the tree, returning a list, as discussed in class.
9. postorder post-order traversal of the tree, returning a list, as discussed in class.
10. find that given a value x and a tree t returns true if x is in t and false otherwise.

Extend the Bintree structure to implement height-balanced trees. You have to implement the following functions:

1. checkbalance, which given a tree, returns true if it is balanced and false otherwise.
2. balpre, that given a list, constructs a height-balanced tree such that its preorder traversal gives the original list, as discussed in class.
3. balin, that given a list, constructs a height-balanced tree such that its in-order traversal gives the original list.

We will extend this structure later to deal with insertion, deletion and other operations while maintaining the balanced tree property.

Define a structure IntBintree which specializes the Bintree package to int bintree and provides additional functions:

1. sumtree adds all the elements in the tree.
2. maxtree returns the largest element in the tree.
3. sumpaths that given a tree, replaces each Leaf by a node containing the sum of all the values on the path from the root of the tree to that leaf.

Implement a PrioQueue package for priority queues, giving a signature and appropriate parametrized structure (called a functor), based on a given structure Order that satisfies the signature ORDER, in which the following operations are supported:

1. a substructure Order of signature ORDER that is a total ordering;
2. a datatype heap that holds items of the type t; within the structure Order satisfying the signature ORDER
3. emptyHeap which creates an empty heap.
4. nullHeap which returns true if a given heap is empty and false o therwise.
5. min which returns the least element in the heap
6. insert that takes an item and a heap and returns a heap which satisfies the height-balance and heap properties.
7. delmin which removes the minimum element from a given heap
8. fromList which creates a heap from a given list
9. toList, which creates a list from a given heap
10. sort which sorts a given list according to the comparison operation given in structure Order by creating a heap and then converting it to a list.

Implement using PrioQueue a discrete event scheduler that works as follows.

1. Implement a random number generator joblength that randomly generates positive integers in a particular range (say, 0..100). These are to intended to be the time durations of some jobs to be done.
2. Implement using a suitable random function arrivals in a small range say (0..4) that gives the number of new jobs that arrive while the current job is executing.
3. Implement schedule that will select the job that has the smallest duration; when this job completes, we will insert all the jobs that have arrived in this interval (by calling joblength as many times as given by arrivals, and getting suitable durations for each new arrival. Also record together with each inserted item the "time" at which it arrived (for simplicity all new arrivals are inserted at the time the previously scheduled job completes).
4. You should return a list that records the time instant at which schedule iscalled, the number of waiting jobs (size of heap), and the time spent waiting in the priority queue by the selected job (current time - time it was inserted).
5. Run your scheduler for a suitable long duration (say 40,000 or more), and calculate average waiting time, and average queue length.

Diwali week, mostly holidays: Completion of previous assignment.

Completion of previous assignment.

Implementation of Sequence structure and its applications.

1. Implement all the programs on sequences given in class.
2. Sieve of Eratosthenes for generating primes
3. Series expansions of various transcendental functions. Taylor and/or MacLaurin Series expansions. Your choice of at least five different expansions.

Numerical programs (not using sequences)

1. Implementation of a Random Number Generator
2. Solving x^2 = a using Newton Raphson method and Bisection method
3. Generalization of the above, where the next approximation function and termination conditions are parameter functions.
4. Variant using different next approx and termination conditions from those given in class example.

Completion of previous assignments

Gaussian Elimination

1. Implementation of Gaussian Elimination as discussed in class. Give various sets of inputs and check the solutions.
2. Write a program to determine whether a set of n equations in n variables is linearly independent or not.