Week 1 Lec 1-5 with watermarking.pdf

E L P T N Data Structures and Algorithms Using Java Debasis Samanta Department of Computer Science & Engineering, IIT Kharagpur Module 01: Introduction Lecture 01 : Introduction and Course Plan  E L  About Data...

E L P T N Data Structures and Algorithms Using Java Debasis Samanta Department of Computer Science & Engineering, IIT Kharagpur Module 01: Introduction Lecture 01 : Introduction and Course Plan  E L  About Data P T  Importance of Data Structures N  Different Types of Data Structures  Course Objectives  Course Plan  Resources for Learning  E L P T About Data N  E L About data Example: T 10, 25, …, Kharagpur, 10CS3002, [email protected] Anything else? P Data vs. Information N 100.0, 0.0, 250.0, 150.0, 220.0, 300.0, 110.0 Is there any information?  E L Sources of data Social media and networks (All of us are generating data) P T Scientific instruments (Collecting all sorts of data) Mobile devices (Tracking all objects all the time) N Sensor technology and networks (Measuring all kinds of data)  E L Measuring the size of data P T N The ever largest unit Quintillion bytes of data 1 Quintillion bytes = 1018 (US standard) = 1030 (Old standard)  E L P TWhy Data Structures? N  E L Importance of data structures T Primitive data Abstract data P Storing data N Retrieving data  E L P T Different Data Structures N  E L Types of data structures 1 2 Top Front Rear T Classic data structures n Array Stack Queue P Linear Non-linear Linked list Linear data structures (a) Linear data structures N Arrays Linked lists Stacks Queues Non-linear data structures Tree Graph Set Table Trees Graphs Tables Sets (b) Nonlinear data structures  E L P TCourse Objectives N  E L Course objectives P T N  E L Course objectives T Java supports for programming Java supports for data structures P Encapsulation java.util Inheritance class String Package and interface java.io N Exception handling Multithreading AWT, Swing, JavaFX Networking JDBC  E L P TCourse Plan N  E L Course plan : Modules Module Topics T 1 Introduction 2 Generic Programming 3 Java Collection Framework P 4 Array 5 Linked List 6 Stack 7 Queue N 8 Trees 9 Tables 10 Set 11 Graphs 12 File Handling 13 Searching 14 Sorting 15 String and Utility  E L Course plan : Week‐wise lectures Week# Topic Week# Topic Week# Topic Introduction Stack Data Structures Operations on Set Collections T Generic Methods Programming for Stacks Java IO Streams Week 1 Week 5 Week 9 Basics of Generic Classes Stack Using JCF IO with Byte Streams Parametrized Generic Classes Queue Data Structures IO with Character Streams Bounded Argument in Generic Classes Programming for Queues File IO P Basic of JCF Queue Using JCF Random Access File Week 10 Collections of JCF Understanding Tree Data Structures Linear Searching Algorithms Week 2 Week 6 Set of JCF Operations on Binary Trees Non‐linear Searching Algorithms Map of JCF Binary Search Tree Programming for Searching Java Legacy Classes Programming for BST Simple Sorting Algorithms N Array Data Structure Height Balanced Binary Search Tree Improved Sorting Algorithms Week 11 Programming with Arrays Heap Trees Advanced Sorting Algorithms Week 3 Week 7 ArrayList for Arrays Programming for Heap Trees Programs for Sorting (Part‐I) Arrays for Arrays Huffman Tree Programs for Sorting (Part‐II) Vector for Arrays Graph Structures Sorting Using JCF Linked List Data Structure (Part‐I) Graph Algorithms String Class Week 12 Linked List Data Structure (Part‐II) Map Framework in Java Applications of String Class Week 4 Week 8 Programming for Linked List (Part‐I) Applications of Map (Part‐I) Class StringBuffer Programming for Linked List (Part‐II) Applications of Map (Part‐II) Miscellaneous Utilities Linked List Using JCF Set Collection in Java Java Cursor Iterator  E L P TResources for Studies N  E L Reference: Data Structures and Algorithms P T N  E L Reference: Programming in Java P T N  E L Reference: Data Structures and Algorithm in Java P T N  E L Reference: Programming for Data Structures and Algorithms P T N  E L Reference: Internet Repositories P T GeeksForGeeks: https://www.geeksforgeeks.org/ Javatpoint: https://www.javatpoint.com/ N Java Oracle: https://docs.oracle.com/javase/tutorial/  E L Reference: Last but not the least P T This course study materials: http://cse.iitkgp.ac.in/~dsamanta/javads/index.html FAQ: https://nptel.ac.in/noc/faqnew.php N  E L Hints and tips Discussion Forum T Getting Started with the Forum: 1. You can ask us questions, doubts, etc. during the run of the course. P 2. Our turnover time for replying is approximately 1 day. 3. Try to provide references and details regarding your queries, so that we can solve them quickly. N 4. Officially, we don't support WhatsApp group and we encourage students to discuss everything related to the course in the Discussion Forum only. 5. Any group out of the NPTEL Discussion Forum is not controlled by NPTEL, so NPTEL is not responsible for anything outside of the Forum.  E L Hints and tips During the Course T Do’s 1. Try to regularly practice all the programs discussed in each lecture, immediately after attending the lecture video. P 2. Check references provided at the end of each lecture. 3. Required study materials will be provided; from which you should practice. 4. Inform us if you are facing any issue regarding any topic in the Forum. 5. You should submit the assignments well before the time to avoid any submission issue. N Don'ts 1. Avoid copying answers to solve assignments, try to understand and give your own answer. 2. You should not submit the assignments just before the submission time, huge traffic may lead to not submitting the assignments in time. If this happens, we won’t be able to do anything in this regard.  E L P T N  E L P T N Data Structures and Algorithms Using Java Debasis Samanta Department of Computer Science & Engineering, IIT Kharagpur Module 02: Generic Programming Lecture 02 : Generic methods  E L P T  Concept of Generic Definition  Parameters Passing N  Generic Methods with Variable List of Arguments  Using an Array  Using an Object  Using Ellipsis  E L P TConcept N  E L Concept of data types T float int String P File Data Table N graph boolean User defined  E L Methods to take any type of data P T N  E L Example of generic methods P T N...... Q1 : How a class can be made generic? Q2 : How a method can be generic?  E L P TGeneric Methods N  E L Example of ‘swap’ program T Before Swap During Swap After Swap N P  E L Writing a ‘swap’ method P T void swap(int x, int y){ int temp; temp = x; x = y; N y = temp; }  E L Generic method : Example of ‘swap’ program T Object o1; Object o2; P void swap(o1, o2) N  E L Generic method: Syntax T A method that can refer to any data type is known as a generic method. P The syntax for declaring a generic method is as follows: N mName( ) { //Body of the method }  E L Example 2.1: A generic method for printing T class DemoClass { // Defining a generic method to print any data type void genericPrint (T t) { P System.out.println (t); } public static void main(String[] args) { DemoClass aObj; // Creating an object of the class DemoClass N aObj.genericPrint(101); // Calling generic method with int argument aObj.genericPrint("Joy with Java"); // Calling generic method with String aObj.genericPrint(3.1412343); // Calling generic method with double } }  E L Generic method versus method overloading T Note: 1. You can readily understand the similarity between method overloading and generic method. Both the concepts have the same objective, but in their own ways. P 2. The main difference is that in case of method overloading, we have to build code for each overloaded method, whereas, with generic method, same code can work for the different type of data. N 3. Further, with generic method, theoretically you can pass any type of data as argument; however, with method overloading only a limited number of arguments are allowed. 4. According to the class encapsulation, method overloading and method overriding are also applicable to generic methods.  E L Example 2.2 : Static generic method T class StaticGenericMethodDemo{ // Defining a static generic method to print any data type P static void genericPrint (T t){ //The following statement print which type parameter T this method is handling System.out.println (t.getClass().getName() + ":" + t); } N public static void main(String[] args){ genericPrint(101); // Calling generic method with integer argument genericPrint("Joy with Java"); // Calling generic method with String argument genericPrint(3.1412343); // Calling generic method with double argument } }  E L P TParameter(s) Passing N  E L Parameter passing T Type(s) of parameter(s) in a method definition is an issue. P Note: N Parameter(s) should be class type(s)  Example 2.3: Generic method for Integer swap operation E L T class SwapTest1{ public static void swap(T x, T y){ T temp; P t = x; x = y; y = t; } N public static void main(String args[]){ Integer x = new Integer(99); Integer y = new Integer(66); System.out.println("x = “ + x + " “ + "y = “ + y); swap(x, y); System.out.println("x = “ + x + " “ + "y = “ + y); } }  Example 2.4: Generic method for Double swap operation E L T class SwapTest2{ public static void swap(T x, T y){ T temp; P t = x; x = y; y = t; } public static void main(String args[]){ N Double x = new Double(99.0); Double y = new Double(66.0); System.out.println("x = “ + x + " “ + "y = “ + y); swap(x, y); System.out.println("x = “ + x + " “ + "y = “ + y); } }  Example 2.5: Generic method for String swap operation E L T class SwapTest3{ public static void swap(T x, T y){ T temp; t = x; P x = y; y = t; } public static void main(String args[]){ N String x = "99"; String y = "66"; System.out.println("x = “ + x + " “ + "y = “ + y); swap(x, y); System.out.println("x = “ + x +" “ + "y = “ + y); } }  E L Example 2.6: Swap method with Object as parameters T class Person { String name; float marks; Person(String name, float marks) { this.name = name; this.marks = marks P } } class SwapTest4{ public static void swap(Object x, Object y){ Object t; N t = x; x = y; y = t; } public static void main(String args[]){ Object p1 = new Person(“Sumit”, 99.9); Double p2 = new Double(”Rahul”, 66.6); System.out.println(“p1 = “ + p1 + " “ + "y = “ + p2); swap(p1, p2); System.out.println(“p1 = “ + p1 + " “ + "y = “ + p2); } }  E L P TMethods with Variable List of Parameters N  E L Declaration of “varargs” methods T 1. Using an array gMethod1(T[] t); P 2. Using ellipsis ( three dots) N gMethod2(T... t); 3. Using Object class gMethod3(Object[] o);  E L varargs methods using array T You can define a varargs method with an argument an array (of any type). P In other words, the values which you want to pass to a method, store them in an array and then pass the array to the method. That’s all! N  E L Example 2.7: varargs method using array T class VarargsMethodDemo1 { static void varargsMethod1(int v[]) { System.out.print("Number of args: " + v.length +" Elements: "); for(int x : v) P System.out.print(x + " "); System.out.println(); } public static void main(String args[]) { // Following arrays are created for test... int x[] = { 1, 3, 5, 7 }; N int y[] = { 2, 4}; int z[] = { }; varargsMethod1 (x); // Passed 4 values to the method varargsMethod1 (y); // Passed 2 values to the method varargsMethod1 (z); // Passed no argument to the method } }  E L varargs methods using Ellipsis T The syntax to define varargs method with this approach is given below. P (...) { N... // Method body }  E L Example 2.8: varargs method using Ellipsis T class VarargsMethodDemo2 { //Defining a varargs method using ellipsis static void varargsMethod2(int...v) { System.out.println("Number of arguments: " + v.length); P for (int i: v) // For each item i in array v System.out.print(i + " "); System.out.println(); } N public static void main(String args[]) { // Calling the varargs method with variable arguments varargsMethod2 (9); // One parameter varargsMethod2 (1, -2, 3, -4); // Four parameters varargsMethod2 (); // no parameter } }  E L Variable methods using Object T 1. This is the most elegant approach to implement the varargs method in a Java program. 2. It uses the ellipsis and in addition to this, it uses the Object type. P 3. For example, to define a varargs method using Object, your method declaration should take the following form. N public static void methodName(Object...obj) { //Body of the method } Note: The restriction that the method can have zero or more parameters preceding this, but this must be the last.  E L Example 2.9: varargs method using Objects T class VarargsMethodDemo3 { public static void varargsMethod3(Object... obj) { P for(Object o : obj) System.out.print(“ “ + o); System.out.println( ); } public static void main(String[] args) { N varargsMethod3( 1, “String”, 2.3, true); // Four arguments varargsMethod3 (); // No arguments varargsMethod3 (15, 25, 35, 45, 55); // Five arguments } }  E L P T N https://cse.iitkgp.ac.in/~dsamanta/javads/index.html https://nptel.ac.in/noc/faqnew.php  E L P T N  E L P T N Data Structures and Algorithms Using Java Debasis Samanta Department of Computer Science & Engineering, IIT Kharagpur Module 02: Generic Programming Lecture 03 : Basics of Generic Class  E L P T  Concept of Generic Class  Defining Generic Class N  Examples  Defining Generic Class  Generic Class with Arrays  Generic Class with Abstract Data Type  E L P TConcept of Generic Class N  E L Why generic class? T Let us consider the case of processing of an array of any type of numbers using a Java program. P 1. Initializing the array. N 2. Printing the elements in the array. 3. Reversing the ordering of the elements in the array.  E L Why generic class? Here, is the program structure which you should consider, in case the array stores integer numbers. T class SpecificArrayInt { P // Declaring an array of integer values // Constructor to load the array. // Method to print the array elements. N // Method to reverse the array elements. } class MainClassInt { }  E L Example 3.1 : Program to handle an array of integers T class SpecificArrayInt { // Declaring an array of integer numbers P int a; // Constructor to load the array SpecificArrayInt(int a[]) { this.a = a; } N // Method to print the array elements void printInt() { for(int x : a) System.out.println(x); } // Continued to next page...  E L Example 3.1 : Program to handle an array of integers T // Continued on... // Method to reverse the array elements P void reverseInt() { j = a.length; for (int i=0; i