CS 331, Programming Languages
Autumn, 2010 - 2011
Purandar Bhaduri, ext: 2360, email: pbhaduri.
1. Akhilesh Tripathi (email: a.tripathi)
2. Malti Verma (email: malti)
3. K. S. Prasad (email: k.prasad)
Ravi Sethi, Programming Languages: Concepts and Constructs, Pearson Education, 2nd Edition, 1996.
Useful additional material
2. Programming in Standard ML, online book by Robert Harper.
3. Formal Semantics of Programming Languages, Lecture Slides by Zhendong Su.
4. On understanding types, data abstraction, and polymorphism, Luca Cardelli and Peter Wegner, Computing Surveys, Vol. 17, No. 4, December 1985.
1. Glynn Winskel, The Formal Semantics of Programming Languages: An Introduction, MIT Pres, 1993.
1. Week of 16 August: Download and install ESC/Java. Try to install the second version – the command-line tool with a simple Swing GUI front-end. Learn to use ESC/Java on examples provided with the distribution. Ask the TAs for help if you face any problems.
2. Due Date: (7 September, Tuesday 5 PM)
Write a Java program for finding the maximum element of an array and use ESC/Java to analyse the partial correctness of your program. Submit your work and give a demo to the TA assigned to you. You may refer to the JML and ESC/Java tutorials in the link provided above.
3. Week of 27 September: Download and install SML/NJ if it is not already there on your machine. Read the relevant manuals and learn to use the system.
4. Due Date: (27 October, Wednesday 5 PM)
Implement the Gale-Shapley algorithm for the Stable Matching problem in ML. You can find a description of the algorithm on page 6 of Algorithm Design by Kleinberg and Tardos, Pearson Education, 2006. You may also find Section 2.3 on page 42 on the implementation of the algorithm useful. Your program should read the men’s and women’s preference lists from a file. Submit source code and sample runs to the appropriate TA and give a demo if required.
5. Due Date: (17 November, Wednesday 5 PM)
Download and install SWI-Prolog if it is not already there on your machine. You will have to implement the dynamic programming algorithm for weighted interval scheduling in Prolog in this exercise (see Kleinberg and Tardos, pages 252 - 258). Submit source code and sample runs to the appropriate TA.
Lab Assignment Policy
Late assignments would be penalised by deducting (10 × no. of days of lateness) % of the marks. Any form of copying will incur zero marks.