Programming Assignments for CSL102

Assignment-1 |Assignment-2|Assignment-3 |Assignment-4 |Assignment-5 |Assignment-6 |Assignment-7

Assignment-1

(non-credit)
  1. Learn how to login, logout and change your password
  2. Learn some basic Unix commands.
  3. Learn how to use an editor in the Unix environment. You may use any editor of your choice. The native Unix editor is called vi. Download tutor.vi and go through interactive tutorial lessons to learn the usage of the `vi' editor.
  4. Learn how to use the mailer to read and send emails.
  5. Send an email to the course instructor with subject "CSL102"
  6. Learn how to use a browser to access the CSL102 home page.
  7. Type in the two programs here and learn how to execute them in the SML interactive environment.

Assignment-2

(non-credit)
  1. Learn the basics of Unix. Unix tutorial for beginners is a good place to start.

Assignment-3

Develop ML functions for the following problems.

  1. Computing factorial of a given integer using both recursive and iterative procedures.
  2. Computing x^n in O(n) time. Write both recursive and iterative versions.
  3. Computing x^n in O(log n) time. Write both recursive and iterative versions.
  4. Computing the nth fibonacci number. First use the algorithm given by the following functional description: fib(1) = 1; fib(2) = 1; fib(n) = fib(n-1)+fib(n-2) for n > 2. Also develop O(n) and O(log n) iterative algorithms for the same problem.
  5. The integer square root of n is the integer k such that k^2 <= n < (k+1)^2. The integer square root can be computed using the following inductive process:
    1. Compute the integer square root i of m = n div 4 recursively. We then have that i^2 <= m < (i+1)^2.
    2. Since m and i are integers we have that (m+1) <= (i+1)^2. We thus have (2i)^2 <= 4m <= n < 4m + 4 <= (2i + 2)^2. Hence we have that the integer square root of n is either 2i or 2i+1.
    Write a recursive ML program corresponding to the above algorithm. Indicate the type of the function and derive the number of steps required.
  6. Study the problem of computing perfect numbers from the the lecture notes (Example 3.13) and implement the ML program. Also study the following discussion on scope rules. You will be questioned on this problem during the demonstration.
  7. Solve the problems of Minor 1 from last year and write the programs.
For each of the above algorithms analyze the correctness using Principle of Mathematical Induction and estimate the time and space complexities. Verify the theoretically estimated time complexities by actually executing the programs. Show that if you double the problem size then the execution time scales as predicted by your theoretical analysis. You can use the function timer.ml to measure the execution time of a program.

Last date of submission: Aug 20. Please submit your assignment after logging in with your IITD userid and password at https://sakai.iitd.ac.in. You can write your analysis as comments withing your programs. Please put all your programs and analysis in a single folder and submit a tarball of your folder. Click here for help on making a tarball.

Please submit a partially completed version of your assignment in case you have not been able to complete it. You can complete and submit again by Aug 27. There will no penalty for late submission till Aug 27. Multiple resubmissions are allowed.

Assignment-4

See here. Please submit your assignment after logging in with your IITD userid and password at https://sakai.iitd.ac.in.

Assignment-5

Study the documentation in An Informal Introduction to Python - Python v2.6.1 documentation and The Python Tutorial - Python v2.6.1 documentation just enough to be able to program the following array based problems:
  1. The searching and sorting methods discussed in the class: Sequential search, Binary search, Selection sort, Bubble sort, Insertion sort, Merge sort and Quick sort. Click here for a graphical illustration of the sorting methods discussed in the class

  2. The Sieve of Eratosthenes, as discussed in the class.
Please don't get lost in syntax issues and concentrate on the algorithmic aspects. Please write the necessary assertions and invariants. Also, prepare a table comparing the execution times of the sorting algorithms for array sizes ranging from 100 to 10^6. Do you see the the theoretically predicted speed ups? If not, please exlain why not? Please submit a single tarball (tar.gz file) for your submission.

Please submit your assignment after logging in with your IITD userid and password at https://sakai.iitd.ac.in. The expected date of submission is October 12, 2012.

Assignment-6

Use the higher order function for depth first search developed in the class to solve the problems of Subset sum and Knight's tour. You can get 5 additional bonus marks if you can also throw in Stable marriage. The last date for submission will be November 4.

Assignment-7

Assignment 7 is on numerical pitfalls. Try to work out as many problems as you can. Don't be alarmed or dismayed by the large number of problems, please first read them thoroughly. All these problems will require short programs and the assignment should not take long to complete.

You may do the necessary derivations on paper and show them to the instructor during demonstration. Please only submit Python demo codes which step through plots and comments. An example will be up here soon.

The last date for submission: November 15.

Subhashis Banerjee / Dept. Computer Science and Engineering / IIT Delhi / Hauz Khas/ New Delhi 110016 / suban@cse.iitd.ac.in