Guilan Faculty of Engineering
Today we are going to be talking about the Importance of Algorithms
in Programming and providing their usage, optimization after
The main propose of this is to help you have a clear view of algorithms or some basic knowledge.
What’s An Algorithm?
Algorithms are sets of rules to be followed in calculation or other problem solving by computer.
After The correctness of an algorithm to solve all the test cases, the most important thing is runtime.
Computer Scientists typically talk about the runtime relative to the size of input. If the input consists of N integers, an algorithm witch has a runtime proportion to N2 represent as O(N2) means that this algorithm terminate and complete after doing N2 operations.
An Example Comparison
As a computer science student you all know at least one sorting algorithm, we are going to compare runtime of Bubble Sort, The most famous sorting algorithm with O(N2) runtime and Merge Sort , Another well-known sorting algorithm with O(NlogN) when the input size is a bit large. Also we can estimate that a normal computer complete 108 operation per second.
As you know 100 seconds so differs from within a second for a user waiting. And we can understand that just finding a correct way to solve problem is not enough we need to do in in efficient way. N2 is not so bad. There are some algorithms with N! or 2N runtime just imagine how terrible will they work when the size of input get bigger.
|Name||Example or Description|
|Brute Force||Very General – Check All Possible Candidates|
|Divide and Conquer||Modular Power – Merge Sort|
|Dynamic Programming||Knapsack Problem – Longest Increasing Sequence|
|Max - Flow||Airline Scheduling|
|Greedy||Prim ( Minimum Spanning Tree ) – Activity Selection Problem|
|DFS||Connected Neighbors In Graph – Detecting Cycle In Graph|
|BFS||Shortest Path In 2dgrid|
|Binary Search||Finding Element In Sorted Array - Longest Increasing Sequence|
Modular Power Problem
We need to design a fast algorithm getting 3 parameters a, n and k and return a^n mod k . Where the mod means remind divisor and you can use it as % sign in c like languages.
I will explain the both efficient and inefficient solutions.
The basic math rules used below as you all know by your high school knowledge.
N.M mod k=N mod k .M mod K
We do the calculation easily just by one loop and then return the output. The runtime is O(N).
We use the Divide and Conquer way and recursively call the function by half n. and if n was odd we return rec.rec.a mod k because we drop the floating part of the division. By squaring it we will get an-1 mod k so we multiply it to another a mod k to reach an mod k. The runtime is O(logN).
When the n is even we haven’t lost anything and just return the square of sub problem in mod k.
We also have a stop point at n=0.
If we replace Int with Unsigned Long Long Int we can use solution for numbers up to 1020 .
As a final conclusion we will compare runtime of these two solutions of Modular Power Problem.
Even when we use a super computer that perform 1000 times faster than normal computers it will terminates after 31 years. So we understand the real importance of algorithms, even more than such expensive super computer in this example.
Download PDF Version
Recommended Books and links for learning Algorithms
Introduction to Algorithms _ Thomas H.Cormen
Art of Programming Contest
TopCoder Tutorials For Algorithms
GeeksForGeeksTutorials For Algorithms