Scribd
Upload
3 views20 pages

Data Structures and Algorithm 2024 Edition

Prepared by: Maxil S. Urocay, MSCS ongoing

Uploaded by

Maxil Urocay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
3 views20 pages

Data Structures and Algorithm 2024 Edition

Prepared by: Maxil S. Urocay, MSCS ongoing

Uploaded by

Maxil Urocay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 20

DATA STRUCTURES

AND ALGORITHM

Prepared by: Maxil S. Urocay MSCS ongoing


Prepared by: Maxil S. Urocay MSCS ongoing
DATA STRUCTURE
- a programmatic way of organizing and storing data
so that it can be used, accessed and modified efficiently.
- a way of collecting and organizing data in such a
way that we can perform operations on these data in an
effective way.
- are essential ingredients in creating fast and
powerful algorithms and gives us the possibility to
manage large amounts of data efficiently for uses such
as large databases and more.

Prepared by: Maxil S. Urocay MSCS ongoing


Categories of Data Structures
1. Linear Data Structures
- it is where elements are organized to form any
specific order or in a linear sequence, which means
each element has a unique predecessor and
successor.
- common types are the arrays, linked list, stacks
and queues.
2. Non-Linear Data Structures
- it represents data which are not arranged in a
sequential order but in a hierarchical relationships
between different elements.
- common types are the family of trees, graphs,
Prepared by: Maxil S. Urocay MSCS ongoing
Characteristics of a Data Structure
Correctness – data structure implementation should
implement its interface correctly.

Time Complexity – running time or the execution time of


operations of data structure must be a small as possible.

Space Complexity – memory usage of a data structure


operation should be as little as possible.

Prepared by: Maxil S. Urocay MSCS ongoing


Why to learn DSA?
*as applications are getting complex and data rich, there
are three common problems that applications face now-
a-days.

Data Search – as data grows, search will become slower.


Processor speed – still falls limited if the data grows to
billion records.
Multiple request – even the fast server still fails while
thousand of request or data operations done at the same
time.

Prepared by: Maxil S. Urocay MSCS ongoing


ALGORITHM
- is a step-by-step procedure, which defines a set of
instructions to be executed in a certain order to get the
desired output.
- are generally created independent of underlying
languages and can be implemented in more than one
programming language.
- can help us to find the solution we are looking for,
and to transform a slow program into a faster one.

Prepared by: Maxil S. Urocay MSCS ongoing


Qualities of a good Algorithm
Input – has an instance of the problem to be solved.
Output – produces results to solve the given instance of
the problem.
Definiteness – each step is unambiguous or must be
precisely defined.
Finiteness – terminates after producing the output in a
finite amount of time.
Effectiveness – must consistently and accurately produce
a meaningful and correct result for all possible valid
inputs within a finite amount of time.
Prepared by: Maxil S. Urocay MSCS ongoing
Example: Cooking Rice Algorithm
*Prepare utensils and Ingredients
*Measure the desired amount of rice
*Rinse rice and remove excess starch and swirl with your
hand then drain.
*Combine rice and specific measured water
*Place the pot on the stove over medium high heat and
let it boil
*Once water is boiling reduce heat to low
*Let the rice simmer on low heat for about 5-7 minutes.
*When cook, ready to serve.
Prepared by: Maxil S. Urocay MSCS ongoing
Applications of Data structures and
Algorithms
*Search – algorithm to search an item in a data structure
*Sort – algorithm to sort items in a certain order.
*Insert – algorithm to insert item in a data structure.
*Update – algorithm to update an existing item in a data
structure.
*Delete – algorithm to delete an existing item from a
data structure.

Prepared by: Maxil S. Urocay MSCS ongoing


DATA STRUCTURES AND ALGORITHM
- is about finding efficient ways to store and retrieve
data, to perform operations on data and to solve specific
problems.
- By understanding DSA, you can decide which data
structure or algorithm is best for a given situation.
- you can make programs that run faster or use less
memory.
- will understand how to approach complex
problems and solve them in a systematic way.

Prepared by: Maxil S. Urocay MSCS ongoing


Types of Data Structure
- includes array, String, Linked List, Stack, Queue,
Heap, Hash, Matrix/Grid, Graph and Tree.

Types of Algorithm
- includes Searching, Sorting, Approximation, Divide
and Conquer, Greedy, Recursion, Backtracking,
Randomized, Dynamic programming, Pattern searching,
Mathematical, Geometric, Bitwise, and Branch and
Bound algorithm.
Prepared by: Maxil S. Urocay MSCS ongoing
Foundation terms of a Data Structure
Interface – represents the set of operations that a data
structures supports or can be performed on it. It
specifies what operations are available, but not how they
are implemented. Sometimes also called an abstract
data type.

Implementation – provides the internal representation


and providing the definition of the algorithm used in the
operations of the data structures. It refers to the actual
code that performs the operations defined by the
interface. Prepared by: Maxil S. Urocay MSCS ongoing
Execution Time Cases
WORST CASE – the algorithm performs the maximum
number of operations and provides an upper bound on
the time complexity.
AVERAGE CASE – the algorithm performance is averaged
over all possible inputs of a given size.
BEST CASE – the algorithm performs the minimum
number of operations and represents the best possible
option.

Prepared by: Maxil S. Urocay MSCS ongoing


Asymptotic notations
- used to represent the complexity of an algorithm.
Common types are Big Oh notation, Big omega notation,
Big theta notation, Little Oh notation and Little omega
notation.
1. Big O Notation - describes an upper bound on the time
complexity of an algorithm and most commonly used
notation. It measures the worst case time complexity or
the longest amount of time an algorithm can possibly
take to complete.
- Common types includes Constant time O(1),
Logarithmic time O(log n), Linear time O(n), and more.
Prepared by: Maxil S. Urocay MSCS ongoing
Big O notation
O (1) Constant time – the running time or space does not
change with the size of the input and remains constant.
It is a random access of an element in an array by
accessing an element by index.
O(log n) Logarithmic time – the running time or space
grows logarithmically with the input size and as the input
size grows, the number of operations grows very slowly.

Prepared by: Maxil S. Urocay MSCS ongoing


Big O notation

O(n) Linear time – refers to an algorithm or operation


whose execution time grows linearly with the size of
input.
O (n log n) Linearithmic time – the algorithm’s
performance grows in proportion to n log n.
O (n^2) Quadratic time – the performance is
proportional to the square of the input size.

Prepared by: Maxil S. Urocay MSCS ongoing


Asymptotic notations
2. Big Omega Notation (Ω) – describes a lower bound on
the time complexity of an algorithm. It measures the
best case time complexity or the best amount of time an
algorithm can possibly take to complete.
3. Big Theta Notation (Θ) – provides a tight bound on the
time complexity of an algorithm. It is a formal way to
express both the lower bound and the upper bound of an
algorithm’s running time.

Prepared by: Maxil S. Urocay MSCS ongoing


Asymptotic notations
4. Little oh Notation (o) – describes a function that grows
slower than a given function. Used to describe an upper
bound that cannot be tight or not asymptotically tight.
5. Little Omega notation(ω) - describes a function that
grows faster than a given function. Used to describe the
asymptotic efficiency of algorithms.

Prepared by: Maxil S. Urocay MSCS ongoing


THANK YOU
PRODUCT
OFFERS
Prepared by: Maxil S. Urocay MSCS ongoing

You might also like