algorithms and data structures
what is an algorithm?
informal definition: a precise , step by step set of instructions for solving a problem or completing a task
everyday examples: recipe for baking a cake etc;
in computer science: a finite, well defined sequence of unambiguous instructions that produces a result and terminates in a finite amount of time
notion of computable problem: problem is colmputable/decidable if there is an algorithm that takes any valid input instance of the problem and produces correct output
key properties of an algorithm
finiteness: must terminate after a finite number of steps (cannot run forever)
definiteness (unambiguity)/clarity: each step must be precise and clearly defined, leaves no room for interpretation
correctness: must produce the correct output for every valid input
input & output: takes 0 or more inputs and produces at least one output
effectiveness ( feasibility): each step must be basic enough to be carried out by a human using only pen and paper, and must be feasible in finite time.
generality: should solve a general class of problems, not just a single input case
why are algorithms important?
efficiency: help us solve problems efficiently, using the least amount of time and memory
automation: allow computers to perform tasks automatically
problem solving: provide a systematic way to approach and solve complex problems.
algorithms vs heuristics
algorithm:
a step by step, well defined procedure for solving a problem
guaranteed to produce the correct result, provided the steps are followed correctly.
solution is th eoptmal solution
heuristic:
a rule of thumb, shortcut or strategy used to make problem solving more efficient when an exact solution is impractical or too costly.
not guaranteed to be correct or optimal, produces a “good enough” solution quickly
often used in complex problems
what is a data structure?
data structure: a way of organizing, managing and storing data in a computer so that it can be assesed and modified efficiently.
why do we need data structures?
efficient operations: crucial for allowing algorithms to perform operations like searching, sorting and adding data quickly and efficiently
managing complexity: help simplify the representation and management of complex relationships between data points.
examples of data structures
list: collection of data elements in a sequence
arrays: fixed size list where elements are stored in contiguous memory locations, accessing an element by its index is very fast.
linked lists: list where elements are not stored in contguous memory, each element contains the data and a reference to the next element in the sequence
queue: a “first in, first out” data structure, operations are “enqueue” (add) and “dequeue” (remove).
trees: non-linear data structure that organizes data in a hierarchical manner.
the relationship between algorithms and data structures
working together: algorithm needs a data structure to operate, choice of data structure can dramatically affect efficiency of algorithm
example: search algorithm needs data to be stored in an array or a tree to find a specific term.