Fundamental Computer Science Concepts & Algorithms
Classified in Computers
Written on in 
English with a size of 1.64 MB
Arithmetic Progressions (AP)
Sum of terms = n[(1st term + last term)]/2
Geometric Progressions (GP)
Sum of terms = [1st term(1 - quotientn)/(1 - quotient)] (Swap positions of 1 & quotient if quotient > 1)
Logarithms
- loga(x/y) = logax - logay
- logaxn = nlogax
- logab = (logcb/logca)
Permutations
For a set of n objects: The total number of permutations is n!
For arranging 'r' objects from a set of 'n' objects: The number of permutations is nPr = n! / (n-r)!. (e.g., ways to arrange 3 objects from a set of 5 is 5 * 4 * 3, since there are 5 possibilities for the first object, followed by 4, then 3.)
Combinations
For selecting 'r' objects from a set of 'n' objects: The number of combinations is nCr = n! / (r! * (n-r)!). (Divide by r! since there are r! ways to arrange a set of r things and order for combinations doesn't matter. e.g., combinations for 3 objects from a set of 5 is (5*4*3)/3!)
Algorithmic Complexity (Big O Notation)
(Increasing complexity down the table)
| Complexity Type | Big O | Remarks |
|---|---|---|
| Constant | O(1) | Not affected by input size n. When n doubles, number of operations remains the same. |
| Logarithmic | O(log n) | When n doubles, number of operations increases by 1. When n increases tenfold, number of operations increases by 1. |
| Linear | O(n) | When n doubles, number of operations also doubles. |
| Linearithmic | O(n log n) | Often seen in decomposition or recursive algorithms. |
| Polynomial | O(nk) | When n doubles, number of operations increases by 2k. |
| Exponential | O(kn) | When n increases by 1, number of operations increases by k. |
| Factorial | O(n!) | When n increases by 1, number of operations increases by n. |
Linear Search
Begin from the start. Compare all the way to the end or until the element is found.
Complexity:
Binary Search
- Array must be sorted.
- Search Method: Initialize
lower = -1,upper = n+1. Calculatemid = (lower + upper) // 2. If the search value is greater than the element atmid, setlower = mid. Continue untillower + 1 = upper.
Number of comparisons to find an element:
Complexity:
Insertion Sort
Number of comparisons also includes situations where numbers are compared but not swapped (e.g., compared to ensure it is larger than the previous number).
Recursion Fundamentals
- Base Case: The simplest possible case that cannot be further reduced.
- Reduction Step: Rules that reduce other cases towards the base case.
Recursive Merge Sort
Stack Data Structure
- Last In, First Out (LIFO)
Stack Operations
- Push: Adds a new data element to the top of the stack.
- Peek: Allows inspection of the data element at the top of the stack without removing it.
- Pop: Removes and returns the data element at the top of the stack.
Queue Data Structure
- First In, First Out (FIFO)
Queue Operations
- Enqueue: Adds a new data element to the tail of the queue.
- Peek: Allows inspection of the data element at the head of the queue without removing it.
- Dequeue: Removes and returns the data element from the head of the queue.
Priority Queue
- Smaller numbers have higher priority.
- Earlier alphabets have higher priority.
Priority Queue Operations
- Enqueue: Adds a new data element to the queue based on its priority.
- Peek: Allows inspection of the data element with the highest priority without removing it.
- Dequeue: Removes and returns the data element with the highest priority.
Binary Trees
- Full Binary Tree: Each node has 0 or 2 children.
- Complete Binary Tree: Every level, except possibly the deepest, is completely filled. At the deepest level (height h), all nodes must be as far left as possible.
- Perfect Binary Tree: All leaf nodes (nodes with no children) have the same depth. All internal nodes have a degree of 2 (meaning they have two children).
