Can anyone suggest real-world problems in this algorithms Insertion sort, Breath first search, Depth first search or Topological sorting? Thank you.
Real-world examples of recursion
I saw sample here But I need is specific problems for insertion sort, Breath first search, Depth first search or Topological sorting algorithms.
I wish you can Help me.
How more real can it get than our daily, humdrum lives?
Insertion sort is what we (or at least I) most commonly use when we need to sort things. Consider a deck of cards - one would go over them one by one, put the smallest ones at the front, smaller behind them, etc. Or a pile of paperwork which needs to be sorted by date, same algorithm.
In CS, insertion-sort is less commonly used because we have much better algorithms (qsort and merge-sort come to mind). A human can do them as well, but that'd be a much more tedious task indeed.
Breadth-first search's use is in the name: When we want to go over a tree horizontally, and not vertically. Let's say you heard your family is connected to Ilya Repin, a Russian artist. You go to the attic, crack open the giant wooden chest that's been gathering dust, and take out the old family tree which dates back to the 19th century (doesn't everyone have that?). You know he's closer to the top of the tree than he is to the bottom, so you go breadth-first: Take the first line, followed by the second, and so on...just a little more...Efim Repin...bingo!
If Ilya Repin happened to be in the leftmost branch of the tree, then depth-first would've made more sense. However, in the average case, you'd want to go breadth-first because we know our target is closer to the root than it is to the leafs. In CS there are a buttload of usage cases (Cheney's Algorithm, A*, etc. you can see several more on wikipedia).
Depth-first search is used when we... drumroll ...want to go to the depth of the tree first, travel vertically. There are so many uses I can't even begin, but the simplest and most common is solving a cereal-box maze. You go through one path until you reach a dead-end, and then you backtrack. We don't do it perfectly, since we sometimes skip over a path or forget which ones we took, but we still do it.
In CS, there're a whole lot of usage cases, so I'll redirect you to wikipedia again.
Topological sort some of us use in the back of our heads, but it's easily seen in chefs, cooks, programmers, anyone and everyone who has to do an ordered set of tasks. My grandmother made the best Canneloni I've eaten, and her very simple recipe was constructed of several simple steps (which I've managed to forget, but here are their very general outline): Making the "pancake" wrapper, making the sauce and wrapping them together. Now, we can't wrap these two up without making them, so naturally, we first have to make the wrapper and sauce, and only then wrap 'em.
In CS it's used for exactly the same thing: scheduling. I think Excel uses it to calculate dependant spreadsheet formulas (or maybe it just uses a simple recursive algorithm, which may be less efficient). For some more, you can see our good friend wikipedia and a random article I found.
I work with Hierarchical Datastructures, and always in need of BFS to find objects i need nested under a specific root...
e.g. Find(/Replace)
some-times (significally less) i use DFS in order to check some design constraints that cannot be evaluated without investigating the leafs.
though not used by me, and not exactly BFS,
but GPS navigation software use A* to search for a good path,
Which is kid of a "Weighted BFS"
Insertion sort - none, it's good for learning. Outside computers it is used often to sort, for example, cards. In real-world merge sort or quick sort are better.
BFS - finding connected nodes, finding shortest paths. Base for Dijkstra's algorithm and A* (faster version of Dijkstra's).
DFS - finding connected nodes, numbering nodes in tree.
Topological sorting - finding correct order of tasks.
