INB371 Data Structures and Algorithms – Lecture 1
Lecture Overview – Introduction to the unit, data structures and algorithms, and
Malcolm Corney – Unit Coordinator/Lecturer
ph: 3138 1923, office: GP-S1042
sequence of statements (which statements run first), selection statements
(if/else), repetition statements, variables, functions and methods, classes and
libraries (object oriented programming basics, encapsulation,extension,etc),
editing compilation and debugging
Use abstraction and encapsulation to design abstract data types (ADT's)
Efficient implementation of data structures
Efficient implementation of Algorithms
Knowledge of algorithm analysis
Analyse and solve programming problems by choosing appropriate data
structures and algorithms
Assignment 1 = 20%
Assignment 2 = 30%
Final Exam = 50%
binary search, insertion sort, selection sort,
PC hardware gets faster, memory gets cheaper, following Moore's Law. If you
as a software developer can make software that uses less memory and
resources to run, then you're doing the world a favour. Smartphones have
limited resources, so efficiency is important especially in mobile applications.
Some of the challenges which efficiency is helping:
- Mapping the human genome. 3.3 million parts of DNA which need to be
mapped, so efficient string comparison algorithms are required.
- Expert systems capable of Natural Language, such as IBM's Watson, a
computer able to play jeopardy. The computer has to be able to figure out the
context of the natural language to search for I nformation on the internet and
find the correct answer.
– Could also be used for medicine, where a computer is given a list of
symptoms and could find an answer.
– Autonomous Vehicles, computers which can drive computers and control
the speed, direction and decision making
– GPS route finding, one of the classical algorithms in graph theory.
Considering a bunch of locations with connections, trying to find the
shortest path between two paths - “Djikstra'a Shortest Path” Travelling Salesman Problem
Even some of the fastest computers in the world cannot compute something if
the problem is too difficult, such as the Travelling Salesman problem. Given a
list of cities and distances, try to find the shortest possible route that visits
each city exactly once and returns to the city of origin. It's one of the most
intensely studied optimisation problems.
The simple way would to try each combination in order. Requires (n – 1)! / 2
routes to be calculated, which for 20 cities would be 60,822,550,204,416,000
different possibilities. On a simple laptop, you wouldn't be able to figure out the
Travelling Salesman Problem for just 20 cities.
Fortunately, better algorithms exist. The tour has been found for an 85,900 city
Introduction to C++
C++ is an extension of the languages C and SmallTalk. C was made for writing
linux, and Smalltalk was one of the first object oriented languages, used in labs
etc, and taught in QUT up until the 90's.
Compilation process for C++ is taking a source file, running it through a
compiler, which produces an object file. The object file is then linked with other
object files and libraries which you may require for your program using a linker,
and the linker produces an executable file. Java and C# run in a VM, which is
converted to machine code with a Just In Time compiler, and then interacts
with a Java runtime environment to interact with the low level computer. C++
uses MinGNU for Windows, and any assessment should be compiled using
MinGNU. Microsoft C++ isn't standard C++, so using visual studio isn't
Importing libraries uses the #include command. The next line after a library
include should be the location, which uses the code using namespace std;, as
the two libraries (iostream and iomanip) are both in the std namespace. In C+
+, you have to declare everything before use, even functions. For example, int
RaiseIntToPower(int n, int k);
To print to screen, the command cout is used. << is used as a redirect,
redirecting anything after it to the output stream. Endl is used to end a line. To
create a loop, it is much like C#. for (int n = LOWER_LIMIT; n <= UPPER_LIMIT;
n++) will take the value of LOWER_LIMIT and increase it by 1 until
UPPER_LIMIT value is reached. Multi line commenting is done by /* and */, and
single line commenting is //. Commenting should be included for the file,
functions and amongst the code. Library inclusions always begin with #include,
there is two styles, one with double quotes e.g. #include “stdio.h” which is for
private libraries, or in angle brackets, which indicate a system library, e.g.
#include . Majority of library inclusions will come from 'std'
namespace. The example program imports functionality from std::iostream and
std::iomanip, but when you include using namespace std; you don't have to
type std before a command e.g. std.setw(3) you just type setw(3).
After you import libraries, definitions that occur throughout the program are made, e.g. constant variables.
Function prototypes are declared as well, you must declare a function
before using it in C++. the main function should be the first function listed,
as it's the function required to run your program. Parameter names are not
required in the prototype of a function, e.g. you just use int functionname(int,
Every program must contain a main function. It's the starting point for a
program, so when main finishes, so does the program. In the example program,
cout is used to display information to the screen. << puts information to the
stream, endl is a stream manipulator. Because main is declared as a function
returns int, it must have a return statement. If you return a 0, it indicates that
the run was successful, and any other value indicates failure.
Programs should be broken down into smaller units of work, giving the program
structure and supporting reuse of code. Function definitions go together with
function prototypes. Starting out, they will be in the same file, but as we look
into abstract data types, we will separate definitions and prototypes, so that
the header file provides the functionality. Functions should declare their own
local variables. Parameters may also be passed into a function. Functions may
also return one value to the caller of the function, although you can return
more than one, which will be covered later.
C++ is a strongly typed language, so variables have to have declared of a
certain type and of a certain scope (which part of the program has access to it).
Declaring a variable
type indicates the data type, namelistis a comma separated list of variable
You can declare and add a value to a variable at same time e.g. int number =
Names for variables/functions/types/constants/c