Week 2

Reading

Chapters 1-2 in GT give an overview of Java. We will not go through these chapters but you can use them as a reference and a review of what you learned in your previous Java course. The lectures during week 1 and 2 cover material from chapter 4 (time analysis), 3 (arrays and linked lists), 5-6 (stacks, queues, iterators), 7 (trees), and 8 (priority queues).

Sections 3.4, 5.3, 6.2, 6.4, 6.5, 8.3.6 and 8.4 are less important than the others.

Recommended exercises

Numbers refer to GT 4th edition (numbers within parentheses refer to the 3rd edition).

R-3.7 (R-4.14), R-3.8 (R-4.15), C-3.9 (C-4.5), C-3.10 (C-4.11)
R-4.6 (R-3.2), R-4.11 (R-3.7), R-4.15 - R-4.23 (R-3.25 - R-3.29, R-3.9, R-3.11 - R-3.13), R-4.34 (R-3.30), R-4.37 (R-3.33), C-4.5 (C-3.1), C-4.13 (C-3.6), C-4.15 (C-3.12).

Homework for 3 November

Problem C-4.20 (C-3.17).

The problem is to describe in pseudo-codea method for multiplying an n x m matrix A and an m x p matrix B. Recall that if C is the matrix product of A and B, then C[i][j] is the sum of A[i][k] x B[k][j] for all k = 1, ..., m.

You should be prepared to present your solution in class.

Homework for 6 November

One way to represent finite sets is by sorted lists without duplicates (cf lab 1). Write Haskell functions which implement some basic functions on sets! To start with we make life simple by considering lists of integers only.

Haskell modules can be used for specifying abstract data types in a similar way as interfaces are used in Java. (Another option is to use Haskell's classes.). Your task is to write a Haskell module for an abstract data type of finite sets with three functions. Here is how you write the module head and the definition of integer sets as integer lists

< module IntSet ( IntSet, -- the type of sets of integers member, -- Int -> IntSet -> Bool union, -- IntSet -> IntSet -> IntSet subset -- IntSet -> IntSet -> Bool ) where type IntSet = [Int] ...

Replace the "..." above by suitable implementations of the functions member, union, and subset.

In Bror Bjerner's notes you can find several examples of how modules can be used for specifying abstract data types. Look for example at the module Stack in chapter 3.

Try to make the functions as efficient as possible! What are the asymptotic complexities (using O)? Does it make sense to implement the membership function by binary search here?

You should be prepared to present your solution in class.

module	IntSet (
	IntSet,	-- the type of sets of integers
	member,	-- Int -> IntSet -> Bool
	union,	-- IntSet -> IntSet -> IntSet
	subset	-- IntSet -> IntSet -> Bool