Overig

data structures and algorithms

0 keer verkocht

Instelling
DSA

Unit I Introduction: Dynamic aspects of operations on data, Characteristics of data structures, Creation and manipulation of data structures, Operations on data structures, Types of data structures – linear and nonlinear. Introduction to algorithm: Asymptotic notations, Analysis of algorithms:...

[Meer zien]

Voorbeeld 4 van de 132 pagina's

Bekijk voorbeeld

Geupload op 27 april 2023
Aantal pagina's 132
Geschreven in 2022/2023
Type Overig
Persoon Onbekend

digital regulation

€8,92

In winkelwagen

Op verlanglijstje

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

LECTURE NOTES
ON
DATA STRUCTURES

Year : 2017 - 2018
Course Code : ACS102
Regulations : R16
Semester : I B.Tech II Semester
Branch : CSE / IT / ECE / EEE

Prepared by
Ms. B Padmaja
Associate Professor

INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
Dundigal, Hyderabad - 500 043

, DATA STRUCTURES
II Semester: CSE / ECE / EEE / IT
Course Code Category Hours / Week Credits Maximum Marks
L T P C CIA SEE Total
ACS002 Foundation
3 1 - 4 30 70 100
Contact Classes: 45 Tutorial Classes: 15 Practical Classes: Nil Total Classes: 60

COURSE OBJECTIVES:
The course should enable the students to:
I. Learn the basic techniques of algorithm analysis.
II. Demonstrate several searching and sorting algorithms.
III. Implement linear and non-linear data structures.
IV. Demonstrate various tree and graph traversal algorithms.
V. Analyze and choose appropriate data structure to solve problems in real world.

UNIT - 1 INTRODUCTION TO DATA STRUCTURES, SEARCHING AND SORTING
Basic concepts: Introduction to data structures, classification of data structures, operations on
data structures, abstract data type, algorithms, different approaches to design an
algorithm, recursive algorithms; Searching techniques: Linear search, binary search and Fibonacci
search; Sorting techniques: Bubble sort, selection sort, insertion sort, quick sort, merge sort, and
comparison of sorting algorithms.
UNIT - 2 LINEAR DATA STRUCTURES
Stacks: Primitive operations, implementation of stacks using Arrays, applications of stacks
arithmetic expression conversion and evaluation; Queues: Primitive operations; Implementation
of queues using Array, applications of linear queue, circular queue and double ended queue
(DEQUE).
UNIT - 3 LINKED LISTS
Linked lists: Introduction, singly linked list, representation of a linked list in memory, operations on a
Single linked list; Applications of linked lists: Polynomial representation and sparse matrix
manipulation.
Types of linked lists: Circular linked lists, doubly linked lists; Linked list representation and
operations of Stack, linked list representation and operations of queue.
UNIT - 4 NON LINEAR DATA STRUCTURES
Trees : Basic concept, binary tree, binary tree representation, array and linked representations, binary
tree traversal, binary search tree, tree variants, application of trees; Graphs: Basic concept, graph
terminology, graph implementation, graph traversals, Application of graphs, Priority Queue.
UNIT - 5 BINARY TREES AND HASHING
Binary search trees: Binary search trees, properties and operations; Balanced search trees:
AVL trees; Introduction to M - Way search trees, B trees; Hashing and collision: Introduction,
hash tables, hash functions, collisions, applications of hashing.
LIST OF REFERENCE BOOKS:
1. Y Daniel Liang, “Introduction to Programming using Python”, Pearson.
2. Benjamin Baka, David Julian, “Python Data Structures and Algorithms”, Packt Publishers,2017.
3. Rance D. Necaise, “Data Structures and Algorithms using Python”, Wiley Student Edition.

,4. Martin Jones, “Python for Complete Beginners”, 2015.
5. Zed A. Shaw, “Learn Python the Hard Way: a very simple introduction to the terrifyingly
beautiful world of computers and code”, 3e, Addison-Wesley, 2014.
6. Hemant Jain, “Problem Solving in Data Structures and Algorithms using Python: programming
interview guide”, 2016.
WEB REFERENCES:
1. https://docs.python.org/3/tutorial/datastructures.html
2. http://interactivepython.org/runestone/static/pythonds/index.html
3. http://www.tutorialspoint.com/data_structures_algorithms
4. http://www.geeksforgeeks.org/data-structures/
5. http://www.studytonight.com/data-structures/
6. http://www.coursera.org/specializations/data-structures-algorithms

, UNIT – I INTRODUCTION TO DATA STRUCTURES,
SEARCHING AND SORTING
Basic Concepts: Introduction to Data Structures:

A data structure is a way of storing data in a computer so that it can be used efficiently and it will allow
the most efficient algorithm to be used. The choice of the data structure begins from the choice of an
abstract data type (ADT). A well-designed data structure allows a variety of critical operations to be
performed, using as few resources, both execution time and memory space, as possible. Data structure
introduction refers to a scheme for organizing data, or in other words it is an arrangement of data in
computer's memory in such a way that it could make the data quickly available to the processor for
required calculations.

A data structure should be seen as a logical concept that must address two fundamental concerns.

1. First, how the data will be stored, and
2. Second, what operations will be performed on it.
As data structure is a scheme for data organization so the functional definition of a data structure should
be independent of its implementation. The functional definition of a data structure is known as ADT
(Abstract Data Type) which is independent of implementation. The way in which the data is organized
affects the performance of a program for different tasks. Computer programmers decide which data
structures to use based on the nature of the data and the processes that need to be performed on that
data. Some of the more commonly used data structures include lists, arrays, stacks, queues, heaps, trees,
and graphs.

Classification of Data Structures:

Data structures can be classified as

 Simple data structure
 Compound data structure
 Linear data structure
 Non linear data structure

[Fig 1.1 Classification of Data Structures]

Simple Data Structure:
Simple data structure can be constructed with the help of primitive data structure. A primitive data
1

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.

Direct to-the-point

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper sachinsoni1. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €8,92. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 68175 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Begin nu gratis