CS 331,
Programming Languages
Autumn, 2008  2009Instructor Purandar Bhaduri, ext: 2360, email: pbhaduri. Textbook Teaching Assistants SHOBHIT AGARWAL (email: shobhit) KAPIL KUMAR CHITTORA (email: k.chittora) C. SURENDRANATH CHOWDARY (email: c.chowdary) PRAVEEN MOPARTHY (email: p.moparthy) Useful additional material 1.
Semantics of
Programming Languages. Lecture Notes by Nick Benton. 2.
Formal
Semantics of Programming Languages, Lecture Slides by Zhendong
Su. 3.
Programming
in Standard ML, online book by Robert Harper. 4.
On understanding types,
data abstraction, and polymorphism, Luca Cardelli
and Peter Wegner, Computing Surveys, Vol. 17, No. 4, December 1985. Reference Books 1. Glynn Winskel, The Formal Semantics of Programming Languages: An Introduction, MIT Pres, 1993. Lab Exercises 1. Week of 25 August 2008: a. Download and install ESC/Java as an Eclipse plugin from http://jmleclipse.projects.cis.ksu.edu/docs/escjava.shtml. Alternatively, if you face problems with the site, try the instructions at http://www.cs.virginia.edu/cs201j/plugin/ . b. Alternatively, you may download other versions of the tool. See details at http://kind.ucd.ie/products/opensource/ESCJava2/. c. Go through the documentation and run ESC/Java on small examples. 2. Lab Exercise 1: Due 10 October, Friday Write simple Java programs for the following examples presented in the class and use ESC/Java to analyse the partial correctness of your programs. Submit your work and give a demo to the TA assigned to you. a. The greatest common divisor of two positive integers. b. The quotient and remainder of two positive integers. 3. Lab Exercise 2: Due 24 October, Friday Download and install SML/NJ. You will have to implement a data type in ML for representing arbitrary trees, where a node can have an arbitrary number of children and an integer valued field. Then implement the following algorithms in ML. The output should print out the values of the nodes in the traversal. Submit source code and sample runs to the appropriate TA. a. Algorithms for depthfirst and breadthfirst traversal of an input tree. b. An algorithm for preorder traversal of an input tree. 4. Lab Exercise 3: Due 14 November, Friday Download and install SWIProlog if it is not already there on your machine. You will have to implement the FloydWarshall algorithm for the all pairs shortest path problem (see Section 25.2 on pages 629 onwards in Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein). Assume that the input graph is represented using the predicate edge(X,Y,N), meaning there is an edge from node X to node Y whose cost is N. Submit source code and sample runs to the appropriate TA. 
