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.

  • Selection sort
  • Bubble sort
  • Insertion sort
  • Merge sort
  • Heap sort …
• 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.