[go: up one dir, main page]
Scribd
Upload
33 views3 pages

INTRODUCTION

dsa INTRODUCTION SIMPLE NOTES

Uploaded by

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

INTRODUCTION

dsa INTRODUCTION SIMPLE NOTES

Uploaded by

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

COURSE OBJECTIVE:

1. Understand the basic concept of algorithms.


2. To introduce the various data structures and their implementations.
3. Evaluate the performance of various sorting algorithms.
SYLLABUS
UNIT- I
Introduction of Algorithms, Analyzing Algorithms, Arrays: Representation of Arrays,
Implementation of Stacks and Queues, Application of Stack: Evaluation of Expression - Infix to
Postfix Conversion - Multiple Stacks and Queues, Sparse Matrices.
UNIT – II
Linked List: Singly Linked list - Linked Stacks and Queues - Polynomial Addition - More on
Linked Lists - Doubly Linked List and Dynamic Storage Management - Garbage Collection and
Compaction.
UNIT – III
Trees: Basic Terminology - Binary Trees - Binary Tree Representations - Binary Trees -
Traversal - More on Binary Trees - Threaded Binary Trees - Counting Binary Trees. Graphs:
Terminology and Representations - Traversals, Connected Components and Spanning Trees,
Single Source Shortest Path Problem.
UNIT – IV
Symbol Tables: Static Tree Tables - Dynamic Tree Tables - Hash Tables Hashing Functions -
Overflow Handling. External Sorting: Storage Devices - Sorting with Disks: K- way Merging -
Sorting with Tapes.
UNIT - V
Internal Sorting: Insertion Sort - Quick Sort - 2 way Merge Sort - Heap Sort - Shell Sort - Sorting
on Keys. Files: Files, Queries and Sequential Organizations - Index Techniques - File
Organization
Text Books
 “Fundamentals of Data Structures”, Ellis Horowitz, Sartaj Shani, Galgotia publication.
Reference Books
 “Data Structures Using C” Aaron M. Tenenbaum, Yedidyah Langsam, Moshe
J.Augenstein, Kindersley (India) Pvt. Ltd.,
 “Data Structure and Algorithms” Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman,
Pearson Education Pvt. Ltd.,
Website/Link
1. www.freetechbooks.com/a-practical-introduction-to-data-structures-and-algorithm-analysis-
thirdedition-c-version-t804.html
2. http://www.nptel.ac.in/courses/106101060/
3. http://www.nptel.ac.in/courses/106104019/

INTRODUCTION:
1. Data structures play a crucial role in computer science and programming, as they provide
efficient ways to organize and manipulate data. A solid understanding of data structures is
essential for designing efficient algorithms and building robust software systems. In this
introduction, we will explore the fundamentals of data structures and their importance in
computer science.
2. Data structures are essentially containers that hold and organize data in a particular
format. They determine how data is stored, accessed, and manipulated. The choice of
data structure can significantly impact the performance and efficiency of algorithms and
operations performed on the data.
3. There are numerous types of data structures, each designed for specific purposes and
scenarios. Some common data structures include arrays, linked lists, stacks, queues, trees,
graphs, and hash tables. Each of these data structures has unique characteristics and
advantages, making them suitable for various applications.
4. One of the fundamental aspects of data structures is their efficiency in terms of time and
space complexity. Time complexity refers to the amount of time required to perform
operations on the data structure, while space complexity refers to the amount of memory
it requires. Different data structures excel in different scenarios, and choosing the right one
depends on the specific requirements and constraints of a problem.
5. Another important concept in data structures is the concept of operations. Data structures
define a set of operations that can be performed on the stored data, such as insertion,
deletion, search, and traversal. The efficiency of these operations can vary depending on
the chosen data structure.
WHAT IS AN ALGORITHM?
In computer programming terms, an algorithm is a set of well-defined instructions to solve a
particular problem. It takes a set of input(s) and produces the desired output. For example,
An algorithm to add two numbers:
1. Take two number inputs
2. Add numbers using the + operator
3. Display the result
QUALITIES OF A GOOD ALGORITHM
 Input and output should be defined precisely.
 Each step in the algorithm should be clear and unambiguous.
 Algorithms should be most effective among many different ways to solve a problem.
 An algorithm shouldn't include computer code. Instead, the algorithm should be written
in such a way that it can be used in different programming languages.
Algorithm 1: Add two numbers entered by the user
Step 1: Start
Step 2: Declare variables num1, num2 and sum.
Step 3: Read values num1 and num2.
Step 4: Add num1 and num2 and assign the result to sum.
sum←num1+num2
Step 5: Display sum
Step 6: Stop
What are Data Structures?
 Data structure is a storage that is used to store and organize data. It is a way of arranging data
on a computer so that it can be accessed and updated efficiently.
 Depending on your requirement and project, it is important to choose the right data structure
for your project. For example, if you want to store data sequentially in the memory, then you
can go for the Array data structure.

Types of Data Structures


 There are two types of data structures:
1) Primitive Data Structure
2) Non-Primitive Data Structure
 Primitive Data Structure
 The primitive data structures are primitive data types.
 The int, char, float, double, and pointer are the primitive data structures that can hold
a single value.
 Non Primitive Data Structure
Basically, data structures are divided into two categories:
 Linear data structure
 Non-linear data structure
Linear data structures
 In linear data structures, the elements are arranged in sequence one after the other. Since
elements are arranged in particular order, they are easy to implement.
 However, when the complexity of the program increases, the linear data structures might
not be the best choice because of operational complexities.

 Popular linear data structures are:


 Array Data Structure.
 Stack Data Structure.
 Queue Data Structure.
 Linked List Data Structure.
1. Array Data Structure
In an array, elements in memory are arranged in
continuous memory. All the elements of an array are of the
same type. And, the type of elements that can be stored in
the form of arrays is determined by the programming
language.
2. Stack Data Structure
In stack data structure, elements are stored in the LIFO principle. That is, the last
element stored in a stack will be removed first.
It works just like a pile of plates where the last plate kept on the pile will be removed first.

You might also like