Sachi Nandan Mohanty - Data Structure and Algorithms Using C++

Здесь есть возможность читать онлайн «Sachi Nandan Mohanty - Data Structure and Algorithms Using C++» — ознакомительный отрывок электронной книги совершенно бесплатно, а после прочтения отрывка купить полную версию. В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. Жанр: unrecognised, на английском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.

Data Structure and Algorithms Using C++: краткое содержание, описание и аннотация

Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «Data Structure and Algorithms Using C++»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.

Everyone knows that programming plays a vital role as a solution to automate and execute a task in a proper manner. Irrespective of mathematical problems, the skills of programming are necessary to solve any type of problems that may be correlated to solve real life problems efficiently and effectively. This book is intended to flow from the basic concepts of C++ to technicalities of the programming language, its approach and debugging. The chapters of the book flow with the formulation of the problem, it’s designing, finding the step-by-step solution procedure along with its compilation, debugging and execution with the output. Keeping in mind the learner’s sentiments and requirements, the exemplary programs are narrated with a simple approach so that it can lead to creation of good programs that not only executes properly to give the output, but also enables the learners to incorporate programming skills in them. The style of writing a program using a programming language is also emphasized by introducing the inclusion of comments wherever necessary to encourage writing more readable and well commented programs. As practice makes perfect, each chapter is also enriched with practice exercise questions so as to build the confidence of writing the programs for learners. The book is a complete and all-inclusive handbook of C++ that covers all that a learner as a beginner would expect, as well as complete enough to go ahead with advanced programming. This book will provide a fundamental idea about the concepts of data structures and associated algorithms. By going through the book, the reader will be able to understand about the different types of algorithms and at which situation and what type of algorithms will be applicable.

Data Structure and Algorithms Using C++ — читать онлайн ознакомительный отрывок

Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «Data Structure and Algorithms Using C++», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.

Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Deletion

Merging

Sorting

Searching

1.3 Algorithm

The step by step procedure to solve a problem is known as the ALGORITHM.An algorithm is a well-organized, pre-arranged, and defined computational module that receives some values or set of values as input and provides a single or set of values as out put. These well-defined computational steps are arranged in sequence, which processes the given input into output.

An algorithm is said to be accurate and truthful only when it provides the exact wanted output.

The efficiency of an algorithm depends on the time and space complexities. The complexity of an algorithm is the function which gives the running time and/or space in terms of the input size.

Steps Required to Develop an Algorithm

Finding a method for solving a problem. Every step of an algorithm should be defined in a precise and in a clear manner. Pseudo code is also used to describe an algorithm.

The next step is to validate the algorithm. This step includes all the steps in our algorithm and should be done manually by giving the required input, perform the required steps including in our algorithm and should get the required amount of output in a finite amount of time.

Finally implement the algorithm in terms of programming language.

Mathematical Notations and Functions

❖ Floor and Ceiling Functions

Floor function returns the greatest integer that does not exceed the number.

Ceiling function returns the least integer that is not less than the number.

❖ Remainder FunctionTo find the remainder “mod” function is being used as

❖ To find the Integer and Absolute value of a numberINT(5.34) = 5 This statement returns the integer part of the numberINT(- 6.45) = 6 This statement returns the absolute as well as the integer portion of the number

❖ Summation SymbolTo add a series of number as a1+ a2 + a3 +............+ an the symbol Σ is used

❖ Factorial of a NumberThe product of the positive integers from 1 to n is known as the factorial of n and it is denoted as n!.

Algorithemic Notations

While writing the algorithm the comments are provided with in [ ].

The assignment should use the symbol “: =” instead of “=”

For Input use Read : variable name

For output use write : message/variable name

The control structures can also be allowed to use inside an algorithm but their way of approaching will be some what different as

Simple If

If condition, then: Statements [end of if structure]

If...else

If condition, then: Statements Else : Statements [end of if structure]

If...else ladder

If condition1, then: Statements Else If condition2, then: Statements Else If condition3, then: Statements ………………………………………… ………………………………………… ………………………………………… Else If conditionN, then: Statements Else: Statements [end of if structure]

LOOPING CONSTRUCT

Repeat for var = start_value to end_value by step_value Statements [end of loop] Repeat while condition: Statements [end of loop] Ex : repeat for I = 1 to 10 by 2 Write: i [end of loop]

OUTPUT

1 3 5 7 9

1.4 Complexity of an Algorithm

The complexity of programs can be judged by criteria such as whether it satisfies the original specification task, whether the code is readable. These factors affect the computing time and storage requirement of the program.

Space Complexity

The space complexity of a program is the amount of memory it needs to run to completion. The space needed by a program is the sum of the following components:

A fixed part that includes space for the code, space for simple variables and fixed size component variables, space for constants, etc.

A variable part that consists of the space needed by component variables whose size is dependent on the particular problem instance being solved, and the stack space used by recursive procedures.

Time Complexity

The time complexity of a program is the amount of computer time it needs to run to completion. The time complexity is of two types such as

Compilation time

Runtime

The amount of time taken by the compiler to compile an algorithm is known as compilation time. During compilation time it does not calculate for the executable statements, it calculates only the declaration statements and checks for any syntax and semantic errors.

The run time depends on the size of an algorithm. If the number of instructions in an algorithm is large, then the run time is also large, and if the number of instructions in an algorithm is small, then the time for executing the program is also small. The runtime is calculated for executable statements and not for declaration statements.

Suppose space is fixed for one algorithm then only run time will be considered for obtaining the complexity of algorithm, these are

Best case

Worst case

Average case

Best Case

Generally, most of the algorithms behave sometimes in best case. In this case, algorithm searches the element for the first time by itself.

For example: In linear search, if it finds the element for the first time by itself, then it behaves as the best case. Best case takes shortest time to execute, as it causes the algorithms to do the least amount of work.

Worst Case

In worst case, we find the element at the end or when searching of elements fails. This could involve comparing the key to each list value for a total of N comparisons.

For example in linear search suppose the element for which algorithm is searching is the last element of array or it is not available in array then algorithm behaves as worst case.

Average Case

Analyzing the average case behavior algorithm is a little bit complex than the best case and worst case. Here, we take the probability with a list of data. Average case of algorithm should be the average number of steps but since data can be at any place, so finding exact behavior of algorithm is difficult. As the volume of data increases, the average case of algorithm behaves like the worst case of algorithm.

1.5 Efficiency of an Algorithm

Efficiency of an algorithm can be determined by measuring the time, space, and amount of resources it uses for executing the program. The amount of time taken by an algorithm can be calculated by finding the number of steps the algorithm executes, while the space refers to the number of units it requires for memory storage.

1.6 Asymptotic Notations

The asymptotic notations are the symbols which are used to solve the different algorithms and the notations are

Big Oh Notation (O)

Little Oh Notation (o)

Omega Notation (Ω)

Theta Notation (θ)

Big Oh (O) Notation

This Notation gives the upper bound for a function to within a constant factor. We write f(n) = O(g(n)) if there are +ve constants n0 and C such that to the right of n0, the value of f(n) always lies on or below Cg(n)

Omega Notation (Ω)

This notation gives a lower bound for a function to with in a constant factor. We write f(n) = Ωg(n) if there are positive constants n0 and C such that to the right of n0 the value of f(n) always lies on or above Cg(n)

Theta Notation (θ)

This notation bounds the function to within constant factors. We say f(n) = θg(n) if there exists +ve constants n0, C1 and C2 such that to the right of n0 the value of f(n) always lies between c1g(n) and c2(g(n)) inclusive.

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Похожие книги на «Data Structure and Algorithms Using C++»

Представляем Вашему вниманию похожие книги на «Data Structure and Algorithms Using C++» списком для выбора. Мы отобрали схожую по названию и смыслу литературу в надежде предоставить читателям больше вариантов отыскать новые, интересные, ещё непрочитанные произведения.


Отзывы о книге «Data Structure and Algorithms Using C++»

Обсуждение, отзывы о книге «Data Structure and Algorithms Using C++» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.

x