Scribd
Upload
21 views15 pages

Module 1 Problem Types

The document outlines important problem types in computer science, including sorting, searching, string processing, graph problems, combinatorial problems, geometric problems, and numerical problems. It also discusses various algorithms associated with these problems, such as sorting algorithms (e.g., merge sort, quick sort) and searching methods (e.g., binary search, linear search). Additionally, it categorizes data structures into primitive and non-primitive types, emphasizing the importance of understanding data structures for effective programming.

Uploaded by

vittalgawde1970
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views15 pages

Module 1 Problem Types

The document outlines important problem types in computer science, including sorting, searching, string processing, graph problems, combinatorial problems, geometric problems, and numerical problems. It also discusses various algorithms associated with these problems, such as sorting algorithms (e.g., merge sort, quick sort) and searching methods (e.g., binary search, linear search). Additionally, it categorizes data structures into primitive and non-primitive types, emphasizing the importance of understanding data structures for effective programming.

Uploaded by

vittalgawde1970
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

MODULE 1

IMPORTANT PROBLEM TYPES


&
FUNDAMENTALS OF DATA STRUCTURES

Prof. N. Guruprasad PROBLEM TYPES 1


Important problem types:
1) Sorting
2) Searching
3) String processing
4) Graph problems
5) Combinatorial problems
6) Geometric problems
7) Numerical problems

Prof. N. Guruprasad PROBLEM TYPES 2


SORTING:
Process of arranging the elements either in ascending /
descending order.

Sorting is used as an auxiliary step in several important


algorithms in other areas, e.g., geometric algorithms and data
compression.

Prof. N. Guruprasad PROBLEM TYPES 3


Sorting algorithms
1) Bubble sort
2) Selection sort
3) Insertion Sort
4) Quick sort
5) Merge Sort
6) Bucket sort
7) Address calculation sort
8) Shell sort
9) Heap sort

Prof. N. Guruprasad PROBLEM TYPES 4


Properties of sorting algorithm:

1) Stable: if algorithm preserves the relative order of


any two equal elements then the algorithm is stable.

Ex: you have two elements a[i] and a[j]


at location i and j

after sorting if a[i] and a[j[ are moved


to i’ and j’ such that i’ < j’ then it is stable.

Ex: MERGE SORT

Prof. N. Guruprasad PROBLEM TYPES 5


2) Place: if algorithm does not require an extra
memory space then it is said to be in place.

Ex: BUBBLE SORT

Prof. N. Guruprasad PROBLEM TYPES 6


SEARCHING:

deals with finding a given value, called a search key

1) Binary search
2) Linear search
3) Interpolation Search
4) Hashing

Prof. N. Guruprasad PROBLEM TYPES 7


STRING PROCESSING:
deals with manipulation of characters of strings.

String matching is a process of searching for a given word in a text.

Algorithms:
1) Using BRUTE FORCE method
2) Using BOYER MOORE algorithm
3) Using HORSPOOL’S algorithm

Prof. N. Guruprasad PROBLEM TYPES 8


GRAPH PROBLEMS:
defined as G = {V,E}
One of the oldest and most interesting areas in algorithms.

Typical Algorithms:
1) Travelling Salesman Problem
2) Shortest Path
3) Project scheduling
4) Graph coloring problem

Prof. N. Guruprasad PROBLEM TYPES 9


COMBINATORIAL PROBLEMS:

problems that involve permutation, combination or that satisfies


some constraints are called combinatorial problems.

Generally speaking, combinatorial problems are the most difficult


problems in computing

Ex: graph coloring problem – requires permutations and


combinations

Prof. N. Guruprasad PROBLEM TYPES 10


GEOMETRIC PROBLEMS:

Geometric algorithms deal with geometric objects such as


points, lines, and polygons.
Example:
1) closest-pair problem: given n points in the plane, find the
closest pair among them.
2) convex-hull problem: asks to find the smallest convex
polygon that would include all the points of a given set.

Prof. N. Guruprasad PROBLEM TYPES 11


NUMERIC PROBLEMS:

problems that involve mathematical objects of continuous nature:


solving equations and systems of equations, computing definite
integrals, evaluating functions, and so on.
The majority of such mathematical problems can be solved only
approximately.
Example:
1) GAUSS ELIMINATION method
2) NEWTON RAPHSON method

Prof. N. Guruprasad PROBLEM TYPES 12


Types of
DATA STRUCTURES

Prof. N. Guruprasad PROBLEM TYPES 13


DATA STRUCTURES

PRIMITIVE NON PRIMITIVE

int
LINEAR NON LINEAR

float
Arrays

char Stacks Trees Graphs

Queues

Linked
List

Prof. N. Guruprasad PROBLEM TYPES 14


Understanding Data Structures is critical if you
want to become a good programmer.

Prof. N. Guruprasad PROBLEM TYPES 15

You might also like