theory
Good Algorithms are based on these:
Corectness -> right output given input -> we can use tests and proofs to deduce if they are a good algorithm or not.
Efficiency -> we can use experiments and analysis to deduce if they are a good algorithm or not
Data type -POV of implementer
Abstract data type (ADT)
client POV
examples:
list,graph, heap,has table, tree, stack, queue
encapsulation -> program requests to implementation of function(), which returns the result to the program. -> key idea is that clients do not need to know the implementation, just need to get the correct result
localisation (??)
flexibility
can swap different implements smoothly.
the way we organise data influences the algorithm with which we process them => by knowing the ADT (Type, Operations), we can solve the problens correctly => by knowing Data Structure (Storage Space, Subroutines), we can solve the problems efficiently
Data Structures
Array
Item associated, fixed size sequence/collectIon of elements of the same type
Good Spatial Locality, usually because it stores over a contiguous memory space.
Linked List
item that points to the next item in the list.
dynamically sized collection of nodes that form a linear sequence.
no relation to their physical placement in memory.
Extension: Doubly Linked List
Extension: Circularly Linked List -> head is after the tail.
Stack
Last in First Out
(Like haw flakes - the last haw flak added into the stack is eaten first)
Queue
First in First Out
Like any queue, the early bird catches the worm.
Double-Ended Queue
Dynamic Arrays
No more fixed sized arrays
Amortisied cost of resizing: copying, doubling
Measuring Performance of a DSA:
Empiraically
Requires implementation to analyse
Hardware and software must be done controlled, or the performance results will not be fair.
Experiments can only be done for limited set of inputs
What to count for empirical?
Analytically
Does not require implementation to analyse
Independent of any hardware/software faults
Accounts for all inputs
Last updated