Data Structures and Algorithms

Data Structures

• Data structures are various ways to store data, chosen based on the type and intended use of the data
• There are 2 types of data structures in computer science

Primitive Data Structures

• Programming languages provide primitive data structures
• Primitive data structures are simple and represent single values

Abstract Data Structures

• Abstract data structures are higher-level structures with intricate, specialized operations
• Abstract data structures are built from primitive data types
• Arrays, stacks (LIFO), queues (FIFO), trees, and graphs are a few examples

Algorithms

• An algorithm consists of step-by-step instructions that solve a problem or achieve a goal
• It is a methodical process with instructions in a specific order to get a result
• Algorithms are generally language-independent, so they can be implemented in various programming languages

Algorithm Categories

• Search: locates an item
• Sort: arranges items in a sequence
• Insert: adds an item
• Update: modifies an existing item
• Delete/Remove: removes an existing item

Characteristics of an Algorithm

• Algorithms must be unambiguous and transparent, with clear steps, inputs, and outputs
• Algorithms should have at least zero inputs
• Algorithms must provide at least one clearly specified output that corresponds to the intention
• Algorithms must stop after a finite number of steps
• Algorithms must be feasible with the available resources
• Step-by-step instructions should be independent of any programming code

Algorithm to Add Two Numbers

• STEP 1 - START
• STEP 2 - Declare three integers a, b & sum
• STEP 3 - Define values of a & b
• STEP 4 - Add values of a & b
• STEP 5 - Store output of step 4 to sum
• STEP 6 - Print sum
• STEP 7 - STOP

Algorithm to compute GCD/HCF

• STEP 1 - Start
• STEP 2 - Input two numbers (num1, num2)
• STEP 3 - Repeat until num2 becomes 0, replace num1 with num2, and replace num2 with num1 % num2
• STEP 4 - Output num1 as the GCD
• STEP 5 - End

Algorithm to print Fibonacci series

• STEP 1 - Start
• STEP 2 - Input the number of terms N
• STEP 3 - Initialize first = 0, second = 1
• STEP 4 - Print the first two terms
• STEP 5 - Repeat for N-2 times, compute next_term = first + second, print next_term, and update first = second, second = next_term
• STEP 6 - End

Algorithm to swap two numbers

• STEP 1 - Two numbers, a and b, are entered
• STEP 2 - To swap, initialize a 3rd variable called temp
• STEP 3 - Print a and b

Algorithm to compute factorial

• STEP 1 - Input an positive integer n
• STEP 2 - Initialize and set fact = 1 and i = 1
• STEP 3 - While i ≤ n, multiply fact by i and increment i by 1
• STEP 4 - Print Output as fact

Algorithm to input integers and print a sum

• STEP 1 - Initialize and set sum = 0
• STEP 2 - While the input is not equal to -1, add the number to sum
• STEP 3 - Print the total sum of entered numbers

Algorithm Analysis

• Algorithm analysis assesses an algorithm's effectiveness and performance
• Algorithm Analysis increases the understanding of how algorithms respond to increasing input size in terms of speed and memory usage

Importance of Algorithm Analysis

• Efficiency Comparison helps compare different algorithms
• Predicting Performance estimates how an algorithm will perform with inputs
• Optimization helps to choose the most suitable algorithm

Types of Algorithm Analysis

• A Priori Analysis (Theoretical) is done before running the algorithm, using mathematical models
• A Posteriori Analysis (Empirical) is done after running the algorithm on real inputs and measuring execution time

Key Aspects of Analysis

• Time Complexity measures how execution time grows with input size like O(n) or O(log n)
• Space Complexity measures the amount of memory

A Priori Analysis (Theoretical Analysis)

• Done before executing the algorithm
• Based on mathematical reasoning and assumptions about the input size
• The performance of the algorithm is measured using asymptotic notations like Big-O, Theta (Θ), and Omega (Ω)

A Posteriori Analysis (Empirical Analysis)

• Done after executing the algorithm
• Performance is evaluated using real-time execution, considering actual system resources
• Based on experimental observations, like profiling tools

Asymptotic Notations

• Asymptotic notations describe the growth rate of an algorithm's time or space complexity as the input size (n) increases
• Assist in comparing algorithms

Big-O Notation (O)

• Describes the worst-case scenario and represents the time an algorithm will take for large input sizes
• Used to ensure an algorithm won’t perform worse than a certain threshold

Omega Notation (Ω)

• Describes the best-case scenario and represents the time an algorithm will take
• Guarantees that an algorithm runs in a certain amount of time

Theta Notation (Θ)

• Describes the average-case scenario
• Represents both the Big-O and Omega

Bubble Sort

• Bubble Sort arranges elements in a list in ascending or descending order
• Bubble Sort repeatedly swaps adjacent elements if they are not in the correct order

Bubble Sort Working Principle

• Compare starting from the first element to the next element.
• If the first element is greater than the second, swap them.
• Move to the next adjacent pair and repeat the comparison.
• Continue this process until the last element of the array is reached.
• After the first pass, the largest element is at the last position (its correct place).
• Repeat the process for the remaining elements excluding the last sorted element.
• Continue this process until all elements are sorted

Selection Sort

• Selection Sort sorts an array by finding the minimum element's index from the unsorted portion, and placing it at its correct position

Selection Sort Description

• Tracks the index of the smallest element in the unsorted portion
• Updates the index whenever a smaller element is found
• Swaps the smallest found element with the first unsorted element at the end of each pass

Selection Sort Efficiency

• Selection Sort only makes one swap per pass
• Follows the Minimum Index Updation principle, where the minimum element's index is updated
• Creates fewer swaps

Selection Sort Working Principle

• Divide the array into two sections; the sorted is initially empty and the unsorted contains all positions.
• Find the minimum index in the unsorted portion by starting with the first unsorted element and scanning the remaining elements to find a smaller value
• Update the index once a smaller element is found
• Swap the element at the index with the first unsorted element
• Expand the sorted portion by moving the boundary one step forward
• Repeat until the entire array is sorted

Insertion Sort

• Insertion Sort sorts an array by building a sorted position one element at a time
• Shifts elements to make space for the current element being placed in its correct position

Insertion Sort Working Principle

• Assume the first element is already sorted
• Pick the next element and compare it with the elements in the sorted portion
• Shift elements in the sorted portion to the right until the correct position is found
• Insert the element into its correct position
• Repeat the process until the entire array is sorted