DSA-Notes.pdf

Data Structures And Algorithm Java Programming Basics Review What is Java - Is a popular high level, class-based object-oriented programming language that is designed to be platform independent - originally developed by S...

Data Structures And Algorithm Java Programming Basics Review What is Java - Is a popular high level, class-based object-oriented programming language that is designed to be platform independent - originally developed by Sun Microsystems and is released in 1995. - currently owned by Oracle and more than three billion devices run by Java. - some aspects of Java are Platform independence, object-oriented, syntax, automatic memory management, multithreading, rich standard library, and security.  Platform Independence – java code is compiled into bytecode which executed on any platform with a compatible Java Virtual Machine (JVM) | “write once, run everywhere.  Object-Oriented – built around the principle of OOP which uses objects and classes to organize code.  Syntax – is similar to C++, which makes it easier for developers to learn and has more simplified aspects of C++ to avoid common errors.  Automatic Memory Management – includes a garbage collector that automatically manages memory allocation and deallocation, which helps to prevent memory leaks.  Multithreading – allows developers to write program that can perform multiple tasks simultaneously, which can improve performance and responsiveness.  Rich Standard Library – comes with comprehensive set of standard libraries that provide functionality for data structures, networking, file handling and more.  Security – has built-in security features like Java sandbox and bytecode verification that helps to protect against malicious code.  // - inline comment, limited to one line.  - multiline comments, in the form of block comments. Data Types - are classifications that specify which type of value a variable can hold. - each data types determines what kind of operations can be performed on the data, how much memory is allocated, and how the data is represented. - are divided into two groups (Primitive data types and Non-primitive data types).  Primitive data types – these are basic types provided by a programming languages which usually represent single values and have a fixed size. -It includes the Boolean, character, byte, short, integer, long, float and double.  Non-primitive data types – also known as reference types which are more complex and represent collections of values or more structures. -it includes the arrays, string, classes, objects, lists, queues, stacks, graph, trees and more.  What is Object and classes in Java?  Class – blueprint or template for creating objects, it is a set of objects which shares common characteristics or behavior and common properties or attributes.  Objects – is an instance of a class , which serves as the type of the object and as blueprint, defining the data which the object stores and the methods for accessing and modifying that data.  Instance variables – which are also called fields, represents the data associated with an object of a class. It is usually have a type (base type like int, float, double and more) (reference type which are the data structures topic)  Methods – are blocks of code that can be called to perform actions and can accept parameters as arguments and their behavior may depend on the object upon which they are invoked and the values of any parameter that are passed.  Modifiers– can be placed to convey additional stipulations and are the keywords that you use to define the characteristic of classes, methods, variables and other elements in your code. Types includes access modifiers, static modifiers, abstract modifiers and final modifiers.  Access modifiers – they control the level of access and also known as visibility that the defining class grants to other classes in the context of a larger program. Public (accessible from any other class) Protected (accessible within the same package and by subclasses) default (no modifier which is accessible only within the same package.  Static modifier– can be declared for any variable or method of a class and indicates that a member belongs to the class rather than to any instance of the class.  Abstract modifier – are and advanced feature of objectoriented programming to be combined with inheritance. Uses to declare abstract classes and methods.  Final modifier – can be initialized as part of that declaration, but can never again be assigned a new value. Used to declare constants, prevent method overriding, and inheritance of classes. Java Operators  Arithmetic Operator – used to perform common mathematical operations like Addition (+), Subtraction(-), Multiplication(*), Division(/), Modulus(%), Increment(++) and Decrement(--).  Relational Operator - a symbol used in computer programming to compare two values and determine if a specific relationship between them is true or false like equal to(==), not equal to(!=), greater than(>), less than(=), and less than or equal to(>>).  Logical Operator – a symbol or word used to connect/combine two or more Boolean expression like Logical AND (&&), Logical OR(||), and Logical NOT (!).  Assignment Operator – store a value in the object specified by the left operand or used to assign values to variables like assignment (=), addition assignment (+=), subtraction assignment (-=), multiplication assignment (*=), division assignment (/=) and modulus assignment (%=).  Miscellaneous Operator – are unique kinds of operators like ternary, member access, comma, array index, new, instanceof, and typecast. Control flow - is the order function calls, instructions, and statement are executed or evaluated when a program is running.  IF STATEMENTS (conditional statement) - to specify a block of Java code to be executed if a condition is true.  IF ELSE STATEMENT (conditional statement) - executes one block of code if a condition is true, and another block if the condition is false.  ELSE IF STATEMENT (conditional statement) - specify a new condition if the first condition is false.  SWITCH STATEMENT (conditional statement) - allows you to choose from multiple options based on the value of an expression.   FOR LOOP (Looping statement) - repeats a block of code a specified number of times.  WHILE LOOP (looping statement) - repeats block of code as long as a specified condition is true.  DO-WHILE LOOP (looping statement) - repeats a block of code at least once and continues to repeat it as long as a specified condition is true.  BREAK STATEMENT (jump statement) - exits the current loop.  CONTINUE STATEMENT (jump statement) - skips the current iteration of a loop and proceeds with the next iteration.  RETURN STATEMENT (jump statement)- exits from the current method and optionally returns a value. DATA STRUCTURE - a programmatic way of organizing and storing data so that it can be used, accessed and modified efficiently - a way of collecting and organizing data in such a way that we can perform operations on these data in an effective way. - are essential ingredients in creating fast and powerful algorithms and gives us the possibility to manage large amounts of data efficiently for uses such as large databases and more. Categories of Data Structures 1. Linear Data Structures - it is where elements are organized to form any specific order or in a linear sequence, which means each element has a unique predecessor and successor. - common types are the arrays, linked list, stacks and queues. 2. Non-Linear Data Structures - it represents data which are not arranged in a sequential order but in a hierarchical relationships between different elements. - common types are the family of trees, graphs, map and more. Characteristics of a Data Structure  Correctness – data structure implementation should implement its interface correctly.  Time Complexity – running time or the execution time of operations of data structure must be a small as possible.  Space Complexity – memory usage of a data structure operation should be as little as possible. Why to learn DSA? - as applications are getting complex and data rich, there are three common problems that applications face now-a-days  Data Search – as data grows, search will become slower.  Processor speed – still falls limited if the data grows to billion records.  Multiple request – even the fast server still fails while thousand of request or data operations done at the same time. ALGORITHM - is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Qualities of a good Algorithm  Input – has an instance of the problem to be solved.  Output – produces results to solve the given instance of the problem.  Definiteness – each step is unambiguous or must be precisely defined.  Finiteness – terminates after producing the output in a finite amount of time.  Effectiveness – must consistently and accurately produce a meaningful and correct result for all possible valid inputs within a finite amount of time. Applications of Data structures and Algorithms  Search – algorithm to search an item in a data structure   Sort – algorithm to sort items in a certain order.  Insert – algorithm to insert item in a data structure.  Update – algorithm to update an existing item in a data structure.  Delete – algorithm to delete an existing item from a data structure. DATA STRUCTURES AND ALGORITHM - is about finding efficient ways to store and retrieve data, to perform operations on data and to solve specific problems. Types of Data Structure includes array, String, Linked List, Stack, Queue, Heap, Hash, Matrix/Grid, Graph and Tree. Types of Algorithms includes Searching, Sorting, Approximation, Divide and Conquer, Greedy, Recursion, Backtracking, Randomized, Dynamic programming, Pattern searching, Mathematical, Geometric, Bitwise, and Branch and Bound algorithm. Foundation terms of a Data Structure  Interface – represents the set of operations that a data structures supports or can be performed on it. It specifies what operations are available, but not how they are implemented. Sometimes also called an abstract data type.  Implementation – provides the internal representation and providing the definition of the algorithm used in the operations of the data structures. It refers to the actual code that performs the operations defined by the interface. Execution Time Cases  WORST CASE – the algorithm performs the maximum number of operations and provides an upper bound on the time complexity.  AVERAGE CASE – the algorithm performance is averaged over all possible inputs of a given size.  BEST CASE – the algorithm performs the minimum number of operations and represents the best possible option. Asymptotic notations - used to represent the complexity of an algorithm. Common types are Big Oh notation, Big omega notation, Big theta notation, Little Oh notation and Little omega notation. 1. Big Oh Notation - describes an upper bound on the time complexity of an algorithm and most commonly used notation. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete. - Common types includes Constant time O(1), Logarithmic time O(log n), Linear time O(n), and more.  (1) Constant time – the running time or space does not change with the size of the input and remains constant. It is a random access of an element in an array by accessing an element by index.  O(log n) Logarithmic time – the running time or space grows logarithmically with the input size and as the input size grows, the number of operations grows very slowly. Big Oh notation  O(n) Linear time – refers to an algorithm or operation whose execution time grows linearly with the size of input.  (n log n) Linearithmic time – the algorithm’s performance grows in proportion to n log n.  (n^2) Quadratic time – the performance is proportional to the square of the input size. 2. Big Omega Notation (Ω) – describes a lower bound on the time complexity of an algorithm. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete. 3. Big Theta Notation (Θ) – provides a tight bound on the time complexity of an algorithm. It is a formal way to express both the lower bound and the upper bound of an algorithm’s running time. 4. Little oh Notation (o) – describes a function that grows slower than a given function. Used to describe an upper bound that cannot be tight or not asymptotically tight. 5. Little Omega notation(ω) - describes a function that grows faster than a given function. Used to describe the asymptotic efficiency of algorithms. Array - is a data structure that holds a fixed-size sequence of elements of the same type. - is a type of linear data structure that is defined as a collection of elements with same or different data types and stores them in contiguous and adjacent memory locations. - each item in an array is indexed starting with 0 and each element in an array is accessed through its index.  Memory address – the starting address of free memory available.  Array index – key value to label the elements in the array.  Element / Array values – the items stored in an array. Types of Array  One-dimensional arrays - which is a one dimensional array as a row, where elements are stored in a single row or stored one after another.  Multidimensional arrays - which stores a multiple rows of elements and do have two types which includes twodimensional array and three-dimensional array.  Two-dimensional arrays – can be considered as an array of arrays or as a matrix consisting of rows and columns.  Three-dimensional arrays – contains three dimensions. Array Operations  Traversal - print all the array elements one by one.  INSERTION - Adds an element at the given index. We are adding one or more elements to the array. It can be done at the beginning, at the end or at any given index of an array.  DELETION – deletes an element at the given index. You can also do deletion in different ways at the beginning, at the end, and at any index.  SEARCHING – searches an element using the given index.  Linear search – sequential search algorithm that start at one end and goes through each element of a list until the desired element is found.  Binary search – is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half.  SORTING – the process which arrange elements in a user-defined order. It could be in ascending order descending order.  UPDATE – an element at the given index, LINKEDLIST  Linkedlist - is a linear data structure which is noncontiguous that forms a series of connected nodes, where each node stores the data and the address of the next node and connected by pointers.  DATA – the value or information stored in node.  REFERENCE / NEXT POINTER - a pointer or reference to the next node in the sequence. It stores the memory address (reference) of the next node in the sequence.  HEAD - linked list is accessed through the head node which points to the first node in the list.  NULL - the last node in the list points to null indicating the end of the list and also known as the tail node.  Singly Linked List - the nodes only point to the address of the next node in the list. Each node has data and address that field that contains a reference to the next node.   Doubly Linked List - the nodes point to the address of both previous and next nodes. Contain a three buckets in one node, one bucket holds the data and the other buckets holds the addresses of the previous and next nodes in the list.  LINK - each link of a linked list can store a data called element.  NEXT - each link of a linked list contains a link to the next link called next.  PREV - each link of a linked list contains a link to the previous link called Prev.  Circular Linked List - the last node in the list will point to the first node in the list. *Since the last node and the first node of the circular linked list are connected, the traversal in this linked list will go on forever until it is broken. LINKEDLIST OPERATIONS  TRAVERSAL - To traverse / display all nodes one by one.  INSERTION - To insert new nodes at specific positions (beginning, end or any position within the list)  DELETION - To delete nodes from a specific positions. (beginning, end or from a specific position).  SEARCHING - To search for an element from the linked list. - comparing every element in the list with the key element. - Searching for an element in the list is using a key element.  REVERSE - We need to make the last node to be pointed by the head node and reverse the whole linked list. import.java.util.LinkedList; -to specifically import the LinkedList class from the java.util package INITIALIZING LINKEDLIST LinkedList list = new LinkedList(); -creating an empty linked list that holds String elements. TRAVERSAL list.display(); System.out.println(list); - to simply print the list. ADDING/INSERTING ELEMENTS list.addFirst(”Apple”); list.insertAtBegin(10); - to add elements to the beginning of the list ADDING/INSERTING ELEMENTS list.addLast(”Apple”); list.add(”Apple”); list.insertAtEnd(30); - to add elements at the end of the list. ADDING/INSERTING ELEMENTS list.insertPosition(2, 3); list.insertAtPosition(0, 25); list.add(0, 25); - to add elements at the specific DELETING ELEMENTS list.deleteNode(4); list.remove(”Max”); - to simply delete specific value in the list. DELETING ELEMENTS list.deleteFromStart(); list.deleteAtBegin(); list.removeFirst(); - to simply delete the head node. DELETING ELEMENTS list.removeLastNode(); list.deleteAtEnd(); list.removeLast(); - to simply delete the last node. SEARCHING ELEMENTS list.searchNode(2); -to simply search the list with the value 2. REVERSE ELEMENTS list.reverse(); -to simply reverse the value of the list. STACKS AND QUEUES STACKS - is a linear type of data structures that follows the Last-in-First-out (LIFO) principle. - -means that the last element inserted inside the stack is removed first. - -allows insertion and deletion operations from one end of the stack which is at the top.  OPERATIONS OF STACKS  PUSH – adds an element to the top of a stack.  POP – remove an element from the top of a stack.  ISEMPTY – check if the stack is empty.  ISFULL – check if the stack is full.  PEEK/TOP – get the value of the top element without removing it.  MAXSIZE – variable that is describes the maximum number of elements in a queue. Import java.util.Stack; -to specifically import the Stack class from the java.util package. INITIALIZATION: Stack stack = new Stack(); Initializes a stack that holds integer objects ADDING A VALUE IN THE STACKS: stack.push(20); stack.push(“DSA”); Simply adding the element at the top of our stack. REMOVING VALUE IN THE STACKS: stack.pop(); DISPLAYING THE TOP/PEEK: stack.peek(); QUEUES QUEUES - is a linear data structure that is open both ends and the operations are performed in FIFO (First-in-First-out) order. - this means that the first element added to the queue will be the first one to be removed. - we define queue to be a list in which all additions are made at one end (BACK/TAIL/REAR), and all deletions from the list made at the other end (FRONT/HEAD). - First come first serve in real scenario. QUEUES COMPONENTS  FRONT– the index or pointer to the element at the beginning of the queue.  REAR – the index or pointer to the element at the end of the queue.  QUEUE SIZE – the maximum number of elements the queue can hold,  QUEUE LENGTH – the number of elements currently in the queue.  ELEMENT – which is the data. QUEUES OPERATIONS  ENQUEUE– Adds an element to the rear of the queue.  DEQUEUE – Removes an element from the front of the queue.  PEEK/FRONT– Retrieves/Viewing the element at the front of the queue without removing it.  ISEMPTY– Checks if the queue is empty.  ISFULL – Checks if the queue is full.  SIZE– Returns the number of elements in the queue.  REAR – Returns the element at the rear end without removing it.  QUEUES IMPLEMENTATION - can be implemented through Array, Linked List and Stacks. - QUEUES TYPES 1. Simple Queue 2. Circular Queue 3. Priority Queue 4. Double-Ended Queue (Deque) SIMPLE QUEUE SIMPLE QUEUE - the basic form of a queue where elements are added at the rear and removed from the front. - initial state for rear be set to -1 which makes it easy to identify an empty queue and the front will starts at 0 because the first element will be added at index 0. CIRCULAR QUEUE CIRCULAR QUEUE - is the extended version of a regular queue where the last element is connected to the first element. - forming a circle-like structure and also called as Ring Buffer. - initial state for circular queue will be set to -1 for both front and rear which indicates as an empty space. Using -1 helps in managing the circular queue nature of the queue efficiently. PRIORITY QUEUE - a special type of queue in which element is associated with a priority value. - elements are either arranged in an ascending or descending order and are served on the basis of their priority. - supports only comparable elements. - element with the higher priority will be deleted before the deletion of the lesser priority. - can be implemented in arrays, linked list, heap and binary search tree. - two types: Ascending order priority queue and Descending order priority queue. Ascending order priority queue - a lower priority number is given as a higher priority like we take 1 to 5 and the smallest number is given as the highest priority which start from 1. Descending order Priority queue - a higher priority number is given as a higher priority like we take 1 to 5 and the largest number is given as the highest priority which start from 5. DEQUE (DOUBLE ENDED QUEUE) - insert and delete operation can either be performed from the front or the rear. - it does not follow FIFO rule. - typically restricts operations to only one end. - 2 types: Input Restricted Deque, Output Restricted Deque DEQUE OPERATIONS  INSERTIONS AT FRONT – adds an element at the front.  INSERTIONS AT REAR – adds an element to the rear.  DELETION AT FRONT – removes an element from the front.  DELETION AT REAR – removes an element from the rear.  PEEK, ISEMPTY, ISFULL, SIZE METHODS OF DEQUE  getLast() / peekLast() – returns the last element of the deque.  removeFirst() / pollFirst() – returns and removes the first element of the deque.  removeLast() / pollLast() – returns and removes the last element of the deque. APPLICATIONS OF DEQUE  Palindrome checker – string or a number that reads the same backward and forward like madam, radar , 101 and etc.  Multiprocessor Scheduling, task scheduling, Sliding window algorithms and more. INPUT RESTRICTED DEQUE - is a special case of a double-ended queue where data can be inserted from one end (rear) but can be removed from both ends (front and rear). OUTPUT RESTRICTED DEQUE - is a special case of a double-ended queue where data can be removed from one end (front) but can be inserted from both ends (front and rear). Import Java.util.Queue; -to specifically import the Queue class from the java.util package. INITIALIZATION: Queue queue = new LinkedList(); - Initializes a queue where elements are managed in FIFO order. The Linked List is used internally to handle the queue operations. ADDING QUEUE: REMOVING QUEUE: CHECKING IF THE QUEUE IS FULL(Bounded queue) queue.add(“First”); queue.poll(“First”); ArrayBlockingQueue queue queue.remove(1); = new queue.offer(1); queue.pollLast(5); ArrayBlockingQueue(5); queue.addLast(5); queue.removeFirst(“Secon queue.size() == d”); queue.remainingCapacity(); queue.addFirst(“Second”); PEEK: queue.peek(); ISEMPTY: queue.isEmpty();