COSC1285/2123: Algorithms & Analysis – Course Overview
COSC1285/2123: Algorithms & Analysis
Course Overview
Hoang MIT University
Email : sonhoang. .au
Lecture 1
(RMIT University) Course Overview Lecture 1 1 / 53
Outline
1 Preliminaries
2 What is an algorithm and motivation for its study
3 Abstract Data Types
4 Data Structures
5 Summary
(RMIT University) Course Overview Lecture 1 2 / 53
Overview
1 Preliminaries
2 What is an algorithm and motivation for its study
3 Abstract Data Types
4 Data Structures
5 Summary
(RMIT University) Course Overview Lecture 1 3 / 53
Staff
Lecturer: Son (call me Hoang)
Email: sonhoang. .au
Team of workshop demonstrators: Ayad, Osama, Rupa, Prodip
Course Homepage: Go to Canvas,
https://rmit.instructure.com/courses/79906
(COSC1285/2123, 2021 Semester 2).
(RMIT University) Course Overview Lecture 1 4 / 53
https://rmit.instructure.com/courses/79906
General Course Goals
Key Goal
Study algorithms and their analysis in order to find practical
solutions to real-world problems
Our goals are:
• Theory:
• Learn a variety of important algorithms
• Understand how to determine algorithm complexity, that is, the
estimate running time
• Practice:
• Learn to implement various algorithms and data structures to solve
a variety of problems
• Understand how to measure the actual running time of an algorithm
empirically
(RMIT University) Course Overview Lecture 1 5 / 53
General Course Goals
Key Goal
Study algorithms and their analysis in order to find practical
solutions to real-world problems
Our goals are:
• Theory:
• Learn a variety of important algorithms
• Understand how to determine algorithm complexity, that is, the
estimate running time
• Practice:
• Learn to implement various algorithms and data structures to solve
a variety of problems
• Understand how to measure the actual running time of an algorithm
empirically
(RMIT University) Course Overview Lecture 1 5 / 53
General Course Goals
Key Goal
Study algorithms and their analysis in order to find practical
solutions to real-world problems
Our goals are:
• Theory:
• Learn a variety of important algorithms
• Understand how to determine algorithm complexity, that is, the
estimate running time
• Practice:
• Learn to implement various algorithms and data structures to solve
a variety of problems
• Understand how to measure the actual running time of an algorithm
empirically
(RMIT University) Course Overview Lecture 1 5 / 53
Why study Algorithms, Data Structures and their
evaluation?
In order to solve problems, including building
computer programs to do so, we need to have
(algorithmic) tools and evaluate how efficient the
tools are.
Why do we need an algorithmic toolset and learn
how to evaluate their efficiency?
Answer:
• Need to know how the algorithms work and how to measure their
efficiency in order to select the right one for the right problem/job.
• Designing new algorithms or modify exiting ones to solve your
problems.
• It makes you a better problem solver and programmer!
(RMIT University) Course Overview Lecture 1 6 / 53
Why study Algorithms, Data Structures and their
evaluation?
In order to solve problems, including building
computer programs to do so, we need to have
(algorithmic) tools and evaluate how efficient the
tools are.
Why do we need an algorithmic toolset and learn
how to evaluate their efficiency?
Answer:
• Need to know how the algorithms work and how to measure their
efficiency in order to select the right one for the right problem/job.
• Designing new algorithms or modify exiting ones to solve your
problems.
• It makes you a better problem solver and programmer!
(RMIT University) Course Overview Lecture 1 6 / 53
Why study Algorithms, Data Structures and their
evaluation?
In order to solve problems, including building
computer programs to do so, we need to have
(algorithmic) tools and evaluate how efficient the
tools are.
Why do we need an algorithmic toolset and learn
how to evaluate their efficiency?
Answer:
• Need to know how the algorithms work and how to measure their
efficiency in order to select the right one for the right problem/job.
• Designing new algorithms or modify exiting ones to solve your
problems.
• It makes you a better problem solver and programmer!
(RMIT University) Course Overview Lecture 1 6 / 53
Why study Algorithms, Data Structures and their
evaluation?
In order to solve problems, including building
computer programs to do so, we need to have
(algorithmic) tools and evaluate how efficient the
tools are.
Why do we need an algorithmic toolset and learn
how to evaluate their efficiency?
Answer:
• Need to know how the algorithms work and how to measure their
efficiency in order to select the right one for the right problem/job.
• Designing new algorithms or modify exiting ones to solve your
problems.
• It makes you a better problem solver and programmer!
(RMIT University) Course Overview Lecture 1 6 / 53
Prequisites
• This course is not about programming, but we do need a
language for the practical parts:
• Java: At a minimum, you should be comfortable with basic data
types and structures, defining new classes and data types,
inheritance and polymorphism.
• Warning: The assignments and labs are all in Java, so you will
struggle if you are not comfortable with Java.
• Prequisites:
• COSC1295 Advanced Programming or COSC2391 Further
Programming, or COSC1076 Advanced Programming Techniques,
which teach Java and concepts helpful for this course.
(RMIT University) Course Overview Lecture 1 7 / 53
Prequisites
• This course is not about programming, but we do need a
language for the practical parts:
• Java: At a minimum, you should be comfortable with basic data
types and structures, defining new classes and data types,
inheritance and polymorphism.
• Warning: The assignments and labs are all in Java, so you will
struggle if you are not comfortable with Java.
• Prequisites:
• COSC1295 Advanced Programming or COSC2391 Further
Programming, or COSC1076 Advanced Programming Techniques,
which teach Java and concepts helpful for this course.
(RMIT University) Course Overview Lecture 1 7 / 53
Prequisites
• This course is not about programming, but we do need a
language for the practical parts:
• Java: At a minimum, you should be comfortable with basic data
types and structures, defining new classes and data types,
inheritance and polymorphism.
• Warning: The assignments and labs are all in Java, so you will
struggle if you are not comfortable with Java.
• Prequisites:
• COSC1295 Advanced Programming or COSC2391 Further
Programming, or COSC1076 Advanced Programming Techniques,
which teach Java and concepts helpful for this course.
(RMIT University) Course Overview Lecture 1 7 / 53
Maths 🙂
This course has some maths in it.
We need to count how many times certain operations occur to analysis
algorithms.
• Equations (summations, recursions).
∑n
i=0 2.
• Arithmetic and partial sum simplifications.
∑n
i=0 2 = 2n + 2.
I understand some of you haven’t see maths for years (or run for
nearest train station when it appears), but help is available.
(RMIT University) Course Overview Lecture 1 8 / 53
Maths 🙂
This course has some maths in it.
We need to count how many times certain operations occur to analysis
algorithms.
• Equations (summations, recursions).
∑n
i=0 2.
• Arithmetic and partial sum simplifications.
∑n
i=0 2 = 2n + 2.
I understand some of you haven’t see maths for years (or run for
nearest train station when it appears), but help is available.
(RMIT University) Course Overview Lecture 1 8 / 53
Maths 🙂
This course has some maths in it.
We need to count how many times certain operations occur to analysis
algorithms.
• Equations (summations, recursions).
∑n
i=0 2.
• Arithmetic and partial sum simplifications.
∑n
i=0 2 = 2n + 2.
I understand some of you haven’t see maths for years (or run for
nearest train station when it appears), but help is available.
(RMIT University) Course Overview Lecture 1 8 / 53
Official Textbook
A. Levitin. Introduction to the design and analysis of algorithms.
, Boston, third edition, 2012, ISBN-13:
9780132316811.
(RMIT University) Course Overview Lecture 1 9 / 53
Other Reference Books
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to
Algorithms. The MIT Press, Cambridge, Massachusetts, third edition,
2008.
J. Kleinberg and É. Tardos. Algorithm Design. Pearson, Boston, 2006.
(RMIT University) Course Overview Lecture 1 10 / 53
Course Syllabus
Lecture Topic Reading
1 Introduction Levitin – Ch 1
2 Basic Data Structures & Algorithmic Analysis Levitin – Ch 2
3 Algorithmic Analysis Levitin – Ch 2
4 Brute Force Levitin – Ch 3
5 Decrease & Conquer Levitin – Ch 4
6 Divide & Conquer Levitin – Ch 5
7 Transform & Conquer Levitin – Ch 6
8 Dynamic Programming Levitin – Ch 8
9 Greedy Techniques Levitin – Ch 9
10 Incremental Improvement Levitin – Ch 10
11 Time & Space Tradeoffs Levitin – Ch 7
12 Course Review
(RMIT University) Course Overview Lecture 1 11 / 53
Course Structure
(RMIT University) Course Overview Lecture 1 12 / 53
Assessment
70% of your assessment will come from two assignments.
10% of your assessment will come from weekly online quizzes that you
can attempt on Canvas.
20% of your assessment will come from the End-of-semester
take-home exercises.
(RMIT University) Course Overview Lecture 1 13 / 53
Weekly Quizzes
• Every week, there will be a 5 question quiz.
• A total of 12 quizzes, one per week, will be available for you to
complete through Canvas.
• Each quiz contributes up to 1% of your final course mark. If you
complete more than 10 quizzes, we take your 10 best results to
compute the quiz mark component .
• For each quiz, if you score at least 4 out of 5, you will get will get
the 1% mark, if you score 3 out of 5, you will get 0.5% marks, and
if you score less than 3, you will get 0 marks for that quiz.
• Each quiz must be completed before 11:59 PM on the Sunday of
that week.
(RMIT University) Course Overview Lecture 1 14 / 53
Weekly Quizzes
• Every week, there will be a 5 question quiz.
• A total of 12 quizzes, one per week, will be available for you to
complete through Canvas.
• Each quiz contributes up to 1% of your final course mark. If you
complete more than 10 quizzes, we take your 10 best results to
compute the quiz mark component .
• For each quiz, if you score at least 4 out of 5, you will get will get
the 1% mark, if you score 3 out of 5, you will get 0.5% marks, and
if you score less than 3, you will get 0 marks for that quiz.
• Each quiz must be completed before 11:59 PM on the Sunday of
that week.
(RMIT University) Course Overview Lecture 1 14 / 53
Weekly Quizzes
• Every week, there will be a 5 question quiz.
• A total of 12 quizzes, one per week, will be available for you to
complete through Canvas.
• Each quiz contributes up to 1% of your final course mark. If you
complete more than 10 quizzes, we take your 10 best results to
compute the quiz mark component
.
• For each quiz, if you score at least 4 out of 5, you will get will get
the 1% mark, if you score 3 out of 5, you will get 0.5% marks, and
if you score less than 3, you will get 0 marks for that quiz.
• Each quiz must be completed before 11:59 PM on the Sunday of
that week.
(RMIT University) Course Overview Lecture 1 14 / 53
Weekly Quizzes
• Every week, there will be a 5 question quiz.
• A total of 12 quizzes, one per week, will be available for you to
complete through Canvas.
• Each quiz contributes up to 1% of your final course mark. If you
complete more than 10 quizzes, we take your 10 best results to
compute the quiz mark component .
• For each quiz, if you score at least 4 out of 5, you will get will get
the 1% mark, if you score 3 out of 5, you will get 0.5% marks, and
if you score less than 3, you will get 0 marks for that quiz.
• Each quiz must be completed before 11:59 PM on the Sunday of
that week.
(RMIT University) Course Overview Lecture 1 14 / 53
Weekly Quizzes
• Every week, there will be a 5 question quiz.
• A total of 12 quizzes, one per week, will be available for you to
complete through Canvas.
• Each quiz contributes up to 1% of your final course mark. If you
complete more than 10 quizzes, we take your 10 best results to
compute the quiz mark component .
• For each quiz, if you score at least 4 out of 5, you will get will get
the 1% mark, if you score 3 out of 5, you will get 0.5% marks, and
if you score less than 3, you will get 0 marks for that quiz.
• Each quiz must be completed before 11:59 PM on the Sunday of
that week.
(RMIT University) Course Overview Lecture 1 14 / 53
Academic Misconduct
• Please read the University Plagiarism Statement in the course
guide very carefully.
• In short, cheating, whether by fabrication, falsification of data, or
representing the work of someone else as your own is an offense
subject to University disciplinary procedures.
• Plagiarism may result in charges of academic misconduct which
carry a range of penalties including cancellation of results and
exclusion from the course.
• Exact penalties are decided in formal plagiarism hearings.
• Assignment 1 will be done in groups of 2 (pairs), while
Assignment 2, weekly quizzes, and End-of-semester
take-home exercises must be done individually.
(RMIT University) Course Overview Lecture 1 15 / 53
Sources of help (We are here to help!)
(RMIT University) Course Overview Lecture 1 16 / 53
Extensions/Special Considerations
• Where possible, let us know if you may be delayed in submitting
an assignment or other assessable material. Please do not wait
until the day before it is due.
• Extensions are only granted in exceptional circumstances and
require the official process of “Special Consideration” to be
followed.
(RMIT University) Course Overview Lecture 1 17 / 53
Week 1 Overview
Levitin – The design and analysis of algorithms
This week we will be covering the material from Chapter 1.
Learning outcomes:
• Understand the concept of algorithms and data structures and the
motivation behind their analysis.
• Learn about different abstract data types and data structures
(expanded upon in subsequent classes).
(RMIT University) Course Overview Lecture 1 18 / 53
Overview
1 Preliminaries
2 What is an algorithm and motivation for its study
3 Abstract Data Types
4 Data Structures
5 Summary
(RMIT University) Course Overview Lecture 1 19 / 53
What is an algorithm?
An algorithm is a sequence of (unambiguous) instructions/steps for
solving a problem.
(RMIT University) Course Overview Lecture 1 20 / 53
Examples of Algorithms … ?
(RMIT University) Course Overview Lecture 1 21 / 53
Example: Euclid’s Algorithm
Problem : Find GCD(m,n), the greatest common divisor of two
non-negative integers m and n.
Examples: GCD(60,24) = 12; GCD(60,0) = 60; GCD(0,0) = ?
Solution (sketch)
Euclid’s algorithm is based on repeated application of the equality
GCD(m,n) = GCD(n,m mod n) until the second number (n) becomes
0. The answer is then the first number (m).
Example : GCD(60,24) = GCD(24,12) = GCD(12,0) = 12
(RMIT University) Course Overview Lecture 1 22 / 53
Example: Euclid’s Algorithm
Problem : Find GCD(m,n), the greatest common divisor of two
non-negative integers m and n.
Examples: GCD(60,24) = 12; GCD(60,0) = 60; GCD(0,0) = ?
Solution (sketch)
Euclid’s algorithm is based on repeated application of the equality
GCD(m,n) = GCD(n,m mod n) until the second number (n) becomes
0. The answer is then the first number (m).
Example : GCD(60,24) = GCD(24,12) = GCD(12,0) = 12
(RMIT University) Course Overview Lecture 1 22 / 53
Euclid’s Algorithm Pseudocode
ALGORITHM Euclid (m,n)
// Computes GCD(m,n) by Euclid’s algorithm
// INPUT : Two non-negative integers m and n
// OUTPUT : Greatest Common Divisor of m and n
1: if n > 0 then
2: return GCD(n,m mod n)
3: end if
4: return m
(RMIT University) Course Overview Lecture 1 23 / 53
Euclid’s Algorithm
Alternative approaches to this problem?
Is it more “efficient”?
(RMIT University) Course Overview Lecture 1 24 / 53
GCD Alternative (Sketch)
Alternative – Common primes:
Step 1 Find the prime factors of m.
Step 2 Find the prime factors of n.
Step 3 Identify all the common factors in the two prime expansions
from Step 1 and Step 2.
Step 4 Compute the product of all common factors and return it as the
greatest common divisor.
Example:
60 = 2 · 2 · 3 · 5
24 = 2 · 2 · 2 · 3
GCD(60,24) = 2 · 2 · 3 = 12
(RMIT University) Course Overview Lecture 1 25 / 53
Motivation for studying algorithms
Video
(RMIT University) Course Overview Lecture 1 26 / 53
https://www.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/v/what-are-algorithms
Overview
1 Preliminaries
2 What is an algorithm and motivation for its study
3 Abstract Data Types
4 Data Structures
5 Summary
(RMIT University) Course Overview Lecture 1 27 / 53
Abstract Data Types and Data structures
Algorithms process input data, produce and process intermediate
data, then output some results, which could be stored as data.
But we do not want to consider algorithms for each type of input data.
Instead we seek to talk about the input data, the intermediate data,
and the output data in terms of general characteristics and operations
the data should possess.
These data abstractions are called Abstract data types (ADT).
• An ADT can be defined by the collection of common operations
that are accessed through an interface and its characteristics.
(RMIT University) Course Overview Lecture 1 28 / 53
Abstract Data Types and Data structures
Algorithms process input data, produce and process intermediate
data, then output some results, which could be stored as data.
But we do not want to consider algorithms for each type of input data.
Instead we seek to talk about the input data, the intermediate data,
and the output data in terms of general characteristics and operations
the data should possess.
These data abstractions are called Abstract data types (ADT).
• An ADT can be defined by the collection of common operations
that are accessed through an interface and its characteristics.
(RMIT University) Course Overview Lecture 1 28 / 53
Abstract Data Types and Data structures
Algorithms process input data, produce and process intermediate
data, then output some results, which could be stored as data.
But we do not want to consider algorithms for each type of input data.
Instead we seek to talk about the input data, the intermediate data,
and the output data in terms of general characteristics and operations
the data should possess.
These data abstractions are called Abstract data types (ADT).
• An ADT can be defined by the collection of common operations
that are accessed through an interface and its characteristics.
(RMIT University) Course Overview Lecture 1 28 / 53
Abstract Data Type
Data structure is the implementation of an abstract data type.
Example:
• Integer (-4,-1, 0, 29) is an abstract data type. Its operations
include add, subtract, multiply etc.
• Bit vectors is a data structure. It is an implementation of an
integer.
• Hexadecimal vectors is a data structure. It is an implementation of
an integer.
Motivation:
• We can specify the input and data forms of our algorithms in
terms of ADT, and not worry about the actual implementation until
we need to implement it.
• We can change data structure implementations to cater for the
problem at hand.
(RMIT University) Course Overview Lecture 1 29 / 53
Abstract Data Type
Data structure is the implementation of an abstract data type.
Example:
• Integer (-4,-1, 0, 29) is an abstract data type. Its operations
include add, subtract, multiply etc.
• Bit vectors is a data structure. It is an implementation of an
integer.
• Hexadecimal vectors is a data structure. It is an implementation of
an integer.
Motivation:
• We can specify the input and data forms of our algorithms in
terms of ADT, and not worry about the actual implementation until
we need to implement it.
• We can change data structure implementations to cater for the
problem at hand.
(RMIT University) Course Overview Lecture 1 29 / 53
Abstract Data Type
Data structure is the implementation of an abstract data type.
Example:
• Integer (-4,-1, 0, 29) is an abstract data type. Its operations
include add, subtract, multiply etc.
• Bit vectors is a data structure. It is an implementation of an
integer.
• Hexadecimal vectors is a data structure. It is an implementation of
an integer.
Motivation:
• We can specify the input and data forms of our algorithms in
terms of ADT, and not worry about the actual implementation until
we need to implement it.
• We can change data structure implementations to cater for the
problem at hand.
(RMIT University) Course Overview Lecture 1 29 / 53
Fundamental ADTs
• set
• sequences
• dictionary/map
• stack
• queue
• priority queue
• graph
• tree
(RMIT University) Course Overview Lecture 1 30 / 53
Sets
Sets
A set is a collection of distinguishable objects, often called members or
elements.
• Sets can be finite or infinite, and do not impose any ordering on
the members.
• Typical operations: add, remove, search
• Each element may only appear in the set once. If elements may
appear multiple times, the resulting collection is referred to as a
bag or multiset.
(RMIT University) Course Overview Lecture 1 31 / 53
Sets
Example (Sets)
Simple examples of sets include:
(1) binary : S1 = {0,1},
(2) character : S2 = {c,a, y , s, t},
(3) word : S3 = { car, house, man, sat, truck },
(4) delimiter : S4 = {{!}, {; }, {?}, {.}},
(5) variable-length, prefix-free bit sequences:
S5 = {0,10,110,1110}.
(RMIT University) Course Overview Lecture 1 32 / 53
Sequences
Sequences
A sequence is a collection of elements in which the order of the
elements must be maintained, and elements can occur any number of
times.
• A sequence is simply a multiset in which the order is important.
• Typical operations: add, remove, search
• In computer science, can also be referred to as a list (ordered
collection of elements).
(RMIT University) Course Overview Lecture 1 33 / 53
Sequences
Example (Sequences)
Examples of sequences include:
(1) Binary : T1 = “101010110001”,
(2) English : T2 = “The red car belongs to me.”,
(3) Genomic : T3 = “gattcaggaatccgccggtaacgcgcatataattt”.
(RMIT University) Course Overview Lecture 1 34 / 53
Stack
Stack
A stack is a collection with two defining operations, push and pop.
Push adds new element at top of stack, pop removes element at top
from stack.
Stack ADT implements LIFO principle (last in, first out).
(a) push (b) pop
(RMIT University) Course Overview Lecture 1 35 / 53
Queue
Queue
A queue is a collection with two defining operations, enqueue and
dequeue. Enqueue adds new element at back of queue, dequeue
removes element at front from queue.
Queue ADT implements FIFO principle (first in, first out).
(c) enqueue (d) dequeue
(RMIT University) Course Overview Lecture 1 36 / 53
Priority Queue
Queue
A priority queue is a queue that has a priority associated with each
element it holds. Enqueue is the same as a (non-priority) queue, but
for dequeue, the element with the highest priority is removed first.
Example: Queue for boarding planes, passengers who are members
of the airlines or elderly have priority board plane (dequeue).
(RMIT University) Course Overview Lecture 1 37 / 53
Priority Queue
Queue
A priority queue is a queue that has a priority associated with each
element it holds. Enqueue is the same as a (non-priority) queue, but
for dequeue, the element with the highest priority is removed first.
Example: Queue for boarding planes, passengers who are members
of the airlines or elderly have priority board plane (dequeue).
(RMIT University) Course Overview Lecture 1 37 / 53
Dictionaries/Maps
Dictionary/Maps
A dictionary/map is a collection of (key,value) pairs, such that each key
can only appear once in the dictionary/map.
Example (Dictionary/map)
Example of a dictionary of current leaders and countries they led:
key value
Australia
Xi Jinping China
UK
Joe Biden US
(RMIT University) Course Overview Lecture 1 38 / 53
Dictionaries/Maps
Dictionary/Maps
A dictionary/map is a collection of (key,value) pairs, such that each key
can only appear once in the dictionary/map.
Example (Dictionary/map)
Example of a dictionary of current leaders and countries they led:
key value
Australia
Xi Jinping China
UK
Joe Biden US
(RMIT University) Course Overview Lecture 1 38 / 53
Graphs
A graph G = 〈V ,E〉 is defined by a pair of two sets: a finite set V of
items called vertices and a set E called edges, representing
links/relations/connections between pairs of vertices.
Example:
V = {a,b, c,d ,e, f}
E = {(a,d), (a, c), (d ,e), (c,e), (c,b), (e, f ), (b, f )}
(RMIT University) Course Overview Lecture 1 39 / 53
Graphs
A graph G = 〈V ,E〉 is defined by a pair of two sets: a finite set V of
items called vertices and a set E called edges, representing
links/relations/connections between pairs of vertices.
Example:
V = {a,b, c,d ,e, f}
E = {(a,d), (a, c), (d ,e), (c,e), (c,b), (e, f ), (b, f )}
(RMIT University) Course Overview Lecture 1 39 / 53
Graphs
• A graph G is undirected if the edges do not have a direction (i.e.,
all of the pairs of vertices in E are unordered).
• A graph G is directed if the edges from a direction (i.e., all of the
pairs of vertices in E have an ordering imposed).
(RMIT University) Course Overview Lecture 1 40 / 53
Graphs
• A graph G is undirected if the edges do not have a direction (i.e.,
all of the pairs of vertices in E are unordered).
• A graph G is directed if the edges from a direction (i.e., all of the
pairs of vertices in E have an ordering imposed).
(RMIT University) Course Overview Lecture 1 40 / 53
Graph Representations
How to represent a graph without drawing it?
Vertex and edge lists
(previously)? Other possibilities?
(RMIT University) Course Overview Lecture 1 41 / 53
Graph Representations
How to represent a graph without drawing it? Vertex and edge lists
(previously)? Other possibilities?
(RMIT University) Course Overview Lecture 1 41 / 53
Graph Representations
How to represent a graph without drawing it? Vertex and edge lists
(previously)? Other possibilities?
(RMIT University) Course Overview Lecture 1 41 / 53
Weighted Graphs
What if edges have weights associated with them?
(RMIT University) Course Overview Lecture 1 42 / 53
Weighted Graphs
What if edges have weights associated with them?
(RMIT University) Course Overview Lecture 1 42 / 53
Trees
A tree is a connected acyclic graph.
(e) tree (f) Not a tree (but a graph)
(RMIT University) Course Overview Lecture 1 43 / 53
Overview
1 Preliminaries
2 What is an algorithm and motivation for its study
3 Abstract Data Types
4 Data Structures
5 Summary
(RMIT University) Course Overview Lecture 1 44 / 53
Data Structures
Now we describe several data structures that can implement different
abstract data types.
We will learn more data structures as we progress through the course.
Two important data structures are array and linked-list.
Both can implement many ADT, e.g., sequences, set, dictionary.
(RMIT University) Course Overview Lecture 1 45 / 53
Array
Characteristics:
• Collection of elements usually stored in a continuous manner,
accessed by indices.
• Fast random access.
• Resizing can be costly (may require copying), hence often need to
estimate size of array beforehand.
(RMIT University) Course Overview Lecture 1 46 / 53
Linked Lists
HEAD TAIL
A P J Q D H B W M
9
• Each node stores element and a pointer to next node.
• There is a head pointer that points to the start of the list.
• Somtimes there is a tail pointer that points to the end of the list.
• Other variants of linked list (e.g., doubly linked lists, go to labs to
see!)
(RMIT University) Course Overview Lecture 1 47 / 53
Linked Lists – insertion
Insert the elements of following sequence of letters, one by one
[A,P,J,Q,D,H,B,W,M]:
(RMIT University) Course Overview Lecture 1 48 / 53
Linked Lists – insertion
Insert the elements of following sequence of letters, one by one
[A,P,J,Q,D,H,B,W,M]:
HEAD TAIL
A P J Q D H B W M
9
What if I wanted to insert element C between Q and D?
(RMIT University) Course Overview Lecture 1 49 / 53
Linked Lists – deletion
HEAD TAIL
A P J Q D H B W M
9
Given linked-list, delete B:
(RMIT University) Course Overview Lecture 1 50 / 53
Overview
1 Preliminaries
2 What is an algorithm and motivation for its study
3 Abstract Data Types
4 Data Structures
5 Summary
(RMIT University) Course Overview Lecture 1 51 / 53
Summary
• What is an algorithm, examples of it, and why the study of
algorithms and data structures are important.
• Discussed the GCD problem and how it can be solved.
• Learnt about abstract data structures and two data structures
(arrays and linked lists).
• Ultimately, remember the study of algorithms and data structures
is for us to become better at solving problem.
(RMIT University) Course Overview Lecture 1 52 / 53
Summary
• What is an algorithm, examples of it, and why the study of
algorithms and data structures are important.
• Discussed the GCD problem and how it can be solved.
• Learnt about abstract data structures and two data structures
(arrays and linked lists).
• Ultimately, remember the study of algorithms and data structures
is for us to become better at solving problem.
(RMIT University) Course Overview Lecture 1 52 / 53
Todo for next week
What should I be doing?
• Get the textbook.
• Read Chapter 1 and Chapter 2 carefully.
• Next week (Chapter 2) covers complexity analysis.
• Be ready for next week. Chapter 2 arguably contains some of
more difficult material of the course.
• Your workshop next week will focus on the fundamental data
structures in Section 1.4.
(RMIT University) Course Overview Lecture 1 53 / 53
Preliminaries
What is an algorithm and motivation for its study
Abstract Data Types
Data Structures
Summary