An algorithm - a precise, unambiguous set of instructions designed to solve a problem or perform a task.
Donald Knuth says… An algorithm:
- Is finite
- Is precisely defined
- Has input
- Has output
- Must be effective
Algorithms and Data Structures Interview - Deckly Overview | HackerEarth
Practice Big-O complexities of common algorithms used in .NET and Computer Science.
- Searching Algorithms (Binary Search)
- Sorting Algorithms (Quick Sort, merge Sort, ...)
- Graph Algorithms
Complexity explained with Big O Notation:
- O(1) - constant time (access an array element by index)
- O(n) - proportional time to input (linear search, simple loop)
- O(log n) - slowly grows based on input (binary search)
- O(n log n) - grows a bit more (merge sort, quick sort, heap sort)
- O(n^2) - impractical for large inputs (bubble, insertion or selection sort)
- O(2^n) - exponential time (naive Knapsack, some recursive algorithms)
- O(n!) - grows extremely fast (brute force combinatoric problems)
- Divide and Conquer (principle of problem decomposition and recursive problem solving)
- Dynamic programming (principle of overlapping subproblems and optimal substructure)
- Graph Traversal (visiting all the vertices and edges in a graph)
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
- Dijkstra's Algorithm (optimal path finding)
Recursion: a method where the solution to a problem depends on solutions to smaller instances of the same problem.
- Key Concept: A function calls itself to solve sub-problems.
- Relies and a base and recursive case.
- Can provides a clear and elegant way to solve complex problems.
Algorithms | Computer science | Computing | Khan Academy Algorithms by Jeff Erickson Algorithms Courses on the WWW CS 161 - Design and Analysis of Algorithms