1. Fundamentals of algorithms Flashcards
Computational Thinking
Solving problems using a computer system.
Decomposition
Breaking down complex problems into smaller, more manageable parts.
Abstraction
Focusing on essential details while ignoring unnecessary information.
Algorithm
A set of step-by-step instructions designed to solve a specific problem.
Systematic Approach
Taking a logical approach and using algorithmic thinking to solve a problem.
Pseudocode
Text-based tool using short English statements to describe an algorithm.
Program Code
Specific to a programming language, unlike generic pseudocode.
Flowchart
Visual tool using shapes to represent different functions of an algorithm, showing input/output, processes, decisions, and control flow.
Algorithm Inputs
Data or information entered into a program before processing, sourced from various inputs like user interaction or sensors.
Algorithm Processes
Doing actions in the algorithm that transform inputs into desired outputs, executed by the CPU.
Algorithm Outputs
Result of processing in an algorithm, often the indicator of whether the algorithm functions as intended.
Trace Table
Tool used to trace through an algorithm or program, testing for logic errors and recording the state of the algorithm at each step.
Purpose of Trace Table
Discovering the algorithm’s purpose, showing output data and intermediary steps, and recording the state of the algorithm.
Trace Table with Algorithms
Trace tables can be used with flowcharts, pseudocode, or program code to analyze algorithms and programs.
Algorithm Efficiency
Measure of the time taken to complete an algorithm.
Linear Search
Sequentially checks each element in the list until the target value is found. A linear search starts with the first value in a dataset and checks every value one at a time until all values have been checked
A linear search can be performed even if the values are not in order.
Binary Search
Divides the sorted list into halves, eliminating half of the remaining elements in each step until the target value is found. A binary search keeps halving a dataset by comparing the target value with the middle value, going left if smaller, right if bigger, until it finds the value or realises it’s not there
To perform a binary search the data must be in order! A binary search can be performed on datasets containing numbers or words. Searching for a word instead of a number is the same process, except comparisons are made based on position in the alphabet (alphabetically) instead of numerical size
Algorithm Selection
Choosing the most appropriate algorithm based on factors like input size, data structure, and problem constraints.
Searching algorithm
Searching algorithms are precise step-by-step instructions that a computer can follow to efficiently locate specific data in massive datasets.
Linear Search advantages / disadvantages
Advantages:
Works on unsorted datasets. Faster (than binary) on very small datasets. Simple to understand and implement.
Disadvantages:
Slow for large datasets. Inefficient, starts at the beginning each time.
Binary Search advantages / disadvantages
Advantages:
Fast for large datasets. Efficient for repeated searches.
Disadvantages:
Dataset must be in order. More complex to implement.
Sorting Algorithm
Precise step-by-step instructions for efficiently sorting data in datasets.
Merge Sort
Sorting algorithm using the ‘divide and conquer’ strategy to divide a dataset into smaller sub-datasets and merge them back together in the correct order. Merge sort divides the dataset into smaller parts, sorts each part separately, and then merges them back together to obtain the sorted dataset.
Bubble Sort
Simple sorting algorithm that compares adjacent elements and swaps them if they are in the wrong order. Bubble sort checks values in pairs and swaps them if they are not in the correct order. Bubble sort continues until there are no more swaps needed, indicating the dataset is sorted.
Merge Sort advantages / disadvantages
Advantages:
Suitable for large datasets
Performs well no matter how unorganized the data is
Disadvantages:
Uses a lot of memory
More complex to implement
Bubble Sort advantages / disadvantages
Advantages:
Simple to understand and implement
Disadvantages:
Slow for large datasets
Inefficient, as it iterates through the data multiple times
