Important Problem Types

1.4 Important Problem Types

• Sorting

• Searching

• String processing

• Graph problems

• Combinatorial problems

• Geometric problems

• Numerical problems

sorting algorithm is an algorithm that puts elements of a list in a certain order. The most- used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions:

1. The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order);

2. The output is a permutation, or reordering, of the input.

Since the dawn of computing, the sorting problem has attracted a great deal of research, per- haps due to the complexity of solving it efficiently despite its simple, familiar statement. For example, bubble sort was analyzed as early as 1956.[1] Although many consider it a solved problem, useful new sorting algorithms are still being invented (for example, library sort was first published in 2004). Sorting problem provides a gentle introduction to a variety of core algorithm concepts, such as big O notation, divide and conquer algorithms, data structures, randomized algorithms, best, worst and average case analysis, time-space tradeoffs, and lower bounds.

Searching : In computer science, a search algorithm, broadly speaking, is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots of an equation with integer variables; or a combination of the two, such as the Hamiltonian circuits of a graph.Searching algorithms are closely related to the concept of dictionaries. Dictionaries are data structures that support search, insert, and delete operations. One of the most effective representations is a hash table. Typically, a simple function is applied to the key to determine its place in the dictionary. Another efficient search algorithms on sorted tables is binary search

String processing:String searching algorithms are important in all sorts of applications that we meet everyday. In text editors, we might want to search through a very large document (say, a million characters) for the occurence of a given string (maybe dozens of characters). In text retrieval tools, we might potentially want to search through thousands of such documents (though normally these files would be indexed, making this unnecessary). Other applications might require string matching algorithms as part of a more complex algorithm (e.g., the Unix program ``diff'' that works out the differences between two simiar text files). Sometimes we might want to search in binary strings (ie, sequences of 0s and 1s). For example the ``pbm'' graphics format is based on sequences of 1s and 0s. We could express a task like ``find a wide white stripe in the image'' as a string searching problem.

Graph problems:Graph algorithms are one of the oldest classes of algorithms and they have been studied for almost 300 years (in 1736 Leonard Euler formulated one of the first graph problems Königsberg Bridge Problem)

There are two large classes of graphs:

• directed graphs (digraphs )

• undirected graphs

Some algorithms differ by the class. Moreover the set of problems for digraphs and undirected graphs are different. There are special cases of digraphs and graphs that have their own sets of problem. One example for digraphs will be program graphs. Program graphs are important in compiler construction and were studied in detail after the invention of the computers.

Graphs are made up of vertices and edges. The simplest property of a vertex is its degree, the number of edges incident upon it. The sum of the vertex degrees in any undirected graph is twice the number of edges, since every edge contributes one to the degree of both adjacent vertices. Trees are undirected graphs which contain no cycles. Vertex degrees are important in the analysis of trees. A leaf of a tree is a vertex of degree 1. Every -vertex tree contains edges, so all non-trivial trees contain at least two leaf vertices.

Among classic algorithms/problems on digraphs we can note the following:

• Reachability. Can you get to B from A?

• Shortest path (min-cost path). Find the path from B to A with the minimum cost (de- termined as some simple function of the edges traversed in the path) (Dijkstra's and Floyd's algorithms)

• Visit all nodes. Traversal. Depth- and breadth-first traversals

• Transitive closure. Determine all pairs of nodes that can reach each other (Floyd's al- gorithm)

• Dominators a node d dominates a node n if every path from the start node to n must go through d. Notationally, this is written as d dom n. By definition, every node dominates itself. There are a number of related concepts:

o immediate dominator

o pre-dominator

o post-dominator.

o dominator tree

• Minimum spanning tree. A spanning three is a set of edges such that every node is

reachable from every other node, and the removal of any edge from the tree eliminates the reachability property. A minimum spanning tree is the smallest such tree. (Prim's and Kruskal's algorithms)

Combinatorial problems: From a more abstract perspective ,the traveling Salesman problem and the graph coloring problems of combinatorial problems are problems that a task to find a combinatorial object-such as a permutation a combination ,or a subset-that satisfies certain constraints and has some desired property.Generally speaking, combinatorial problems are the most difficult problems in computing ,from both the theoretical and practical standpoints. Their difficulty stems from the following facts. First ,the number of combinatorial objects typically grows extremely fast with a problem size , reaching unimaginable magnitudes even moderate-sized intances. Second, there are no known algorithms for solving most such problems exactly in an acceptable amount of time. Moreover, most computer scientist believe such algorithms do not exist. This conjecture has been neither proved nor disproved ,and it remains the most important resolved issue in theoretical computer science.

Some combinatorial problems can be solved by efficient algorithms, but they should be considered fortunate to the rule. The shortest-problem mentioned earlier is among such exceptions.

Geometric Problems

Geometric algorithms deal with geometric objects such as points , lines, and polygons. Ancient Greeks were very much interested in developing procedures for solving a variety of geometric problems including problems of constructing simple geometric shapes-triangles

,circles and so on-with an unmarked ruler and a compass. Then ,for about2000 years ,intense interest in geometrics disappeared, to be resurrected in the age of computers-no more rulers and compasses, just bits, bytes, and good old human ingenuity. Of course, today people are interested in geometric algorithms with quite different applications in mind, such as computer Graphics, robotics, and tomography.

We will discuss algorithms for only two classic problems of computational geometry: the closest pair problem and the convex-hull problem. The closest-pair problem is self explanatory :given n points in the plain, find the closest pair among them. The convex hull problem is to find the smallest convex polygon that would include all points of a given set.

Numerical Problems

Numerical problems, another large area of applications are problems that involve mathematical objects of continuous nature: solving equations and system of equation, computing definite integrals, evaluating functions and so on. The majority of such mathematical problems can be solved only approximately. Another principal difficulty stems from the fact that such problem typically requires manipulating real numbers, which can be represented in computer only approximately. Moreover, a large number of arithmetic operations performed on approximately represented numbers can lead to an accumulation of the round-off error to a point where it can drastically distort an output produced by a seemingly sound algorithm.

Many sophisticated algorithms have been developed over the years in this area ,and they continue to play a critical role in many scientific and engineering applications. But in the last 25years or so, the computing industry has shifted its focus into business application .These new application require primary algorithms for information storage, retrieval ,transportation through networks and presentation to users. As a result of this revolutionary change, numerical analysis has lost formerly dominating position in both industry and computer science pro- grams. Still, it is important for any computer-literate person to have at least a rudimentary idea about numerical algorithms.