CMP305B: Algorithms

Prof. Aminu M. Bui

Outline
 Introduction
 Algorithms as opposed to programs
 Fundamental Questions about
Algorithms
 Data structures, abstract data types
Introduction
 The course cover the key ideas involved in designing
algorithms.
 Dependence on suitable data structures
 How some structures and algorithms are more efficient than
others for the same task.
 We will concentrate on a few basic tasks, such as storing,
sorting and searching data
 We will start by studying some key data structures, such as
arrays, lists, queues, stacks and trees, and then move on to
explore their use in a range of different searching and
sorting algorithms.
 We will investigate the computational efficiency of the
algorithms we develop.
 No restriction to a particular programming
Algorithms as opposed to
programs
 An algorithm for a particular task can be defined as “a finite
sequence of instructions, each of which has a clear
meaning and can be performed with a finite amount of
effort in a finite length of time”.
 As such, an algorithm must be precise enough to be
understood by human beings.
 May be in plain English, but often in pseudocode
 However, in order to be executed by a computer, we will
generally need a program that is written in a rigorous formal
language; and since computers are quite inflexible compared to
the human mind, programs usually need to contain more details
than algorithms.
Fundamental questions about
algorithms
 Given an algorithm to solve a particular problem, we are
naturally led to ask:
 1. What is it supposed to do?

 2. Does it really do what it is supposed to do?

 3. How efficiently does it do it?

 The technical terms normally used for these three aspects are:
 1. Specification

 2. Verification

 3. Performance analysis
Fundamental questions about
algorithms
 The specification should formalize the crucial details of the
problem that the algorithm is intended to solve.
 Verification involves making sure an algorithm satisfies its
specification
 For simple problems, it is often easy to see that a particular
algorithm will always work
 However, for more complicated specifications and/or algorithms,
the fact that an algorithm satisfies its specification may not be
obvious at all.
 In this case, we need to spend some effort verifying whether the algorithm
is indeed correct.
 In general, testing on a few particular inputs can be enough to show that
the algorithm is incorrect. However, since the number of different potential
inputs for most algorithms is infinite in theory, and huge in practice, more
than just testing on particular cases is needed to be sure that the algorithm
satisfies its specification.
 We need correctness proofs.
Fundamental questions about
algorithms
 Finally, the efficiency or performance of an algorithm relates
to the resources required by it, such as how quickly it will run,
or how much computer memory it will use.

 This will usually depend on the problem instance size, the

choice of data representation, and the details of the
algorithm. Indeed, this is what normally drives the
development of new data structures and algorithms.
The Concepts of Arrays
 a data structure
 an ordered set of homogeneous
data
 primitive data types (e.g. int, float)
 OR references to objects

…
1st 2nd … nth
component
Arrays in Java
 arrays are Java objects
 has attributes & methods attached
 created by the new operator
 but NOT via a constructor
 i.e. NO “()”
 instead, you have a pair of square
brackets
 i.e. “[]”
When to Use Arrays?
 when all items are homogeneous
 i.e. of the same type
 need fast access to individual item
 because components are stored in a
continuous piece of memory
 the maximum size is known
 items need to be ordered
How to Use Arrays?
 involve 3 steps:
 declare array
 i.e. attribute/ variable declaration
 create/construct array object
 i.e. calling “new” with an array size
 access array component(s)
 i.e. read/ write
Step #1 - Array Declaration
attribute/
int[] daysInMonth; variable
declaration,
String month[]; no size
specified
char myCharArray[];
 “[]” go after data type/ variable name

 you declare an attribute/ variable that

will hold a reference to an array object
 NOT yet the array itself
Step #2 - Array Creation
 before an array is created the array
reference points to nothing (i.e.
null)
 to create an array:
 specify the array size
 need not known until runtime
 once you created an array, you
cannot change its size (i.e. length)
Array Creation Examples
 use the new operator to create the
array object
 assign object reference to array variable

myCharArray=new char[100];
daysInMonth=new int[12];
month=new String[12];
 Note
 you use “[]” instead of “()”
Shortcut to Array Creation &
Initialisation
declaration, creation & assignment in
one line
int[] prime={2,3,5,7,11,13};
index value
prime

0 1 2 3 4 5

2 3 5 7 11 13
1st 2nd 3rd 4th 5th 6th
element
Step #3 - Accessing Array
Elements
 use the “[]” to specify the index
 index value ranges from 0 to "length-1"
 get value of an array component
month[10]
 assign value to an array component
month[0]="January";
 a "for" loop is usually used to process
array components
 Graphical Representation of an
Array of String

month "January" 1st component

"February" 2nd

String[] month;
month=new String[12];
month[0]=“January”;
month[1]=“February”;
…
"December" 12th
Array Size
 each array has a "length" attribute
 "length" is an attribute, not a method!
 so NO brackets “()”
 the following code scans the whole
array and prints out each component:
for (int i=0;i<month.length;i++)
System.out.println(month[i]);
Copying Arrays
 array variables hold object references
 assigning 1 array variable to another
make them point to the same array
object
NOT copying!
 p1 2 3 5 7
int[] p1={2,3,5,7};
p2
int[] p2=new int[4];
p2=p1;
How to Copy an Array Properly?
 you can copy the components 1 by 1
 use a "for" loop
int[] p1={2,3,5,7};
int[] p2=new int[p1.length];
for (int i=0;i<p1.length;i++)
p2[i]=p1[i]; p1 2 3 5 7

p2 2 3 5 7
How to Copy an Array Properly?
(approach #2)
 Array inherits the "clone()" method
from the Object class
int[] p1={2,3,5,7};
int[] p2=(int[])p1.clone();
 "clone()" returns an Object, need to
cast it to a "int[]" type
Limitations of Arrays
 you cannot expand an array
 size is fixed on creation
 order of components is fixed
 you may shuffle them
2D Arrays
 distance between 2 cities
Sokoto B/Kebbi Gusau Kaduna

Sokoto 0 153 207 463

B/Kebbi 153 0 338 616
Gusau 207 359 0 257
Kaduna 463 616 257 0
2D Arrays (cont'd)
int distance[][]=
{ {0,153,207,463},
{153,0,338,616},
{207,359,0,257},
{463,616,257,0}
};
String town[]={“Sokoto",
“B/Kebbi",“Gusau",“Kaduna"};
2D Arrays (cont'd)
int t1=0,t2=3; //Sokoto and
Kaduna
int d=distance[t1,t2];
System.out.println("Distance
between "+town[t1]+" and
"+town[t2]+" is "+d+" KM");
Multiple Dimensional Array
 a component can be another Array
 whose components can be another
Array
Common Mistakes Using
Arrays
 size must be >=0
 don't confuse component type with
array reference type
 you cannot use an array reference
before an array is created (i.e. not
before calling "new")
Common Mistakes (cont'd)
 length is an object-level
attribute/variable, not a method
 defined for each array object
 length cannot be changed by assignment
 no need to pass the length of array
 index must be in the range 0..length-1
 or you'll get an
ArrayIndexOutOfBoundsException
Abstract Data Types
 follow the principles of:
 data abstraction
 encapsulation
 information hiding
 you don't need to know how things are
implemented
 only need to know how to use them!
 specified by operations (i.e. methods)
Abstract Data Types (cont'd)
 "interface" (i.e. data & behaviours
which are accessible) remains the
same even if implementation has
changed
 define your classes this way
 so that changing the internal of your
classes will not affect the others
Containers
 an object that holds a collection of
other kinds of objects
 different kinds of containers
 some allow duplicates
 some are ordered
 examples of Abstract Data Types in Java
Arrays as Containers
 simple data structure
 disadvantages
 fixed size
 inserting is difficult
 the java.util.Arrays class have
methods defined to perform:
 sort
 binary search (on sorted arrays)
Array Sorting Example
import class from
import java.util.Arrays;
a different
public class SortExample package
{ public static void main(String argv[])
{
int[] a={3,2,1,10,7,9,5,8,4,6};
Arrays.sort(a); calling a
for (int i=0;i<a.length;i++) class-level
method
System.out.println(a[i]);
} //end method main
} //end class SortExample
Binary Search Example
import java.util.Arrays;
public class BinarySearchExample
{ public static void main(String argv[])
{
int[] a={3,2,1,10,7,9,5,8,4,6};
Arrays.sort(a);
System.out.println(Arrays.binarySearch(
a,7));
} //end method main
} //end class BinarySearchExample
Other Members of the Java
Collections Framework
 defined in the java.util
package
 behaviour defined by 3

interfaces
 java.util.List define a set of methods
that the implementing
 java.util.Set classes MUST defined/
implement
 java.util.Map
The java.util.List
Interface
 duplicates allowed
 ordered
 no maximum limit
 some concrete classes implementing
the java.util.List interface:
 java.util.Vector
 java.util.ArrayList
 java.util.LinkedList
java.util.List (cont'd)
 each node stores an Object
 implement a linked-list
 can add to beginning/end of list
...
java.util.List Example
import java.util.*;
public class Test
{
public static void main(String argv[])
{
List x=new LinkedList();
x.addFirst("hello");
x.addLast("world");
} //end method main
} //end class Test
The java.util.Set
Interface
 no duplicates (because it is a set!)
 un-ordered
 you can
 add/remove element
 check membership/existence of an

element
 find the size of set (i.e. no. of

elements)
java.util.Set (cont'd)
 2 implementations: HashSet,
TreeSet
Set x=new TreeSet();
x.add("Hello");
x.add("World");
System.out.println(x.contains("Hello"));
x.remove("Hello");
System.out.println(x.contains("Hello"));
The java.util.Map
Interface
 key-value pairs
 e.g. a phone directory
 each key must be unique
 2 implementations: HashMap, TreeMap
 main operations:
 add/remove a key-value pair
 look up using key
 get all keys
java.util.Map Example
Map directory=new HashMap();
directory.put(“Bello","262626");
directory.put(“Bala","264321");
String
phone=(String)directory.get(“
Bello");
The java.util.Iterator
Interface
 allow iteration through all elements in a
list/set
 like a "for" loop in an array
 the iterator() methods returns an
Iterator object
 use hasNext() to test for existence of
next element
 use next() to get next element (if exists)
Iterator in a List
Collection c=new LinkedList();
... //add some elements into c
Iterator i=c.iterator();
Object x;
while (i.hasNext())
{
x=i.next(); //get next element
... //do something
}
Iterator in a Map
Set keyset=m.keySet();
Iterator i=keyset.iterator();
while (i.hasNext())
{
Object key=i.next();//get next key
Object value=m.get(key);//get
value
}
Summary
 collection of objects can be implemented by
arrays/ abstract data types
(collection/container)
 some container/collection abstract data types
are defined in the java.util package
 handy & easy to use
 no need to know their implementation details
 you can also define your own abstract data
types
Readings
 Deitel & Deitel Chapters 7 (Arrays)