Please enable JavaScript.
Coggle requires JavaScript to display documents.
DATA & ALGORITHM - Coggle Diagram
DATA & ALGORITHM
Linear
Array
Appending to over the size of the current existing array.
In JS, array.push() is O(1) - as Arrays in JS is always dynamic
In C, it is O(1) - as only moving the pointer
In Java, it is O(n) as needs to create a new array and copy all the previous n elements to the new array.
Amortized time
-
-
-
-
-
Graph (Hierarchical)
- Weighted vs Unweighted
- Directed vs Undirected
Common ways to represent graph
- Adjacency matrix
- Adjacency List
-
-
-
-
Data Types
Primitive(Built in)
- Boolean
- Character
- Float
- Integer
- Pointer(Reference)
- ENUM
Composite(Derived | User Defined)Derived from more than one primitive type.(EG Array of Integers.)
- Array/Vector/List
- Record
- Union
- Set
AbstractMathematical model for data types - Defined by its behaviour in terms of possible operations on data of this type and behaviour of these operations.Abstract Data Types provides Abstraction : Hide details from the client/user programs.
- Collection
- Contrainer
- Graph
- Tree
- Queue
(You can implement using an array)
Common Operations on ADT
Algorithm Types
-
-
Traversal Methods
- Breadth First Search
- Depth First Search
- In Order
- Pre Order
- Post Order
Space Time Complexity
Asymptotic complexity = approximate measure of time complexityBig O Omega Theta are asymptotic notations that describe the upper, lower and tight bounds for the run time and we use those notations to describe the best, worse and expected time for particular inputs/scenario.Big O (Worst Case)
Theta (Average Case)
Omega (Best Case)Big O Omega ThetaBig O : how well a problem is solved. Big O is the language we use for talking about how long an algorithm takes to run.
Run time : How long it takes to run a certain problem through a function.**Good Code
- Readable
- Scalable [Big O]
2.1 Speed (CPU) TIME COMPLEXITY
Always Worse Case
Remove Constants 0(n/2+100) = O(n)
Different Input=Different Value O(a+b)
Drop Non-dominant Terms O(n+n^2) = O(n^2)
2.2 Memory (RAM) SIZE COMPLEXITY
Variables
Datastructures
Allocations
Functions
Big O does not measure things in second. Instead focusing on how quickly the runtime grows.
O(1) : Constant Time
O(n) : Linear Time !
O(n^2) : Quadratic [Nested Loops]
O(n!) : Factorial Time ! Oh No!Cheat sheet
-
Patterns
- Sliding Window
No window size = Kadane's algo
Kadane's algo is a DP algo
-