LinkedIn Course, part of Become a Programmer Learning Path.
- Space and time complexity.
- Input, output
- Classification: serial/ parallel, exact/ approximate, deterministic/non-deterministic
- Search Algorithms
- Sorting Algorithms.
- Computational Algorithms.
- Collection algorithms.
- Greatest Common Denominator (GCD) of two integers. == GCD of 20 and 8 = 4
- a > b divide a by b.
- if remainder is 0 stop so GCD is b
- otherwise set a to b and b to remainder and repeat until r is 0.
- Big-O notation:order of operation, usually describes worst case senaroi.
- O(1): constant time=> looking up a single element in an array.
- O(log n): logarithmic=> finding item in a sorted array with binary search.
- O(n): linear time=> searching an unsorted array for a specific value.
- O(nlogn): log-linear=> heap sort and merge sort.
- O(n^2): Quadratic=> not good like bubble sort, selection sort, insertion sort.
- Used to organize data so it can be processed.
- Arrays.
- Linked lists.
- Stacks and queues.
- Trees.
- Hash Tables.
- Collection of elements identified by index or key.
- Claculate item index: O(1).
- Insert or delete item at beginning: O(n)
- Insert of delete item in middle: O(n).
- Insert or delete item at the end: O(1)
- Collection of data elements called nodes.
- Contains references to the next node in the list.
- Hold whatever data the application needs.
- Elements can be easily inserted and removed.
- Underlying memory doesn't need to reorganized.
- Can't do constant time random item access.
- Item lookup is linear in time complexity O(n).
- Collection of elemens supports push and pop operations.
- The last item pushed is the first one popped.
- Queues: supports adding and removing items.
- First item added is the first time out.
- Expression processing => stack.
- Backtracking => stack.
- Order processing => queue.
- Messaging => queue.
- Assosaitive arrays.
- Maps keys to thier assosaitive values.
- Key to value mapping are unique.
- Hash tables are typically very fast.
- For small dataset, array are usually more efficient.
- Hash tables don't enter enteries in predictible way.
- A function calls itself.
- Recursive functions terminates using breaking conditions which prevents infinte calls.
- Every time function is called, the previous step is saved.
- Sorting is build-in in most modern languages.
- Bubble sort.
- Merge sort.
- Quick sort.
- Simple to understand and implement.
- Performance = O(n^2)
- Not a practical solution.
- Divide and conquer algorithm.
- Uses recursion.
- Performs well on large set of data.
- Complexity of merge sort = O(nlogn).
- Divide and conquer algorithm.
- Uses recursion to perform sorting.
- Generally performs better than merge sort O(nlogn)
- Worst case is O(n^2) when data is mostly sorted already.
- Selection of pivot point.