ELEE28706D Introduction S1

ELEE28706D ALGORITHMS AND DATA
STRUCTURES
,
Nazrul Khan PhD, PEng.
1
ELEE28706D Algorithms and Data Structures
Today’s Learning Outcome
1. Getting to know each other
2. Understanding the course, its goals, content and requirements

 Class Plan
3. Introduction to data, data structure, and algorithms
4. Some house keeping information
2
Getting to know each other
NAZRUL Khan, Ph.D, P.Eng

Professor and Coordinator(EET)
EXT. 5000
Room: c274
Office Hours:
Virtual meeting through appointment only.
3
DREAM
IF YOU HAVE A DREAM….
GO FOR IT.
Challenged!
NEVER GIVE UP
Face it.
Tips!
How to do good in this course?

 Come to the class and participate in the class: there is no alternative to that
 Ask questions
 Write computer program implementing and applying data structure and
algorithms
We will explore:
- Algorithms for solving problems efficiently.

- Data structures for efficient storing, accessing, and modifying data.
But, in conclusion:
- There is no ultimate data structure/algorithm…

- The choice depends on our requirements
Courtesy: Douglas@uwaterloo
Consider accessing the kth entry in an array or linked list

In an array, we can access it using an index array[k]
We must step through the first k – 1 nodes in a linked list
Consider searching for an entry in a sorted array or linked list

In a sorted array, we use a fast binary search
 Very fast
We must step through all entries less than the entry we’re looking
for
 Slow
However, consider inserting a new entry to the start of an array or a

linked list
– An array requires that you copy all the elements in the array over
• Slow for large arrays
– A linked list allows you to make the insertion very quickly

• Very fast regardless of size
Data & Algorithms
Data and Data item:
 It is a value or set of values. 7,5, Harry etc.,
 Data item refers to a single unit (item) of those data.
Data items are generally organized in a hierarchical way (fields,
records, files etc.,)
Entity:
Something distinct with some properties and having values
(Numeric/Non-numeric).
Property: Name(Nazrul) Nazrul is an

Property: Age(60) entity!
Data & Algorithms
Entity Set:
- All the students in the class with similar properties can form an
Entity
Set.
- Each property of an Entity Set has a range of values (allowed values
for that property).

Field:
A field is a single piece of information (value) representing a property of
an entity.
Record/structure:
A record is one complete set of fields for an entity.
File:
A file is a collection of records of the entities in a entity set.
Data & Algorithms
Data Type:
- It is a classification that specifies which type of value and operation
that can be performed.
In java:
Primitive: int, float, char, double, boolean etc.,
Non-primitive: Data types (class, object, array, string, and interface)
that are not defined by the programming language but are created by
the programmer.
Data & Algorithms
Data Structure:
 A particular way to organize data so that a set of specific operations
can be performed.
 Schemes for organizing data that leave them amenable
(manageable) to efficient processing by an algorithm.
Governed by:
 It must mimic the real world data
 Must be amenable to efficient data processing.
Data & Algorithms
Data Structure:
Logical data representation that specifies:
 A set of data elements and

 A set of operations that can be applied to the data elements for
efficient processing.
DS uses some common

operations to manipulate
& process the data.
Data & Algorithms
Operations:
The possible operations on the linear data structure are:
 Traversal
 Insertion
 Deletion
 Searching
 Sorting
 Merging
Traversal: Processing (accessing) all the data elements (records)

present in it.
Data & Algorithms
Operations:
Insertion: Adding a new record to the data structure.

Deletion: Removing of a data element (record) from the data structure.
Searching: Searching a specific data element (with a key value) in a

data structure.
Sorting: Arranging data elements of a data structure in a specific order.
Merging: Combining elements of two similar data structures to form a

new data structure of the same type.
Data & Algorithms
Design of Data Structure:
 Logical picture of the data
 Representation of data
 Operations on the data
 Quantitative analysis of the structure in terms of resource

(memory) and time to process.
Data & Algorithms
Data Structures
Courtesy: scanftree
Data & Algorithms
Algorithms:
- A finite, deterministic, and effective problem-solving method suitable

for implementation as a computer program.
- We can define an algorithm by writing a computer program that
implements the procedure.
- Most algorithms of interest involve organizing the data involved in
the computation.
- Learning algorithms enabling us to do tasks that would otherwise be
impossible.
- Choosing the best algorithm involves sophisticated mathematical
analysis.
Data & Algorithms
Algorithms:
- In fact, the programs, you developed in the past, is a combination of

algorithms and data structures.
- May be, you didn’t realize that at that time.
- Data structures are quite distinct from algorithms.
- We will focus on abstract data types and analysis of data structures
and algorithms.
- Compare them in terms of time and memory.
- Remember, data structures effect algorithm’s performance!
Good to know…
Algorithm:
A sequence of steps that is unambiguous, executable, and
terminating is called an algorithm. The existence of an algorithm
is an essential prerequisite for programming a task.
Data & Algorithms
Famous Algorithms:
- Euclid’s algorithm (computing the greatest common divisor (GCD) of

two integers.
- Search Engines(www)
- Shortest path (Dijkstra)
- Fast Fourier Transform
- Compression (Huffman)
- Parity Check (Parity Error)
- etc.,
Data & Algorithms
Euclid’s Algorithm:
(Compute the greatest common divisor of two non-negative integers p
and q)
public static int gcd (int p, int q)

{
if(q == 0) return p;
int r = p % q;
return gcd (q,r);
}
Data & Algorithms
Algorithm Comparison:
Computing Factorial
public static int calfact (int p)
{
if(p <= 1) return 1;
else
return p*calfact (p-1); Which one
}
public static int calfact (int p)
is the
{ better?
int value = 0;
if(p <= 1) return 1;
else
{
value = 1;
for(int q = 2; q <= p; q++)
value *= q
return value;
}}
Data & Algorithms
Algorithms in action:
- Network traffic management
- Database transactions and analysis
- Scientific data analysis and computing
- Sensor networks
- Data communications and data transmissions
- ….and so on.
How google finds
your documents??
Data & Algorithms
At the end:
- Study of data structures and algorithms is interesting and exciting.

- With data structures, we can organize data in a amenable way
- With algorithms, we process those data in an efficient way
- That is what we aim to explore in this course.
Good to know…
Programming:
You need to first discover and describe an algorithm for the task
that you want to solve before you start programming.
and you know …
Programming:
A sequence of statements, telling the computer:

1. What to do and
2. How to do.
Computer doesn’t do any thing of its own!
in this course …
we are exploring data structures and implementing/applying

algorithm in those data structures by writing computer program.
This is not a computer programming course!
in this course …
But, we need to write computer program!

We will use java as the language
Your C programming skill will also be handy!
Remember, array, structure, and pointers!
in this course …
As always, you will be given Tim (virtual, of course!) for

answering critical questions.
As such, participate in the class.
Suggestive Reading list:

1. Algorithms, Fourth Edition, Robert Sedgewick, Kevin Wayne
2. Java Concepts Late Objects, 3/e, Cay Horstmann
Acknowledgements
1. DouglasWilhelmHarder@uwaterloo
2. Algs4.cs@princeton
3. Dr. Abul Kashem Mia@buet

ELEE28706D Introduction S1

Uploaded by

Copyright:

Available Formats

ELEE28706D Introduction S1

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

ELEE28706D Introduction S1

Uploaded by

Copyright:

Available Formats

ELEE28706D ALGORITHMS AND DATA

Today’s Learning Outcome

1. Getting to know each other

2. Understanding the course, its goals, content and requirements

3. Introduction to data, data structure, and algorithms

4. Some house keeping information

NAZRUL Khan, Ph.D, P.Eng

IF YOU HAVE A DREAM….

How to do good in this course?

- Algorithms for solving problems efficiently.

- There is no ultimate data structure/algorithm…

Consider accessing the kth entry in an array or linked list

We must step through the first k – 1 nodes in a linked list

Consider searching for an entry in a sorted array or linked list

However, consider inserting a new entry to the start of an array or a

– A linked list allows you to make the insertion very quickly

Property: Name(Nazrul) Nazrul is an

for that property).

 A set of data elements and

DS uses some common

Traversal: Processing (accessing) all the data elements (records)

Insertion: Adding a new record to the data structure.

Searching: Searching a specific data element (with a key value) in a

Sorting: Arranging data elements of a data structure in a specific order.

Merging: Combining elements of two similar data structures to form a

 Logical picture of the data

 Operations on the data

 Quantitative analysis of the structure in terms of resource

- A finite, deterministic, and effective problem-solving method suitable

- In fact, the programs, you developed in the past, is a combination of

- Euclid’s algorithm (computing the greatest common divisor (GCD) of

public static int gcd (int p, int q)

- Study of data structures and algorithms is interesting and exciting.

A sequence of statements, telling the computer:

we are exploring data structures and implementing/applying

But, we need to write computer program!

As always, you will be given Tim (virtual, of course!) for

Suggestive Reading list:

You might also like