Transcript Programming & Data Structures

GRIFFITH
COLLEGE
DUBLIN
Data Structures, Algorithms &
Complexity
Introduction
Dr Kevin Casey BSc, MSc, PhD
[email protected]
Lecture 1
1
Course Format

Twelve weeks

Two lectures and one tutorial per week

Assessment is 50% exam and 50% continuous
assessment

We will be using the Java programming language

Lecture notes will cover most of the material

Recommended reference texts will be in the library
Lecture 1
2
Why Data Structures?

Professor Niklaus Wirth – Algorithms + Data Structures =
Programs

What is a computer program?

A series of operations carried out on data



We are always seeking to write better, more efficient, faster,
more understandable, or in other words, better quality programs
The operations we carry out on data both affects, and is
affected by, the way we structure the data in the computer.
We want to study how to develop good data structures and
good algorithms
Lecture 1
3
Good Programs




Programs which don't run correctly are of little use.
Programs need to run efficiently. This is usually understood to
mean in the minimum time - but occasionally there will be other
constraints, such as memory use
Better running times will generally be obtained from use of the
most appropriate data structures and algorithms
This course will focus on solving problems efficiently: you will be
introduced to a number of fundamental data structures and
algorithms (or procedures) for manipulating them.
Lecture 1
4
Efficient Solutions

Failed software is hugely expensive

There is an enormous amount of bad software in circulation

We will study well-known solutions to well-known problems


Using these techniques will mean that not only do you produce
correct and fast programs in the minimum time, but you make
you programs easier to modify
Another software engineer will find it much simpler to work with
a well-known solution than something that has been hacked
together and “looks a bit like” some textbook algorithm
Lecture 1
5
Abstraction




A modular approach to problem solving is a tried and
tested technique
We need a formal basis for partitioning our large task
into smaller ones.
The notion of abstraction is extremely useful here
Abstractions are high level views of objects or
functions which enable us to forget about the low
level details and concentrate on the problem at hand
Lecture 1
6
Example






What data is important in order to solve the problem at hand?
We wish to store information in relation to a person. What is
important?
 Name? Gender? Social Security Number? Eye colour?
It depends on the application
If developing a medical diagnostic system we will ‘abstract’
particular data that is of use.
If developing a Student information system for the college we
will ‘abstract’ different data.
The view we take is called an ‘abstraction’.
Lecture 1
7
Algorithms




An algorithm is any well-defined computational procedure that
takes some value, or set of values, as input and produces some
value, or set of values, as output
An algorithm is a series of operations performed on data to
achieve a set goal
 E.g. Unsorted input – sort the data – sorted output
We can also view an algorithm as a tool for solving a wellspecified computational problem
The analysis is language independent and in the notes we will
use pseudocode
Lecture 1
8
Pseudocode

Indentation indicates block structure
Fib(F, x)
F[0] = 0
F[1] = 1
for i = 2 to x
F[i] = F[i-1] + F[i-2]
endfor
endalg

I will introduce the conventions during lectures
Lecture 1
9
Data Structures





A Data Structure is a model of how we store
individual pieces of data. A set of data items
Sets are as fundamental to computer science as they
are to mathematics
The sets of data manipulated by algorithms can
grow, shrink, or otherwise change over time
We call such data sets dynamic
Operations on a dynamic set can be grouped into two
categories: queries, which simply return information
about the set, and modifying operations
Lecture 1
10
Typical Operations




Search(S, x)
 Given a set S and a reference x to an element in S, return
the position of x or nil if no such element is found
Insert(S, x)
 Add the element x to the set S.
Delete(S, x)
 Remove the element x from the set S.
Minimum(S)
 Given a totally ordered set S return the element of S with
the smallest value
Lecture 1
11
Typical Operations



Maximum(S)
 Given a totally ordered set S return the element of S with
the largest value
Successor(S, x)
 Given an element x from a totally ordered set S, return the
next element in S, or nil if x is the last element
Predecessor(S, x)
 Given an element x from a totally ordered set S, return the
previous element in S, or nil if x is the first element
Lecture 1
12
Operations on Data Structures




Why are we interested in whether an operation
queries the set, or modifies the set?
We have looked at these operations in the Abstract.
What do they mean in particular situations?
E.g. The data set of BSc students. How would we
apply each of the operations outlined?
Are there other issues we need to consider?
Lecture 1
13
Comparing Efficiency



The steps we take to carry out the function
constitutes the algorithm
We could solve the same problem using different
steps
If two algorithms perform the same task in different
ways, can we say one is ‘better’ than the other?

What do we mean by ‘better’?

Effectiveness versus Efficiency
Lecture 1
14
Questions

This module interested in questions.

How we decide what data we need?

How we decide to store that data?



How we manipulate that data to achieve certain
results?
How we decide on the ‘best’ way to manipulate the
data?
How we compare different answers to the above.
Lecture 1
15
Summary

Computing Science is about problem solving.

How do we represent problems?

How can we improve our results?

We store the information in Data Structures.

We solve the problems using algorithms.

We judge our results based on analysis of complexity
Lecture 1
16