Data Structures Through C

Learn the fundamentals of Data Structures through C

Yashavant Kanetkar

• Publisher: BPB Publications
• Year: 2020
• ISBN:
  9789388511391
• Topic: Computer Science
• Subtopic: Programming Algorithms
• Index: Computer Science

Experience Data Structures C through animationsThere are two major hurdles faced by anybody trying to learn Data Structures:Most books attempt to teach it using algorithms rather than complete working programsA lot is left to the imagination of the reader, instead of explaining it in detail. This is a different Data Structures book. It uses a common language like C to teach Data Structures. Secondly, it goes far beyond merely explaining how Stacks, Queues, and Linked Lists work. The readers can actually experience (rather than imagine) sorting of an array, traversing of a doubly-linked list, construction of a binary tree, etc. through carefully crafted animations that depict these processes. All these animations are available on the downloadable DVD. In addition it contains numerous carefully-crafted figures, working programs and real world scenarios where different data structures are used. This would help you understand the complicated operations being performed an different data structures easily. Add to that the customary lucid style of Yashavant Kanetkar and you have a perfect Data Structures book in your hands. KEY FEATURES• Strengthens the foundations, as detailed explanation of concepts are given • Focuses on how to think logically to solve a problem• Algorithms used in the book are well explained and illustrated step by step.• Help students in understanding how data structures are implemented in programs. WHAT WILL YOU LEARN• Analysis of Algorithms, Arrays, Linked Lists, Sparse Matrices• Stacks, Queues, Trees, Graphs, Searching and Sorting WHO THIS BOOK IS FORStudents, Programmers, researchers, and software developers who wish to learn the basics of Data structures.AUTHOR BIOYashavant Kanetkar Through his books and Quest Video Courses on C, C++, Java, Python, Data Structures,.NET, IoT, etc. Yashavant Kanetkar has created, molded and groomed lacs of IT careers in the last three decades. Yashavant's books and Quest videos have made a significant contribution in creating top-notch IT manpower in India and abroad. Yashavant's books are globally recognized and millions of students / professionals have benefitted from them. Yashavant's books have been translated into Hindi, Gujarati, Japanese, Korean and Chinese languages. Many of his books are published in India, USA, Japan, Singapore, Korea and China. Yashavant is a much sought after speaker in the IT field and has conducted seminars/workshops at TedEx, IITs, IIITs, NITs and global software companies. Yashavant has been honored with the prestigious "Distinguished Alumnus Award" by IIT Kanpur for his entrepreneurial, professional and academic excellence. This award was given to top 50 alumni of IIT

Chapter 01

Analysis of Algorithms

Justifying the means

Why This Chapter Matters?

The dictum “ends justify the means” doesn’t hold good in Computer Science. Just because we got the right answer (end) does not mean that the method (means) that we employed to obtain it was correct. In fact, the efficiency of obtaining the correct answer is largely dependent on the method employed to obtain it. Hence scientific analysis of performance of the method is very important.

The method of solving a problem is known as an algorithm. More precisely, an algorithm is a sequence of instructions that act on some input data to produce desired output in a finite number of steps. An algorithm must have the following properties:

(a) Input - An algorithm must receive some input data supplied externally.

(b) Output - An algorithm must produce at least one output as the result.

(c) Finiteness - No matter what the input might be, the algorithm must terminate after a finite number of steps. For example, a procedure which goes on performing a series of steps infinitely is not an algorithm.

(d) Definiteness - The steps to be performed in the algorithm must be clear and unambiguous.

(e) Effectiveness - One must be able to perform the steps in the algorithm without applying any intelligence. For example, the step—Select three numbers which form a Pythagorean triplet—is not effective.

Why Analyze Algorithms?

Multiple algorithms may exist for solving a given problem. To determine which algorithm is more efficient than others, we need to analyze the algorithms. This analysis is done by comparing the time and/or space required for executing the algorithms. In this chapter we would analyze algorithms on the basis of time. We would carry out space based analysis in later chapters.

While doing time based analysis of algorithms we do not use conventional time units like seconds or minutes required for executing the algorithms. There are two reasons for this.

(a) A worse algorithm may take less time units to execute if we move it to a faster computer, or use a more efficient language.

(b) We are interested in relative efficiency of different algorithms rather than the exact time for one.

So instead of time units we consider the number of prominent operations that are carried out by the algorithm. For example, in a searching algorithm we would try to determine the number of comparisons that are done to search a value in a list of values. Or in an algorithm to add two matrices, we might determine the number of arithmetic operations it performs.

Once we identify the prominent operations in an algorithm, we try to build a function that relates this number of operations to the size of the input. Once these functions are formed for algorithms under consideration, we can compare them by comparing the rate at which the functions grow as the input gets larger. This growth rate is critical since there are situations where one algorithm needs fewer operations than the other when the input size is small, but many more when the input size becomes larger.

Thus analysis of algorithms gives us a scientific reason to determine which algorithm should be chosen to solve the problem.

What to Consider, What to Ignore?

It is very important to decide which operations to consider and which operations to ignore while analyzing an algorithm. For this we must first identify which is the significant time consuming operation(s) in the algorithm. Once that is decided, we should determine which of these operations are integral to the algorithm and which merely contribute to the overheads. There are two classes of operations that are typically chosen for the significant operation—comparison or arithmetic.

For example, in Searching and Sorting algorithms the important task being done is the comparison of two values. While searching the comparison is done to check if the value is the one we are looking for, whereas in sorting the comparison is done to see whether values being compared are out of order.

The arithmetic operations fall under two groups—additive and multiplicative. Additive operators include addition, subtraction, increment, and decrement. Multiplicative operators include multiplication, division, and modulus. These two groups are counted separately because multiplication operations take longer time to execute than additions.

Let us now see which operations we should ignore while analyzing an algorithm. Suppose we have an algorithm that counts the number of characters in a file. This algorithm is given below.

Count = 0

While there are more characters in the file do

Increment Count by 1
Get the next character

End while

Print Count

If there are 500 characters present in the file we need to initialize Count once, check the condition 500 + 1 times (the +1 is for the last check when the file is empty), and increment the counter 500 times. Thus the total number of operations would be

Initializations - 1

Increments - 500

Conditional checks - 500 + 1

Printing - 1

As can be seen from these numbers, the number of increments and conditiona...