Scribd
Upload
6 views

Algorithm

An algorithm is a sequence of clear instructions for solving a problem with defined inputs and outputs, characterized by finiteness, unambiguity, and effectiveness. Various sorting algorithms like selection sort, bubble sort, merge sort, quick sort, and insertion sort are discussed, along with searching algorithms such as linear search and binary search. Additionally, concepts like time complexity, space complexity, dynamic programming, and recursion are highlighted as essential components in understanding algorithms.

Uploaded by

marwansitten
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
6 views

Algorithm

An algorithm is a sequence of clear instructions for solving a problem with defined inputs and outputs, characterized by finiteness, unambiguity, and effectiveness. Various sorting algorithms like selection sort, bubble sort, merge sort, quick sort, and insertion sort are discussed, along with searching algorithms such as linear search and binary search. Additionally, concepts like time complexity, space complexity, dynamic programming, and recursion are highlighted as essential components in understanding algorithms.

Uploaded by

marwansitten
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

What is an algorithm?

• It is a sequence of unambiguous instructions for solving a problem, for obtaining


a required output for any legitimate input in a finite amount of time

Characteristics of an Algorithm?

• Input: An algorithm should have zero or more inputs


• Output: An algorithm should have one or more outputs
• Finiteness: Every step in an algorithm should end in finite amount of time
• Unambiguous: Each step in an algorithm should clearly stated
• Effectiveness: Each step in an algorithm should be effective
• Brute force
• Brute force is a straightforward approach to solving a problem, usually directly
based on the problem statement and definitions of the concepts involved.

Divide and conquer

• Divide-and-conquer is probably the best-known general algorithm design


technique.

Decrease and conquer

• The decrease-and-conquer technique is based on exploiting the relationship


between a solution to a given instance of a problem and a solution to its smaller
instance.

Time Complexity

• The time taken by a program is the sum of the compiled time & the run time. The
time complexity of an algorithm is given by the number of steps taken by the
algorithm to compute the function it was written for.

Space Complexity

• The space complexity of an algorithm is the amount of memory it needs to run.

How to Determine Complexities

• The total time is found by adding the times for all statements

What is Sorting?

• Sorting is a classic subject in computer science to sort a list of numbers

Selection Sort

• The main idea of selection sort is to scan the entire given list to find its smallest
element and exchange it with the first element, putting the smallest element in
its final position in the sorted list. And repeat this operation until we sort all the
list

Prepared by Hazim Taha


Bubble Sort

• The bubble sort algorithm makes several passes through the array. On each
pass, successive neighboring pairs are compared. If a pair is in decreasing order,
its values are swapped; otherwise, the values remain unchanged

Merge Sort

• Merge sort is a perfect example of a successful application of the divide-and


conquer technique, it divides the array into 2 halves and sorting them then
merging them

Quick Sort

• Another divide-and-conquer algorithm.


• The algorithm selects an element, called the pivot, in the array.
• Divide the array into two parts such that all the elements in the first part are less
than or equal to the pivot and all the elements in the second part are greater
than the pivot.
• Recursively apply the quick sort algorithm to the first part and then the second
part

Insertion Sort

• Insertion sort is a simple sorting algorithm that works by iteratively inserting


each element of an unsorted list into its correct position in a sorted portion of
the list. It is a stable sorting algorithm, meaning that elements with equal values
maintain their relative order in the sorted output.
• Searching
• Search algorithm is an algorithm for finding an item with specified properties
among a collection of items

Linear search

• A linear search, also known as sequential search, is a method of searching an


element in an array or list of elements by iterating through each element one by
one until a match is found or all elements have been searched

Binary Search

• This type of searching algorithm is used to find the position of a specific value
contained in a sorted array.
• The binary search algorithm works on the principle of divide and conquer and it
is considered the best search algorithm because it's faster to run.

Prepared by Hazim Taha


Depth-first Search

• Depth First Search (DFS) is a recursive algorithm for exploring all vertices of a
graph or tree.
• Traversal refers to visiting all the nodes in a graph.
• This algorithm explores the graph in a depthward manner and uses a stack to
keep track of the next vertex to visit when a dead end is reached.

Exhaustive Search

• Many important problems involve finding an element with a special property in a


domain that grows exponentially with instance size.
• These problems often involve combinatorial objects like permutations,
combinations, or subsets of a set.
• Many of them are optimization problems, seeking to maximize or minimize a
characteristic like path length or assignment cost.

Dynamic Programming

• Dynamic Programming is a method used in mathematics and computer science


to solve complex problems by breaking them down into simpler subproblems.
By solving each subproblem only once and storing the results.

Recursion

• A technique where a function calls itself to solve a smaller instance of the same
problem.

Program

• a sequence of coded instructions that can be inserted into a mechanism

Prepared by Hazim Taha

You might also like