Education4U

Data Structures (DS)

Lec-01 : Introduction

Description

In this tutorial, students will learn about the entire world of Data Structures & Algorithms, about how the data can be stored and managed, with the Least Time Complexity and also Space Complexity.

Prerequisite

We don't expect you to have any prior knowledge on Data Structure or Algorithm, but a basic or fundamental prior knowledge of any Programming Language will help you

Topics Covered

• Methodologies • Arrays • Stacks & Queues • Infix, prefix and Postfix notations

• Linked list & Sparse matrix • Binary tree • BST • AVL tree

• Graphs • Sorting • Hashing

For whom

• This tutorial is designed for Computer Science graduates as well as Software Professionals who are willing to learn data structures and algorithm programming in simple and easy steps.

• This tutorial for students who want to learn the data structure and its Algorithms from the basic level to the Intermediate level.

Reference books

1. Data Structures and Algorithms Made Easy

2. Introduction to Algorithms by Thomas H. Cormen

3. Algorithms by Robert Sedgewick & Kevin Wayne

4. The Algorithm Design Manual by Steve S. Skiena

Q & A
Exam Questions

Q1 . With help of a suitable example, explain the working of Selection Sort.
Q2 . Comment on the complexity of Merge Sort and Insertion Sort.
Q3 . Explain the technique to access array elements using a pointer.
Q4 . Explain PUSH and POP Operation on Stack in derail.
Q5 . What is Hashing? Explain Chaining Operations.
Q6 . Write a short note on the Priority Queue.
Q7 . Explain the algorithm for inserting a new node at the end of the doubly linked list.
Q8 . write an algorithm for deleting a node from the end of the circular linked list.
Q9 . Write Depth First Traversal Algorithm for Graph. Explain the algorithm with a suitable example.
Q10 . Explain different scenarios for inserting a new node in the AVL Tree.

We are using two data structures to implement an LRU Cache. 1. The queue is implemented using a doubly-linked list. The maximum size of the queue will be similar to the total number of frames provided (cache size). The more recently used pages will be near the rear end and the least recently used pages will be near the front end. 2. A Hash within the page number is a key and address of the corresponding queue node as a value.

A linked list is a sequence of nodes in which each node is connecting to the next node following it. This creates a chain-like link for data storage.

• Linear: A data structure is saying to be linear if its elements create a sequence or a linear list. Examples: Array. Linked List, Stacks and Queues • Non-Linear: A data structure is saying to be non-linear only if the traversal of nodes is nonlinear. Example: Graph and Trees.

• The RDBMS uses an Array data structure • The network data model uses Graph • The hierarchal data model uses Trees

Data structure applications are: • Compiler Design • Operating System • Database Management System • Statistical analysis package • Numerical Analysis • Graphics • Artificial Intelligence • Simulation

• Expression evaluation • Backtracking • Memory Management • Function calling and return

• Push Operations • Pop Operations • Peek Operations

An array is the collection of similar types of data items stored at contiguous memory locations. Every data element can be randomly accessed by using its index number in the simplest data structure.

A queue is an ordered list that performs insert operations at one end called REAR and the delete operations to be performing at another end called FRONT.

There are six types of trees. • General Tree • Forests • Binary Tree • Binary Search Tree • Expression Tree • Tournament Tree

LIFO stands for Last In First Out means how data is accessed, stored, and retrieved. The LIFO contains the last items entered are the first to be removed.

A binary tree is a data structure it has two nodes, a left node, and a right node. In programming, a binary tree is an extension of the linked list structures.

Applications of Tree- data structure: • The manipulation of Arithmetic expression, • Symbol Table construction, • Syntax analysis • Hierarchal data model

For graph implementation, the following data structures are used. • In sequential representation, the Adjacency matrix is used. • In Linked representation, an Adjacency list is used.

In the BFS algorithm, the Queue data structure is used. In the DFS algorithm, the Stack data structure is used.

• It is simple and easy to implement. • It is used for small data sets. • It is 60 percent more efficient than the bubble sort is.

• Path: A Path is the sequence of adjacent vertices joined by the edges with no restrictions. • Cycle: A Cycle is a closed path where the initial vertex is identical to the end vertex. Any vertex in the path cannot be visited twice • Circuit: A Circuit is a closed path where the initial vertex is identical to the end vertex. Any vertex may be repeated.

Null Void Null is a value A void is a data type identifier

1. Sparse matrix, 2. Index generation.

2k+1-1 where k >= 1

Polish and Reverse Polish notations

AB+CD-*

Queue data structure

Two queues are required. The first queue is used to store the data elements, and the second queue is used for storing priorities.

Dequeue (also known as a double-ended queue) is defined as an ordered set of elements in which the insertion and deletion can be performed at both ends, that is the front end and the rear end.

No Reviews. Be the First Student to Review the course...

Review :

0 | 0 Reviews

Course Feature

Category Computer Science
Course Duration 9 Hrs
Language English
Price 49.00
Validity 1 Year
Q & A 25
Exam Questions 10
Full Course PDF View

Wishlist

Add to Cart

Computer Science

Data Structures (DS)

Lec-01 : Introduction

Course Feature

Share

Data Communication

Distributed Systems

Adhoc & Sensor

Operating Systems(OS)

Useful Links

Download

Computer Science

1.Methodologies

2.Arrays

3.Stacks & Queues

4.Infix, Prefix & Postfix

5.Linked list & Sparse Matrix

6.Binary Tree

7.BST : Binary Search Tree

8.AVL tree

9.Graphs

10.Sorting

11.Hashing

Data Structures (DS)

Lec-01 : Introduction

1.Methodologies

2.Arrays

3.Stacks & Queues

4.Infix, Prefix & Postfix

5.Linked list & Sparse Matrix

6.Binary Tree

7.BST : Binary Search Tree

8.AVL tree

9.Graphs

10.Sorting

11.Hashing

Q1 . Which Data Structure Should be used for implementing LRU cache?

Q2 . What is a linked list?

Q3 . What are linear and non-linear data Structures?

Q4 . List the data structures which are used in RDBMS, Network Data Modal, and Hierarchical Data Model.

Q5 . List the area of applications of Data Structure

Q6 . List the area of applications where a stack data structure can be used?

Q7 . What are the operations that are performed on a stack?

Q8 . What is an array?

Q9 . Define the queue data structure.

Q10 . List the types of trees.

Q11 . What is LIFO?

Q12 . What are binary trees?

Q13 . List some applications of Tree-data structure?

Q14 . Mention the data structures which are used in graph implementation

Q15 . Which data structures are used in BFS and DFS algorithm?

Q16 . What are the advantages of Selection Sort?

Q17 . Differentiate among cycle, path, and circuit?

Q18 . What is the difference between NULL and VOID?

Q19 . List Some Applications of Multi linked Structures?

Q20 . What is the maximum number of nodes in a binary tree of height k?

Q21 . Which notations are used in the Evaluation of Arithmetic Expressions using prefix and postfix forms?

Q22 . Write the postfix form of the expression: (A + B) * (C - D)

Q23 . Which data structure suits the most in the tree construction?

Q24 . What is the minimum number of queues that can be used to implement a priority queue?

Q25 . What is a Dequeue?

Course Feature

Share

Related Courses

Data Communication

Distributed Systems

Adhoc & Sensor

Operating Systems(OS)

Useful Links

Download