The University of Western Australia
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.


School of Computer Science and Software Engineering

University information

CRICOS Code: 00126G

This Page