by BehindJava

# What are the most important Problem types in Data Structures

Home » datastructures » 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

1. Sorting
2. Searching
3. String processing
4. Graph problems
5. Combinatorial problems
6. Geometric problems
7. 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 real-life problems: Modeling WWW, communication networks, Project scheduling …
• Examples of graph algorithms: Graph traversal algorithms, Shortest-path 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.