Assignment 1

  1. Design a queue abstract data type in Java, including operations for enqueue, dequeue, and empty.

  2. Write an abstract type for complex numbers, including operations for addition, subtraction, multiplication, division, extraction of each of the parts, and construction of a complex number from two floating-point numbers. Use preferably Java.

  3. Discuss both the advantages and disadvantages of dynamic binding, from both the programmer's and the implementer's perspectives.

  4. Extend the class Stack to provide a new method called pushdown(i) that duplicates the top element and pushes the copy i elements down. Illustrate the advantages of interface inheritance and implementation inheritance using this example.

Assignment 2

  1. The read/write problem is another famous concurrency control problem. Several processes share a data object. Some processes (readers) only want to read the content of the object, whereas others (writers) want to update the content. To ensure the integrity of the shared object, we control the processes in the following way: readers can read the shared object only when no writer is updating the object; and a writer can update the shared object only when no other process is accessing the object. Give a solution to the problem in Java or any other concurrent programming language.

Assignment 3

  1. Write an one-page article to summarize the advantages and disadvantages of Prolog.

  2. Write a program in Prolog or CLP(FD) to solve the following logic puzzle taken from Logic Problems Issue 16 page 46:

    On one page of the visitor's book at Sandholme Castle, seat of the Duke of Wallingfen, were the names of ten couples from various locations in the English-speaking world who had paid to look round the ancestral pile. From the clues given below, can you fill in the blank page of the book with the surnames and home-towns of each couple?

    Clues:

    1. The Drummonds are from Edinburgh; their name appears on the line above the Jones family, who were not the last couple to sign the page.
    2. Mr and Mrs Ince's signatures are immediately followed by those of the London couple.
    3. The couple on line 3 gave a North American address; their surname contains two more letters than that of the Portsmouth pair and three more than that of the couple on line 9.
    4. Only one couple's surname initial immediately preceeds that of the next family to sign; they are not the Childers family, whose name appears on line 5 and who do not live in Melbourne.
    5. Bristol is the address on the line above Durban; one of these cities is the home of the Adams family.
    6. The Los Angeles couple signed on line 8; their surname contains an even number of letters.
    7. Mr and Mrs Fellowes, who are not transatlantic visitors, wrote their name on an odd-numbered line, unlike the couple from Wellington.
    8. The Toronto family's name immediately follows that of the Harringtons, who are not from Washington.
    9. Mr and Mrs Bourne signed on the lower half of the page, whilst the Giles family, who did not sign on line 6, are not resident in the U.K.

    London, Edinburgh, Bristol and Portsmouth are all in the U.K. Durban is in South Africa. Los Angeles and Washington (D.C.) are in the U.S.A. Toronto is in Canada. Wellington is in NewZealand. And of course, Melbourne is in Australia.

    Here is a solution: 

    
1:drummond, edinburgh
2:jones, portsmouth
3:edwards, washington
4:giles, wellington
5:childers, bristol
6:adams, durban
7:fellowes, melbourne
8:harrington, los_angeles
9:ince, toronto
10:bourne, london

    Solution
  3. Write a program in Prolog to solve the crossword puzzle (Problem C) in the problem set used in the 1999 ACM programming contest. You can use arrays in B-Prolog.
    Solution (core part)