lookichild.blogg.se - Basic data structures and algorithms

Pattern matching/searching is one of the most important problem in Computer Science. RSA also uses modular arithmetic along with binary exponentiation. Calculation of large powers of a number is mostly required in RSA encryption.Not only this, the method is also used for computation of powers of polynomials and square matrices. What if I told you it can be done in 5 iterations?Įxponentiation by squaring or Binary exponentiation is a general method for fast computation of large positive integer powers of a number in O(log 2N). Normally we’d iterate 32 times and find the result. There are many DP algorithms and applications but I’d name one and blow you away, Duckworth-Lewis method in cricket.So you didn’t need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say ‘remembering stuff to save time later’ *writes down another “1+” on the left* What about that? *writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper* What’s that equal to? We solve the subproblems, remember their results and using them we make our way to solve the complex problem, quickly. We can also use Set data structure for this operation.ĭynamic programming (DP) is a method for solving a complex problem by breaking it down into simpler subproblems. To perform the check if a value already exists in a list.In routers, to store IP address -> Path pair for routing mechanisms.Choosing a good hash function depends upon the scenario. Idea is to use an appropriate hash function which does the key -> value mapping. The data structure is referred as Hash-Map or Hash-Table or Dictionary that maps keys to values, efficiently. Previously we relied on Sorting+Binary Search to look for index whereas now we use hashing. Hash lookup is currently the most widely used technique to find appropriate data by key or ID. Finding shortest path between two cities in a map and many other such applications.Used in artificial intelligence to build bots, for instance a chess bot.

Used by search engines for web-crawling.

We wouldn’t go deep into how DFS/BFS work but will see how they are different through following animation.

Used to debug in git through git bisectĭepth/Breadth First Search (in Graph data structures)ĭFS and BFS are tree/graph traversing and searching data structures.

When you search for a name of song in a sorted list of songs, it performs binary search and string-matching to quickly return the results.

Idea is to repeatedly divide in half the portion of the list that could contain the item, until we narrow it down to one possible item.

Sorting by price, popularity etc in e-commerce websitesīinary Search (in linear data structures)īinary search is used to perform a very efficient search on sorted dataset.

Some examples where you can find direct application of sorting techniques include: More importantly one should know when and where to use them. Depending upon requirement you may want to use any of these. Though every major programming language has built-in sorting libraries, it comes in handy if you know how they work. Idea is to arrange the items of a list in a specific order. Sorting is the most heavily studied concept in Computer Science.

This list is prepared keeping in mind their use in competitive programming and current development practices. Today, We will see what they do and where they are used with simplest examples.

In programmers life algorithms and data structures is most important subject if they want to go out in the programming world and make some bucks.