School of Computer Science and Software Engineering

# School of Computer Science and Software Engineering

## CITS2200 Data Structures and Algorithms

### Some animals from the complexity zoo

ALL: the class of all languages

Almost-NP: the class of languages that is in NP with probability 1, given a random oracle

BPP: The class of problems for which there is a polynomial algorithm that is correct at least 2/3 of the time.

BQP: The class of problems solveable by a quantum Turing machine in polynomial time, correct at least 2/3 of the time.

Co-NP: The complement of NP

DSPACE(f(n)): The class of problems that may be solved by a Turing machine using O(f(n)) memory.

ELEMENTARY: Problems that can be computed in n-exponential time, for some n

EXP: Problems that can be computed in exponential time

FO: Problems that can be represented in first order logic

L: Problems that may be solved by a Turing machine memory logarithmic in the size of the problem.

NP: The class of dashed hopes and idle dreams (Languages that may be computed by a non-deterministic Turing machine in polynomial time)

P: Problems that may be solved using a deterministic Turing machine in polynomial time

RE: Problems that may be solved using a deterministic Turing machine in a finite amount of time

REG: Regular languages (languages that may be computed using a deterministic finite state machine)

WHILE: A theoretical programming in which all programmes are guarenteed to run in polynomial time.

ZPP: The class of problems that is expected to be solved in polynomial time by a randomized algorithm

1. Adapted from Weiss, Exercise 3.10

A combination lock has the following basic properties:

• the combination (a sequence of three numbers) is hidden.

• the lock can be opened by providing the combination.

• the lock can be closed without requiring the combination.

• the combination can be changed, but only by someone who knows the current combination.

Imagine designing an ADT to represent a combination lock.

1. What operations would you expect of the ADT?

2. What are the pre- and post-conditions of these operations?

3. Fully specify the behaviour of the ADT by specifying the complete behaviour of each operation.

4. Write a Java interface for the ADT specified above.

2. Adapted from Sahni, Chapter 10, Question 7

Consider a double-ended queue (deque) of characters. A deque differs from a standard queue in that it allows objects to be added and deleted from both ends of the queue. Contrast this to a standard queue, where objects can only be added to the end of the queue and removed from the front.

1. Write a (non-cyclic) block implementation of the deque ADT.

2. The non-cyclic block implementation from part (a) is subject to memory erosion. Modify your code to rectify this problem by writing a cyclic block implementation of the deque ADT.

In both cases, your implementation should contain the following methods:

1. `DequeCharCyclic(s)`: create an empty deque of size `s`.
2. `isEmpty()`: return true iff the deque is empty, false otherwise.
3. `isFull()`: return true iff the deque is full, false otherwise.
4. `pushLeft(c)`: add character `c` as the left-most character in the deque, or throw an `Overflow` exception if the deque is full.
5. `pushRight(c)`: add character `c` as the right-most character in the deque, or throw an `Overflow` exception if the deque is full.
6. `peekLeft()`: return the left-most character in the deque, or throw an `Underflow` exception if the deque is empty.
7. `peekRight()`: return the right-most character in the deque, or throw an `Underflow` exception if the deque is empty.
8. `popLeft()`: remove and return the left-most character in the deque, or throw an `Underflow` exception if the deque is empty.
9. `popRight()`: remove and return the right-most character in the deque, or throw an `Underflow` exception if the deque is empty.

# The University of Western Australia

## University information

CRICOS Code: 00126G