UNIVERSITY OF GONDAR

INSTITUTE OF TECHNOLOGY
Department of Computer Engineering
Algorithm analysis and design Assignment
• NAME ID

SAMUEL TESHALE............................03077/14

submitted to M.r Matiwos G.

Submitted date 04/04/2017
 what is algorithm ?
• An algorithm is a set of instructions or rules that are followed to complete a task
or solve a problem.An algorithm is a series of steps that takes one or more inputs,
runs them through a systematic process, and produces one or more outputs.

• TYPES OF ALGORITHM AND THIERE APPLICATION AREA

Recursion Algorithm and it’s application area
• A recursive algorithm is a programming technique that solves a problem by breaking it
down into smaller, more manageable subproblems and calling itself to solve each
subproblem. This process continues until the problem is simple enough to be solved
directly.

1,APPLICATION AREA OF RECURSIVE ALGORITHM

• Recursive algorithms have many applications, including:
• Sorting
• Recursive algorithms are used in sorting algorithms like merge sort and quick sort.
• Searching
• Recursive algorithms are used in searching algorithms like binary search.
• String manipulation
• Recursive algorithms are used to check if two strings are anagrams or find the longest
common subsequence between two strings.
 continue...
• Mathematical computations
• Recursive algorithms are used to compute factorials and generate Fibonacci numbers.
• Tree and graph traversals
• Recursive algorithms are used to visit nodes in a tree data structure and explore all possible paths in a graph.
• Dynamic programming
• Recursive algorithms with memoization store the results of subproblems to avoid redundant calculations.
• Divide and conquer algorithms
• Recursive algorithms are used to multiply matrices by breaking them down into smaller submatrices.
• AI
• Recursive algorithms are the backbone of AI.
• Windows Paint
• Recursive algorithms are used to fill color in a particular area of a drawing or model.
• Recursive algorithms are a problem-solving approach that breaks down problems into smaller subproblems. They
can make coding certain tasks simpler and cleaner, improving the readability and understanding of the code
 Searching algorithm
• A searching algorithm is a sequence of instructions that helps find information in
a data structure or search space
• APPLICATION AREA OF SEARCHING ALGORITHM
• ORITHMSearching algorithms have many applications, including:
• Finding items in lists or databases: Searching algorithms can find items in lists or
databases by searching for a specific item.
• Searching for words or phrases in documents: Searching algorithms can search
for words or phrases in documents.
• Finding locations on maps: Searching algorithms can find locations on maps.
• Internet search engines: Searching algorithms are used in internet search engines
to find relevant web pages based on keywords.
 continue...

• Machine learning: Binary search is a backbone for developing machine learning

applications.
• Computer graphics: Binary search is a backbone for developing computer
graphics applications.
• Database systems: Binary search is a backbone for developing database systems
applications.
• String matching: Aho-Corasick algorithm is used in string matching, particularly in
text processing applications like keyword searching and pattern recognition.
• Sequence alignment: Suffix arrays are used in bioinformatics for sequence
alignment and string matching in genomic data.
 Sorting algorithm
• A sorting algorithm is a set of instructions that arranges a list or array of items
into a specific order.
• APPLICATION AREA OF SORTING ALGORITHM
• Sorting algorithms have many applications, including:
• E-commerce: Sorting algorithms help users find products based on price,
popularity, or other factors.
• Databases: Sorting algorithms help organize large datasets and make them more
accessible.
• Medical records: Sorting algorithms help organize patient records and make
them more accessible.
• Computer graphics: Sorting algorithms are used for image rendering and data
visualization.
• Numerical computations: Sorting algorithms are used for matrix sorting.
 Bubble sort algorithm
• Bubble sort is a basic algorithm that arranges a list of data into order by comparing
adjacent elements and swapping them if they are out of order
• APPLICATION AREA OF BUBBLE SORT ALGORITHM
• Bubble sort is a sorting algorithm that has a few common applications, including:
• Teaching sorting
• Bubble sort is a simple algorithm that's often used to teach the basics of sorting to new
programmers and computer science students.
• Sorting small datasets
• Bubble sort is ideal for sorting small datasets with a few elements. It's not optimal for large
datasets because it has to repeatedly cycle through the entire set of elements.
• Checking for orderly datasets
• Bubble sort can be used to arrange a dataset that's already sorted but requires a final check
to verify that the elements are in the correct order.
• Testing and debugging other sorting algorithms
• Bubble sort can be used to test and debug other sorting algorithms by serving as a simple
and straightforward reference point.
 continue...

• Some real-world examples of bubble sort include how the contact list on your
phone is sorted in alphabetical order, or the sorting of files on your phone
according to the time they were added.
 selection sorting algorithm
• the selection sort algorithm organises a list of an array by constantly discovering the minimum component
(assuming ascending order) from the unsorted part and placing it at the starting point. The algorithm is very
simple and popular. However, it is not appropriate for extensive data sets.
• APPLICATION AREA OF SELECTION SORT ALGORITHM
• The selection sort algorithm has several applications, including:
• Small datasets
• Selection sort is effective for sorting small arrays or lists because it's simple and easy to implement.
• Limited memory
• Selection sort is an in-place sorting algorithm with a space complexity of O(1), making it suitable for
environments with limited memory.
• Costly writing to memory
• Selection sort is advantageous in scenarios where writing to memory is more expensive than reading, such as
with flash memory or EEPROM.
• Initial pass
• Selection sort can be used as the initial pass in more complex sorting algorithms.
 continue...
• Educational tool
• Selection sort is a valuable tool for teaching the fundamentals of sorting
algorithms.
• Selection Sort in Data Structures
• Selection sort is a straightforward algorithm that works by repeatedly finding
the smallest element from the unsorted portion of a list and placing it at the
beginning.
heap algorithm
• A heap is a tree-based data structure with specific properties that is used in
many algorithms
• APPLICATION AREA OF HEAPS
• Heaps are used in many applications in computer science, including:
• Priority queues
• Heaps are used to implement priority queues, which allow for the insertion,
deletion, and identification of the highest priority element in O(log N) time. For
example, a priority queue could be used to give priority to customers with short
wait times.
• Graph algorithms
• Heaps are used in many graph algorithms, including Dijkstra's algorithm for
finding the shortest path, Huffman coding, and the BFS algorithm.
 continue...
• Finding the smallest or largest element in an array
• A min-heap tree is used to find the smallest element in an array, and a max-
heap tree is used to find the largest element.
• Heap sort
• The heap sort algorithm is used in systems concerned with security and
embedded systems, such as the Linux Kernel.
• Applications of Heap data structures | Heap | Prepbytes
• Heaps are data structures that are typically represented as lists, structures, or
trees. They are used to store other objects, and are suitable for objects or data
whose size might change at runtime
 hash algorithm
• A hash algorithm is a mathematical function that scrambles data into an
unreadable, fixed-length output called a hash value. Hash algorithms are also
known as hash functions.
• APPLICATION AREA OF HASH ALGORITHM
• Data indexing and retrieval: Hashing is a cornerstone concept in computer
science that makes it efficient to retrieve data from large datasets and
databases.
• Authentication: Hashing algorithms can be used for digital signatures, message
authentication codes (MACs), and other forms of authentication.
• Verifying the integrity of messages and files. An important application of secure
hashes is the verification of message integrity. ...
• Signature generation and verification. ...
• Password verification. ...
• Proof-of-work. ...
• File or data identifier.
greedy algorithm
• a greedy algorithm is an algorithm that finds a solution to problems in the
shortest time possible. It picks the path that seems optimal at the moment
without regard for the overall optimization of the solution that would be
formed
• APPLICATION AREA OF GREEDY ALGORITHM
• Greedy algorithms are used in many applications, including:
• Optimization problems
• Greedy algorithms are used to solve problems that involve finding the
minimum or maximum of something, such as the shortest path, the largest
profit, or the smallest cost. Examples of optimization problems that can be
solved using greedy algorithms include the knapsack problem, job scheduling
problem, and activity selection problem.
• Constructing minimum spanning trees
• Prim's and Kruskal's algorithms are greedy algorithms used to construct
minimum spanning trees.
 continue...
• Huffman encoding
• A greedy algorithm is used to build a Huffman tree that compresses a given
image, spreadsheet, or video into a lossless compressed file.
• Decision tree learning
• Greedy algorithms are commonly used in decision tree learning, although they
are not guaranteed to find the optimal solution.
 graph algorithm
• A graph algorithm is a set of instructions that manipulate graph data structures
to solve problems or perform tasks. Graphs are made up of nodes and edges
that represent entities and relationships, respectively.
• APPLICATION AREA OF GRAPH ALGORITHM
• Graph algorithms have many applications, including:
• Transportation planning: Graph algorithms are used to calculate the shortest
paths between nodes in a graph, such as in Google Maps.
• Social network analysis: Graph algorithms can be used to find degrees of
separation between users, suggest potential friends, and detect communities.
• Bioinformatics: Graph algorithms are used in DNA analysis.
• Equilibrium analysis: Graph algorithms can be used to analyze equilibrium
outcomes in games, such as identifying influential players.
• Machine learning: Graph algorithms can be used in machine learning models.
 continue...
• Blockchain: Graph algorithms can be used to model blockchains, where
vertices are blocks and edges connect the blocks.
• Bitcoin creation graphs: Graph algorithms can be used to model the flow of
money between Bitcoin wallets.
• Graph algorithms are computational procedures that operate on graph
structures, which are made up of nodes and edges. Graphs are a valuable tool
for modeling real-world data in many fields, including economics, mathematics,
physics, and aeronautics
Backtracking Algorithm
• A backtracking algorithm is a technique that finds solutions to problems by exploring all possible combinations
and discarding those that don't meet the problem's constraints. It's based on the Depth First Search (DFS)
approach.
• APPLICATION AREA OF BACKTRACKING ALGORITHM
• Backtracking algorithms are used in many applications, including:
• Puzzle solving
• Backtracking is used to solve puzzles like Sudoku, crosswords, and the N-Queens problem.
• Pathfinding
• Backtracking can be used to find optimal paths in graphs or solve mazes.
• Game playing
• Backtracking can be used to evaluate possible moves in board games like chess or to explore possible moves in
strategy games.
• Combinatorial optimization
• Backtracking can be used to generate all permutations, combinations, and subsets of a given set.
 continue...
• Constraint satisfaction problems
• Backtracking can be used in problems like graph coloring, scheduling, and job assignment.
• Decision-making
• Backtracking can be used to help make optimal decisions in situations where multiple choices are
possible.
• String processing
• Backtracking can be used to generate valid strings that meet certain criteria.
• Optimization problems
• Backtracking can be used to find solutions to complex optimization problems.
• Verifying other algorithms
• Backtracking can be used to verify the correctness and efficiency of other algorithms.
• Backtracking algorithms work by building a solution step by step using recursion. If it's determined that
the solution isn't valid, the algorithm backtracks to the previous step.
 END OF ASSIGNMENT

• THANK YOU.