• Recap

    An Abstract Data Type (ADT) defines:
    A well-specified collection of data (data state)
    A set of operations that can be performed upon the data

    Abstract – does not say anything about the details of how it actually works. To use data in a program, in the form defined by an ADT, you need to have a concrete (non-abstract) implementation – a data structure.

    A data structure consists of
    A base storage method (e.g. an array, a list, a tree, a …)
    One or more algorithms that are used to access or modify that data

    In an object oriented programming language such as Java it is convenient to define a data structure as a class, which contains
    Fields to encapsulate the data state
    Methods which encapsulate the algorithms for the operations

    In Java, an ADT can be expressed as an interface which must be implemented by a class that defines a corresponding data structure.

    It is possible to have more than one implementation of the same ADT by creating classes that implement the ADT interface. A programme can be written to use the interface type, and the actual data structure can be chosen at the time the program runs – polymorphism. This is useful as you can have different implementations of an ADT each of which performs better in a specific situation. You will see examples of this later in the module.

  • Representing Time

    It is a common requirement in programs to be able to deal with information that involves time. Example: in online systems you often want to keep track of the amount of time a user spends online doing something, or waiting, and so on. Time is relatively complicated as the same point in time can be expressed in a number of different ways.

    Clock and calendar representations

    So how can we represent time? Clocks show time in hours, minutes, and some clocks show seconds also. Some clocks show 12hr time, some show 24hr time, and some give a choice between these.

    Clock Diagram
    12 hr – 8:31:30

    24 hr – 20:31:30

    Clock and Calandar Diagram
    Wed, 02 December 2015, 20:31:30

    A simpler representation

    The easiest way for a program to handle time, as an integer representing the number of seconds or minutes since a defined point in time, can be hard for the user to work with. Imagine a hospital receptionist saw a prompt like this each time a patient’s arrival time needs to be recorded:

    Enter the patient arrival time as the number of minutes since midnight:

    However, if time is represented as an integer (whole number) then many operations become easy to perform.

    Arrival time = 1234 mins


    Seen by doctor at = 1266 mins    		 What time Diagram
    Waiting time = Time seen by doctor – Arrival time = 32 mins

  • A Program That Uses Time

    Here is a simple Java program that records patient visits and calculates the average waiting time that patients have before seeing a doctor.

    public static void main(String[] args) {
    int numberOfVisits = 0;
    int totalWaitingTime = 0;
    Scanner in = new Scanner(System.in);
    String answer;

    do {
        int arrivalTime, seenByDoctor, waitingTime;
        numberOfVisits++;
        System.out.print("Enter arrival time:");
        arrivalTime = in.nextInt();
        in.nextLine();
        System.out.print("Enter time seen by doctor:");
        seenByDoctor = in.nextInt();
        in.nextLine();
        // assume that subtracting one time from another yields the
        // difference in minutes as an int
        waitingTime = seenByDoctor - arrivalTime;
        totalWaitingTime += waitingTime;

        System.out.print("Done? Enter 'Q' to quit, anything else to 
               continue: ");
        answer = in.nextLine();
    } while (!answer.equals("Q"));

    System.out.println("Number of visits: " + numberOfVisits);
    System.out.println("Total waiting time: " + totalWaitingTime + "minutes");
    System.out.println("Average waiting time: " + totalWaitingTime/numberOfVisits + " minutes");
}

    An example of a user’s interaction with this program looks like this:

    Enter arrival time: 037
Enter time seen by doctor: 0045
Done? Enter 'Q' to quit, anything else to continue: .
Enter arrival time: 0123
Enter time seen by doctor: 0145
Done? Enter 'Q' to quit, anything else to continue: Q
Number of visits: 2
Total waiting time: 30 minutes.
Average wait is 15 minutes.

    Although this program is simple to write and easy to understand, it requires the user to transform the times into minutes before entering them.

    This is a BAD idea.

    Users should be able to enter data in the form they are most comfortable with. For time this might be the form HH:MM (AM/PM). If the program is written to allow this then the user’s interaction with the program becomes more convenient.

    Enter arrival time: 12:17PM
Enter time seen by doctor: 12:25PM
Done? Enter 'Q' to quit, anything else to continue: .
Enter arrival time: 1:10PM
Enter time seen by doctor: 2:02PM
Done? Enter 'Q' to quit, anything else to continue: Q
Number of visits: 2
Total waiting time: 60 minutes.
Average wait is 30 minutes.

  • Time and Program Design

    The program designer’s goal is to meet both the needs of user and of programmers.

    We want our program to work in a manner that our users would expect and user input to be entered in the most natural way possible. We also want to make it convenient for the programmer to implement the required functionality and for this to work in an efficient way.

    Designing a Time ADT

    One way to handle Time would be to provide a Time ADT and a suitable implementation of this. Note that the Java API does provide a number of classes to represent dates and times (a useful set of these are in the package java.time) and all the complexity that these concepts involve, but here we will look at our own, somewhat simpler, representation of Time, as an example of developing a useful ADT.

    The definition of our Time ADT might include properties to hold hour, minute, seconds and am/pm values:
    probably an integer for hour, an integer for minutes and an integer for seconds
    and possibly use an enumerated type for AM/PM or just true/false

    The definition could also include operations for reading data as a user might input it and using this to set the properties of a Time object, and for subtracting them to get the difference in minutes. In fact, there could be many more operations – can you think of any others that might be useful.

    Using the Time ADT

    The users would not have to know anything about the actual class definition. They just enter time values in the form they are used to. The actual implementation of the Time ADT is hidden from them. As you saw previously, this is the idea of abstraction

    Back to the design

    Our design goal is to come up with a Time ADT that is:
    A good abstraction
    the concept is familiar to the user
    Safe
    automatically checks for bad input
    Modifiable
    changes made to the ADT won’t hurt client code
    Reusable
    many apps requiring Time can use it

    What are the
    Characteristics of ‘time’
    Operations associated with ‘time’

  • Simple Time ADT Characteristics

    Our Time ADT will be relatively simple. It will represent only hours and minutes, not seconds, and does not contain any information about the date. It will have the following characteristics:
    A Time consists of some number of hours and minutes, and is either before noon (AM) or after noon (PM)
    Twelve Noon is 12:00 PM and Twelve Midnight is 12:00 AM
    All Times are assumed to fall on the same day

    It will have operations to:
    Read a string and parse it, and to return an indication of whether this was successful
    Return the difference in minutes between a Time object and another Time object
    Return the values of each of the hours and minutes components, and whether AM or PM

    Simple Time ADT – interface

    public interface ITime {
    
    int getHour();
    
    int getMinute();
    
    boolean isAm();
    
    boolean readTime(String inputTime);
    
    int subtractTime(ITime t);

}

  • Simple Time ADT Implementation

    The methods getHour, getMinute and isAm will simply return the values of each of the hours and minutes components of the time, and whether the time is AM or PM. The other methods are a bit more complicated, and can be specified as follows:

    boolean readTime(String input)

    Precondition: input is a string representing a point in time

    Postconditions: Leading whitespace characters are ignored; readTime attempts to parse the input as a time in the format <HH>:<MM><A>, where <HH> is an integer between 1 and 12, <MM> is an integer between 0 and 59, and <A> is either “AM” or “PM”. If a properly formatted time can be read, currentTime holds read in values; otherwise, method returns arbitrary time.

    Returns: If can parse input as valid time; returns true otherwise, returns false

    int subtractTime(Time t)

    Precondition: t is a well-defined time.

    Postcondition: None.

    Returns: The difference, in minutes, between this time and t. If this time occurs before t, this difference is negative.

    We need to create the data structure class that will implement the Time ADT. This class will implement the ITime interface. We need to implement storage for the date and operations which act on the data in the form it is stored. One way to store the data that we need is to use three fields to store the hour, minute and AM/PM values.

    public class Time implements ITime {
    private int hour;
    private int minute;
    private boolean am;

    The methods getHour, getMinute and isAm will be simple getter methods for these fields.

  • Simple Time ADT Operations

    The readTime method has quite a lot of work to do. It has to:
    Split the input into parts (tokens)
    Convert the hour/minute data to integers
    Check that these integers are within range
    Check that the AM/PM value is valid
    Use the obtained values to set the field values
    Return true if all input was valid, false otherwise

    Here's a possible implementation of this:

    public boolean readTime(String inputTime) {
    StringTokenizer st = new StringTokenizer(inputTime, ": ");

    try {
        while (st.hasMoreElements()) {
            hour = Integer.parseInt((String) st.nextElement());
            minute = Integer.parseInt((String) st.nextElement());              
            if ((0 > getHour()) || (getHour() > 12) || 
                    (0 > getMinute()) || (getMinute() > 59)) {
                invalidate(); //   private method to set default values
                return false;
            }

            String ampm = (String) st.nextElement();
            if (ampm.equals("AM")) {
                am = true;
            } else if (ampm.equals("PM")) {
                am = false;
            } else {
                invalidate();
                return false;
            }
        }
    } catch (NumberFormatException e) {
        invalidate();
        return false;
    }
    return true;
}

    The subtractTime method also has some work to do. It needs to:
    Convert the hours value into a 24 hour clock value
    Get the 24 hour clock value from the Time object to be subtracted
    Calculate the total difference in minutes, taking the hours and minutes into account

    Here is a possible implementation of this:

    public int subtractTime(Time t) {
    int hour24 = hour;
    if (!isAm()) {
        hour24 += 12;
    }

    Time ta = (Time) t;
    int taHour24 = ta.getHour();
    if (!ta.isAm()) {
        taHour24 += 12;
    }

    return (hour24 - ta.getHour()) * 60 + (this.minute - ta.getMinute());
}

    Simple Time ADT – alternative implementation

    This is not the only way that the Time class could be implemented. For example, we could have chosen a different way to store the data. In this alternative version, there is only one field, containing the time data as a number of minutes since midnight. Note that the getter methods in this case have to do a little bit more work:

    public class TimeV2 implements ITime {  
    private int minutes;

   public int getHour() {
        return getMinutes() / 60;
    }

    public int getMinute() {
        return getMinutes() % 60;
    }

    public boolean isAm() {
        return getHour()<12;
    }

    The implementations of readTime and subtractTime will also be somewhat different. These are not shown here, but how do you think they would work?

  • Encapsulation and Information Hiding

    Note that a program that uses your Time class (the client program) does not need to know how either the data storage or the operations are implemented. It just needs to know that the operations are available. The ADT class encapsulates the data and hides the information about the implementation from client code.

    Time ADT Diagram

    Public
    Declares just those operations and properties the client will need
    Member functions (methods)
    Private
    Definitions of the ADT representation
    Not accessible to client code
    Data members

    There may be good reasons for implementing an ADT in a particular way:
    May be more convenient for the programmer writing the ADT code
    May give better performance

    Which version of the Time class do you think is "better"?

    Client program

    Here is a version of the patient waiting time program you saw previously, now written as a client program that makes use of our Time ADT class. Only the do-while loop is shown here as the rest of the code is unchanged. Note that this version supports the way that we want users to be able to input times.

    do {
    ITime arrivalTime = new Time();
    ITime seenByDoctor = new Time();
    int waitingTime;

    numberOfVisits++;
    System.out.print("Enter arrival time:");
    arrivalTime.readTime(in.nextLine());

    System.out.print("Enter time seen by doctor:");
    seenByDoctor.readTime(in.nextLine());

    waitingTime = seenByDoctor.subtractTime(arrivalTime);
    totalWaitingTime += waitingTime;
    System.out.print("Done? Enter 'Q' to quit, anything else to 
        continue: ");
    answer = in.nextLine();
} while (!answer.equals("Q"));

    Code reuse and Java

    A good implementation of an ADT like Time should be reusable. Any program that imports your source class and has access to the implementation can use the Time ADT

    Java terminology:
    Abstraction
    interface /abstract class / class
    Information hiding
    Encapsulation
    Code reuse

    These are the key terms used so far. You should know what each of them means and why it is important and where they can be used

  • Algorithms

    An algorithm is a plan, a set of step-by-step instructions to solve a problem.

    If you can tie shoelaces, make a cup of tea, get dressed or prepare a meal then you already know how to follow an algorithm.

    In an algorithm, each instruction is identified and the order in which they should be carried out is planned. Algorithms are often used as a starting point for creating a computer program, and they are sometimes written as a flowchart / pseudocode / structure chart / UML

    If we want to tell a computer to do something, we have to write a computer program that will tell the computer, step-by-step, exactly what we want it to do and how we want it to do it.

    This step-by-step program will need planning, and to do this we use an algorithm.

    Computers are only as good as the algorithms they are given. If you give a computer a poor algorithm, you will get a poor result – hence the phrase:

    ‘Garbage in, garbage out’

    Algorithms are used for many different things including calculations, data processing and automation.

    Representing an algorithm

    Two simple ways that algorithms can be represented –
    Pseudocode
    Flowcharts

    Most programs are developed using programming languages. These languages have specific syntax that must be used so that the program will run properly. Pseudocode is not a programming language; it is a simple way of describing a set of instructions that does not have to use specific syntax.

    Pseudo Code
    (resembling) (programming language)

    Writing in pseudocode is similar to writing in a programming language.
    Each step of the algorithm is written on a line of its own in sequence
    No real rules as it does not need to be interpreted by a computer

    In the presentations you’ll see a mix of pseudocode and Java implementations
    Pseudocode examples often conform closely to Java syntax, but typically contain one or more lines of higher-level description.
    Java implementations have actually been compiled and tested. You can tell which examples represent Java in the presentations as these are shown with coloured syntax highlighting

    Pseudocode is used to describe an algorithm which is then implemented using Java.

    In pseudocode, INPUT asks a question. OUTPUT prints a message on screen.

    A simple program could be created to take a temperature value and print a message to indicate whether this is above or below freezing. This program represented in pseudocode might look like this:

    OUTPUT 'Please enter the temperature' 
INPUT user inputs the temperature
STORE the user's input in the temperature variable 
IF temperature < 0 THEN 
OUTPUT 'Below freezing!' 
ELSE 
OUTPUT 'Above freezing!'

  • Complexity of Algorithms

    We are often interested in how complex an algorithm is – in other words, how long it will take to run

    Here is a simple algorithm, in pseudocode, that counts the number of people, N, in a room:

    LET N = 0
FOR each person in room
	SET N = N+1

    Q: How long will this take?
    A: Depends how big N is

    Here is another algorithm which also counts the number of people, N, but does it by by counting pairs of people:

    LET N = 0
FOR each pair of people in room
	SET N = N+2

    Q: How long will this take?
    A: Depends how big N is
    Q: Will it take as long as the first version?
    A: No
    Q: Does it give the correct answer?
    A: Not always? Why not?

  • Flowcharts

    A flowchart is a diagram that represents a set of instructions.

    Flowcharts normally use standard symbols to represent the different instructions. There are few real rules about the level of detail needed in a flowchart. Sometimes flowcharts are broken down into many steps to provide a lot of detail about exactly what is happening. Sometimes they are simplified so that a number of steps occur in just one step.

    Flowchart Symbols
    Name Symbol Usage
    Start or Stop Start Stop Diagram Beginning and end points in a sequence
    Process Process Diagram An instruction or command
    Decision Decision Diagram A decision, yes or no
    Input or Output Input Output Diagram Input – data received by the computer, Output – data sent by the computer
    Connector Connector Diagram Connects the symbols, showing the direction of flow

    The temperature program represented by a flowchart might look like this:

    flowchart diagram

  • Evaluating Solutions

    Before an algorithm can be programmed, it is important to make sure that it properly satisfies the problem, and that it does so efficiently.

    Think back to previous counting pairs example, although quicker to get the answer it wouldn’t be the right answer all the time

    What would you prefer: code that runs quickly or code that gives you the right answer ?

    Evaluation is the process that allows us to make sure our solution does the job it has been designed to do. Then we can think about how it could be improved.

    Once written, an algorithm should be checked to make sure it:
    is easily understood – is it fully decomposed?
    is complete – does it solve every aspect of the problem?
    is efficient – does it solve the problem, making best use of the available resources (eg as quickly as possible/using least space)?
    meets any design criteria we have been given

    If an algorithm meets these four criteria it is likely to work well. The algorithm can then be programmed. Failure to evaluate can make it difficult to write a program.

    Evaluation helps to make sure that as few difficulties as possible are faced when programming the solution.

    Dry runs

    One of the best ways to test a solution is to perform what’s known as a ‘dry run’. With pen and paper, work through the algorithm and trace a path through it. A dry run (or a practice run) is a testing process where the effects of a possible failure are intentionally mitigated.

    Dry runs are also used with completed programs.

    Programmers use dry runs to help find errors in their program code.

    For example, we have looked at a simple algorithm was created to ask for a temperature value and report whether this is below or above freezing. You could try out this algorithm – give it a dry run. Try two temperatures, 1 and -1. When using temperature 1, where does the algorithm go? Does it give the right output? If you use temperature -1, does it take you down a different path? Does it still give the correct output?

    If the dry run doesn’t give the right answer, there is something wrong that needs fixing. Recording the path through the algorithm will help show where the error occurs.

    Always have test cases for every boundary in your code.


    Test Instruction Output temperature
    Test 1 Output 'Please enter the temperature' Please enter the temperature
    User inputs the temperature
    Store the user's input in the temperature variable -1
    Check whether temperature < 0
    Output message Below freezing
    Stop
    Test 2 Output 'Please enter the temperature' Please enter the temperature
    User inputs the temperature
    Store the user's input in the temperature variable 1
    Check whether temperature < 0
    Output message Above freezing
    Stop
    Test 3 Output 'Please enter the temperature' Please enter the temperature
    User inputs the temperature
    Store the user's input in the temperature variable 0
    Check whether temperature < 0
    Output message Above freezing
    Stop

    Always test around the Boundary values of all conditions . In the example dry run above, we chose a value of temperature just above 0, one just below, and 0 itself. Is the output what you would expect for a temperature of 0? Does this suggest an improvement that could be made to the design of the algorithm.

  • Why are Data Structures and Algorithms Important

    Programmers need an understanding of how to assess costs and benefits to be able to adapt to new design challenges.

    Data structures provide a way to organise the information that programs need to store to allow them to perform their required functions. Programmers need to know how to select the best data structure for a particular application, and to implement it if it doesn't already exist.

    Algorithms provide ways for programs to perform tasks. Programmers need to know how to design an algorithm to accomplish a particular task, which may include making use of well-known algorithms for common operations.

    Data structures and algorithms are often studied together as they are closely related. The operations of a data structure implement algorithms, and the way these work depend on the way the data structure stores information. Knowledge of data structure and algorithms can allow you to improve the performance and efficiency of your programs.

    This requires an understanding of
    The principles of algorithm analysis
    How to weigh up tradeoffs
    e.g. it is quite common to reduce time requirements at the expense of an increase in space requirements, or vice versa – common in many phases of software design and implementation
    When and when not to reinvent common practice
    e.g. use of certain well known algorithms or design patterns