by BehindJava
What are the most important Problem types in Data Structures
In this blog, we are going to learn about important Problem types in Data Structures.
Important Problem Types
 Sorting
 Searching
 String processing
 Graph problems
 Combinatorial problems
 Geometric problems
 Numerical problems
1. Sorting

Rearrange the items of a given list in ascending order.
 Input: A sequence of n numbers <a1, a2, …, an>
 Output: A reordering <a´1, a´2, …, a´n> of the input sequence such that a´1≤ a´2 ≤ … ≤ a´n.

Why sorting?
 Help’s searching
 Algorithms often use sorting as a key subroutine.

Sorting key
 A specially chosen piece of information used to guide sorting. I.e., sort student records by names.

Examples of sorting algorithms.
 Evaluate sorting algorithm complexity: the number of key comparisons.

Two properties
 Stability: A sorting algorithm is called stable if it preserves the relative order of any two equal elements in its input.
 In place : A sorting algorithm is in place if it does not require extra memory, except, possibly for a few memory units.
2. Searching
 A string is a sequence of characters from an alphabet.
 Text strings: letters, numbers, and special characters.
 String matching: searching for a given word/pattern in a text.
3. String Processing
 A string is a sequence of characters from an alphabet.
 Text strings: letters, numbers, and special characters.
 String matching: searching for a given word/pattern in a text.
4. Graph Problems
 Informal definition: A graph is a collection of points called vertices, some of which are connected by line segments called edges.
 Modeling reallife problems: Modeling WWW, communication networks, Project scheduling …
 Examples of graph algorithms: Graph traversal algorithms, Shortestpath algorithms, Topological sorting.
 Other graph problems: Traveling salesman problem, Graph coloring problem.
5. Combinatorial problems
 These problems asked to find a combinatorial object such as permutation, combination or a subset that satisfies certain constraints and some derived properties.
 Combinatorial problems are difficult because Combinatorial objects grow extremely fast with problem size. No known algorithms for solving these problems.
Ex: traveling salesman pbm, graph coloring pbm.
6. Geometric Problem
 It deals with geometric objects such as points, lines and polygons.

Two classic geometric problems:
 Closest Pair Problem: Given n points in the plain, find the closest pair among them.
 Convex hull problem: It finds the smallest convex polygon that would include all points of a given set.
7. Numerical Problems
 Problems that involve mathematical objects of continuous nature. For example Solving equations, evaluating functions, etc.,
 Most numerical problems are solved approximately.
 Difficulties in numerical problems: Real numbers are represented approximately. Hence round off error will occur.