Data Structures
Data can be organized in many ways and data structures is one of these ways. It is used to represent data in the memory of the computer so that the processing of data can be done in easier way. Data structures is the logical and mathematical model of a particular organization of data. The data can be organised in linear or non-linear representation. The utilization of data using the various searching and sorting techniques. The real world examples for stacks, queues, link list and trees and its applications.
Notes
- Chpt.1: Introduction to Data Structure
- Chpt.2: Sorting and Searching
- Chpt.3: Stacks
- Chpt.4: Queues
- Chpt.5: Link List
- Chpt.6: Trees
- Chpt.7: Graph and Hashing
Video Lectures
INTRODUCTION TO DATA STRUCTURES
Data can be organized in many ways and data structures is one of these ways. It is used to represent data in the memory of the computer so that the processing of data can be done in easier way Linear Data structures: In these data structures the elements form a sequence. Such as Arrays, Linked Lists, Stacks and Queues are linear data structures.
Non-Linear Data Structures: In these data structures the elements do not form a sequence. Such as Trees and Graphs are non-linear data structures.
Growth of a Function – Asymptotic Notation
What is the goal of analysis of algorithms?To compare algorithms mainly in terms of running time but also in terms of other factors ,e.g., memory requirements, programmer’s effort etc. What do we mean by running time analysis?
Determine how running time increases as the size of the problem increases.
Time and Space Complexity
To calculate the allocation of static and Dynamic memory for the execution of pseudocode. Performance analysis calculates the time and space complexity of any given pseudocode.
Selection Sort
The simplest sorting algorithm, which works by assigning the first element to the variable min, as the minimum element in the array. Then compares the remaining elements with the min element. After the pass one places the first element at its location.
Bubble Sort
Bubble sort algorithms cycle through a list, analyzing pairs of elements from left to right, or beginning to end.If the leftmost element in the pair is less than the rightmost element, the pair will remain in that order. If the rightmost element is less than the leftmost element, then the two elements will be switched. This cycle repeats from beginning to end until a pass in which no switch occurs.
Insertion Sort
It always maintains two zones in the array to be sorted: sorted and unsorted.
At the beginning the sorted zone consist of one element (the first element of array that we are sorting).On each step the algorithms expand the sorted zone by one element inserting the first element from the unsorted zone in the proper place in the sorted zone and shifting all larger elements one slot down.
Divide and Conquer
Divide-and-conquer is a top-down technique for designing algorithms.
The algorithms that consists of dividing the problem into smaller sub problems hoping that the solutions of the sub problems are easier to find and then composing the partial solutions into the solution of the original problem.
Merge Sort
Splits array A[0..n-1] into about equal halves and make copies of each half in arrays B and C.Sort arrays B and C recursively and then Merges the sorted arrays B and C into array A.
Quick Sort
The quick sort uses divide and conquer while not using additional storage.A quick sort first selects a value, which is called the pivot value.The role of the pivot value is to assist with splitting the list.The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.
Radix Sort
The array divided in to 10 buckets from 0 to 9. The numbers are sorted on the LSB (Least Significant Bit) of any number for the first pass.The time complexity of radix sort is Ω(nLogn).
Linear Search
This is the simplest searching technique available. To search whether an element is present or absent in the array, we compare it with each and every other element in the array. If the element is found after comparison than it is printed as element found, else element not found or absent in the array.
Binary Search
This is the simplest searching technique available.
To search whether an element is present or absent in the array, we compare it with each and every other element in the array. If the element is found after comparison than it is printed as element found, else element not found or absent in the array.
Stack
An abstract data type (ADT) consists of a data structure and a set of primitive operations. A stack is structured, as an ordered collection of items where items are added to and removed from the end called the “top”. Stacks are ordered LIFO.
Polish Notation using Stack
Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions known as Polish notation.It is easiest to demonstrate the differences by looking at examples of operators that take two operands.
Evaluating Postfix Expression using Stack
The stack operations are given below in the form of function are –
Stack () creates a new stack that is empty. It needs no parameters and returns an empty stack.
Push (item) adds a new item to the top of the stack. It needs the item and returns nothing.
Pop () removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
Queue
A queue is a list from which items are deleted from one end (front) and into which items are inserted at the other end (rear, or back). It is like line of people waiting to purchase tickets. Queue is referred to as a first-in-first-out (FIFO) data structure. The first item inserted into a queue is the first item to leave.
Circular Queue using Array
Queue using Array: Circular queue is a linear data structure. In circular queue the last node is connected back to the first node to make a circle. Circular linked list follow the First In First Out principle. Elements are added at the rear end and the elements are deleted at front end of the queue. Both the front and the rear pointers points to the beginning of the array. It is also called as “Ring buffer”. Items can inserted and deleted from a queue in O(1) time.
Singly Link List
Linked lists stores data with structures, create a new place to store data.It is written using a struct definition that contains variables holding information about something and that has a pointer to a struct of its same type.Each of these individual struct in the list is commonly known as a node or element of the list.
Insertion Sort
Insert and Delete elements from the middle of a Singly Link List
Insert & Delete Element from a Location
Doubly Link List