CS1ADS: Algorithms and Data Structures

Coursework 3

Issue date: 2000.02.11

Submission date: 2000.02.25

In order to pass this coursework, you must submit and pass all questions.

Questions that require a program to be written should result in one or more files with a .java extension, all comments should be embedded in the files (with particular emphasis on documentation comments). Questions that require an essay to be written should result in a single file that is one of: a Word file (.doc extension), a FrameMaker file (.fm extension), a LATEX2e file (.ltx extension), an HTML file or a plain ASCII text file (.txt extension).

Question 1

The piece of code that is obtained by clicking here computes something.  Analyse and document this poor piece of coding so as to make it presentable.  What does this program compute and how does it do it?  What is the time and space complexity of the code?  Is there any change to the code that would make it simpler and/or more efficient?

Question 2

In mathematics, the factorial function is represented by a postfix exclamation mark and is usually defined by the equations:
0! = 1
n! = n.(n-1)!     where n > 0
Construct recursive and iterative implementations of the factorial function.  Write a short essay analysing the difference between the recursive and iterative approaches, including time and space complexity issues.  You should consider whether factorial(15) and factorial(24) are calculated correctly in your implementation.

Question 3

ADS, JGL and Collections all have an array type (Array, Array, ArrayList respectively) and a doubly-linked list type (DLList, DList, LinkedList respectively). Create a program (or programs) to test these implementations' performance using indexing and iterators.

Russel Winder
Last updated: 2000-02-10