Data Structures (18CS202) Lecture Notes

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What are the four basic properties/characteristics of an algorithm?

Input-Output, Finiteness, Definiteness, Effectiveness

Which category of algorithm involves decision making or option selection?

Sequence

Selection (correct)

Iteration

The Efficiency of an Algorithm can be measured by __________ metrics.

time complexity and space complexity

Define Asymptotic Notations.

Asymptotic analysis of an algorithm defines the mathematical framework of its run-time performance. Signup and view all the answers

Linear data structures organize their data elements in a non-sequential fashion.

False Signup and view all the answers

What principle does a stack follow?

LIFO (Last In, First Out) Signup and view all the answers

What is the operation used to add new elements to a stack?

Push Signup and view all the answers

What happens when a stack is full and a new element is attempted to be added?

Stack Overflow Signup and view all the answers

What is the operation used to remove elements from a stack?

Pop Signup and view all the answers

What happens when a stack is empty and an element is tried to be removed?

Stack Underflow Signup and view all the answers

What principle does a queue follow?

FIFO (First In, First Out) Signup and view all the answers

What is the purpose of the 'insertion' function in the queue program provided?

To insert an element into the queue Signup and view all the answers

What does the 'deletion' function do in the queue program?

Removes an element from the queue Signup and view all the answers

Explain the purpose of the 'display' function in the queue program.

To show the elements in the queue Signup and view all the answers

What is the output of the postfix expression for the given infix expression? ((a + b ((b ^ c – d))) * (e – (a / c)))

abbc^d-+eac/-* Signup and view all the answers

What are the three types of searching algorithms mentioned in the content?

Linear search, Binary search, Fibonacci search Signup and view all the answers

In the provided program, which option would the user choose to perform an insertion operation?

1.insertion Signup and view all the answers

In the output provided, the inorder traversal of the tree is: 2, 6, 7, 9, 15, 18, ___.

21 Signup and view all the answers

The main function of the BST program starts with a function named 'bst'.

True Signup and view all the answers

Match the traversal types with their corresponding order:

In Order Traversal = 2 6 7 9 15 18 21 Pre Order Traversal = 15 7 6 2 9 18 21 Post Order Traversal = 2 6 9 7 21 18 15 Signup and view all the answers

What is a queue in the context of data structures?

An object or abstract data structure that allows operations like Enqueue and Dequeue Signup and view all the answers

What are the primary operations on a queue?

Enqueue or insertion Signup and view all the answers

In a queue, the element is inserted at the _ of the queue.

end Signup and view all the answers

A queue is a linear data structure that follows the LIFO principle.

False Signup and view all the answers

Match the queue operation with its description:

Enqueue = Inserts an element at the end of the queue Dequeue = Deletes an element at the start of the queue Signup and view all the answers

Study Notes

Data Structures and Algorithms

Data Structures course objectives:
- Demonstrate familiarity with major algorithms and data structures
- Choose the appropriate data structure and algorithm design method for a specified application
- Determine which algorithm or data structure to use in different scenarios
- Improve logical ability

Algorithms

An algorithm is a step-by-step process to solve a problem
Properties of an algorithm:
- Input-Output: Algorithm takes input and produces output
- Finiteness: An algorithm must terminate in a countable number of steps
- Definiteness: Each step of an algorithm must be stated clearly and unambiguously
- Effectiveness: Each step in an algorithm can be converted into a programming language statement
- Generality: Algorithm is generalized and works on all set of inputs
Categories of algorithms:
- Sequence: Steps are performed successively one by one
- Selection: Involves decision-making and conditional branching
- Iteration: Used for solving problems that involve repetition of statements

Performance Analysis of Algorithms

Time Complexity: The amount of time required for an algorithm to complete its execution
Space Complexity: The amount of space occupied by an algorithm
Asymptotic Notations:
- Big Oh Notation (Ο): Measures the upper bound of an algorithm's running time
- Omega Notation (Ω): Measures the lower bound of an algorithm's running time
- Theta Notation (θ): Measures both the upper and lower bound of an algorithm's running time

Data Structures

Data Structure: An organized collection of data with allowed operations
Types of Data Structures:
- Linear Data Structures: Organize data elements in a linear fashion (e.g., arrays, linked lists, stacks, and queues)
- Non-Linear Data Structures: Organize data elements in a non-sequential fashion (e.g., multidimensional arrays, trees, graphs, tables, and sets)
Operations on Data Structures:
- Traversing
- Searching
- Inserting
- Deleting
- Sorting
- Merging

Stacks and Queues

Stack: A linear data structure that follows the LIFO (Last In, First Out) principle
Operations on Stacks:
- Push: Add a new element to the stack
- Pop: Remove an element from the stack
Representation of Stacks:
- Using arrays
- Using linked lists

Stack Operations

Push Operation:
- Add a new element to the stack
- Check if the stack is full before adding a new element
Pop Operation:
- Remove an element from the stack
- Check if the stack is empty before removing an element
Display Operation:
- Display the elements in the stack
- Check if the stack is empty before displaying the elements### Stack Operations
A stack is used to check for balancing of parentheses, brackets, and braces in compilers.
It is used to evaluate postfix expressions and convert infix expressions into postfix or prefix form.
In recursion, all intermediate arguments and return values are stored on the processor's stack.
During a function call, the return address and arguments are pushed onto a stack and popped off when the function returns.

Algebraic Expressions

An algebraic expression is a legal combination of operators and operands.
Operands are quantities on which mathematical operations are performed, and can be variables or constants.
Operators are symbols that signify mathematical or logical operations between operands.
There are three types of algebraic expressions: infix, postfix, and prefix.

Infix, Postfix, and Prefix Notations

Infix notation places the arithmetic operator between two operands (e.g. A + B).
Prefix notation places the arithmetic operator before its two operands (e.g. + A B).
Postfix notation places the arithmetic operator after its two operands (e.g. A B +).

Conversion from Infix to Postfix

Scan the infix expression from left to right.
If the scanned symbol is a left parenthesis, push it onto the stack.
If the scanned symbol is an operand, place it directly in the postfix expression.
If the scanned symbol is a right parenthesis, pop all items from the stack and place them in the postfix expression until the matching left parenthesis is found.
If the scanned symbol is an operator, remove all operators from the stack and place them in the postfix expression if their precedence is greater than or equal to the precedence of the scanned operator.

Evaluation of Postfix Expressions

Use a stack to evaluate the postfix expression.
When a number is seen, push it onto the stack.
When an operator is seen, apply it to the two numbers popped from the stack and push the result onto the stack.
There is no need to know precedence rules when evaluating postfix expressions.

Queues

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle.
Items are inserted at the rear and deleted from the front of the queue.
Queue operations are analogous to those of a stack, but with insertions at the end and deletions at the beginning.
Queue operations include enqueue (insertion), dequeue (deletion), and display.

Representation of Queues

Queues can be represented using arrays or linked lists.
Array representation uses a fixed-size array to store queue elements.
Linked list representation uses a dynamic list of nodes, each pointing to the next node.

Linear Lists

A linear list is a collection of elements that can be stored in a specific order.
Operations on linear lists include create, destroy, determine whether the list is empty, determine the size of the list, find an element with a given index, and insert or delete an element at a given index.

Array Representation of Linear Lists

Array representation uses a mathematical formula to map list elements to array positions.
The formula is Location(i) = i-1, which means the ith element of the list is in position i-1 of the array.
The length of the list is stored separately and is used to keep track of the current size of the list.

Insertion and Deletion of Linear Lists

To remove an element from the list, move all elements to the right of it down by one position.
To insert an element, move all elements to the right of it up by one position and then insert the new element.

Linked Representation of Linear Lists

Linked representation uses a separate node for each element of the list.
Each node has a link field that points to the next node in the list.
The link field is used to locate the next element in the list.### Queue Using Arrays
A program is written to implement a queue using arrays.
The program includes functions for insertion, deletion, and display.
The user is prompted to enter the size of the queue and then perform operations on the queue.
The program uses a switch statement to handle different cases for insertion, deletion, and display.

Types of Queues

There are two types of queues: priority queue and circular queue.
A program is written to implement a priority queue using a linked list.
The program includes functions for insertion, deletion, and display.
The priority queue is implemented using a linked list, where each node has a priority and info field.

Stack Implementation

A program is written to implement a stack using an array.
The program includes functions for push and pop operations.
The program uses a switch statement to handle different cases for push and pop operations.

Infix to Postfix Conversion

A program is written to convert an infix expression to a postfix expression.
The program uses a stack to convert the infix expression to postfix.
The program includes functions for push and pop operations.

Circular Queue

A program is written to implement a circular queue using an array.
The program includes functions for insertion, deletion, and display.
The program uses a circular array to implement the queue.

Doubly Linked List

A program is written to implement a doubly linked list.
The program includes functions for insertion, deletion, and display.
The program uses a doubly linked list, where each node has a prev and nxt field.

Searching Algorithms

There are three types of searching algorithms: linear search, binary search, and Fibonacci search.
A program is written to implement linear search and binary search.
The program includes functions for searching and displaying the result.

Tree Traversal

A program is written to implement tree traversal using a binary tree.
The program includes functions for insertion, inorder, preorder, and postorder traversal.
The program uses a binary tree, where each node has a left and right child.

Balancing a Tree

A program is written to balance a tree using a binary search tree.
The program includes functions for creating a binary search tree and displaying the preorder traversal.
The program uses a binary search tree, where each node has a value and left and right child.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Lecture notes on Data Structures (18CS202) covering objectives, algorithms, and data structure design methods for various applications.