IT245 Module 1 - Data Structures - Saudi Electronic University - 2021

‫ت‬ ‫اﻟﺠﺎﻣﻌﺔ اﻟﺴﻌﻮد ﺔ اﻻﻟ وﻧ ﺔ‬ ‫ت‬ ‫اﻻﻟ وﻧ ﺔ‬ ‫اﻟﺠﺎﻣﻌﺔ اﻟﺴﻌﻮد ﺔ‬ ‫‪26/12/2021‬‬ ‫‪1‬‬ College of Computing and Informatics IT Program IT245 Data Structure 2 IT245 Data Structure Module 1...

‫ت‬ ‫اﻟﺠﺎﻣﻌﺔ اﻟﺴﻌﻮد ﺔ اﻻﻟ وﻧ ﺔ‬ ‫ت‬ ‫اﻻﻟ وﻧ ﺔ‬ ‫اﻟﺠﺎﻣﻌﺔ اﻟﺴﻌﻮد ﺔ‬ ‫‪26/12/2021‬‬ ‫‪1‬‬ College of Computing and Informatics IT Program IT245 Data Structure 2 IT245 Data Structure Module 1 Introduction to Data Structures  1. Why Data Structure? 2. Mathematics Review 3. Implementing Generic Components Pre-Java 5 4. Implementing Generic Components Using Java 5 Generics 5. Algorithms as a technology Contents 4  1. Recall the major mathematics concepts 2. Review the basic of Java Primitive data types, classes, objects and Interface 3. Introduce the concept of Algorithm design Weekly Learning Outcomes 5 Required Reading 1. Chapter 1 (Data structures and algorithm analysis in Java by Mark Allen Weiss) Recommended Reading 1. Chapter 1 (al, Cormen Thomas H et. Introduction to Algorithms. Cambridge, MA: MIT Press, 2009) 2. Beyond Basic Arithmetic: https://docs.oracle.com/javase/tutorial/java/data/beyondmath.html 6  Why Data Structure? 7 Why Data Structure? “Why not just use a big array?” Example problem Search for a number k in a set of N numbers Solution Store numbers in an array of size N Iterate through array until find k Number of checks Best case: 1 (k=29) Worst case: N (k=25) Average case: N/2 8 Why Data Structure? Suppose you have a group of N numbers and would like to determine the kth largest. This is known as the selection problem. One way to solve this problem would be to read the N numbers into an array, sort the array in decreasing order by some simple algorithm, and then return the element in position k. A somewhat better algorithm might be to read the first k elements into an array and sort them (in decreasing order). Next, each remaining element is read one by one. As a new element arrives, it is ignored if it is smaller than the kth element in the array. Otherwise, it is placed in its correct spot in the array, bumping one element out of the array A simulation using a random file of 30 million elements and k = 15,000,000 will show that neither algorithm finishes in a reasonable amount of time; 9 Why Data Structure? Does it matter? The Message Appropriate data structures ease design and improve performance The Challenge Design appropriate data structure and associated algorithms for a problem Analyze to show improved performance 10  Mathematics Review 11 Mathematics Review Exponents 12 Mathematics Review Logarithms In computer science, all logarithms are to the base 2 unless specified otherwise. Definition 1.1. XA = B if and only if logX B = A Several convenient equalities follow from this definition. Review Page 3 in Chapter 1 (Required Book) for more revision. 13 Mathematics Review Series The easiest formulas to remember are Also, suppose: S = 1 + A + A2 + A3 + A4 + A5 + · · · Then: AS = A + A2 + A3 + A4 + A5 + · · · If we subtract these two equations S - AS = 1 Thus: 14 Mathematics Review Brief Revision to Recursion A function that is defined in terms of itself is called a recursive function. f(x) = 0, if x = 0 = 2f(x - 1) + x2, otherwise From this definition we see that: f(0) = 0 f(1) = 1 f(2) = 6 f(3) = 21 f(4) = 58 15 Mathematics Review Brief Revision to Recursion Lines 3 and 4 handle what is known as the base case. Line 6 is the recursive call 16 Mathematics Review Brief Revision to Recursion Following are the first two fundamental rules of recursion: 1. Base cases. You must always have some base cases, which can be solved without recursion. 2. Making progress. For the cases that are to be solved recursively, the recursive call must always be to a case that makes progress toward a base case. 17 Mathematics Review Brief Revision to Recursion Printing Out Numbers Example: Suppose we have a positive integer, n, that we wish to print out. Recursion provides a very clean solution to this problem. To print out 76234, we need to first print out 7623 and then print out 4. The second step is easily accomplished with the statement printDigit(n%10) 18 Mathematics Review Design rule for Recursive Function 1. Base cases. You must always have some base cases, which can be solved without recursion. 2. Making progress. For the cases that are to be solved recursively, the recursive call must always be to a case that makes progress toward a base case. 3. Design rule. Assume that all the recursive calls work. 4. Compound interest rule. Never duplicate work by solving the same instance of a problem in separate recursive calls. 19  Implementing Generic Components Pre-Java 5 20 Implementing Generic Components Pre-Java 5 A generic implementation can be used to describe the basic functionality. For instance, a method can be written to sort an array of items; the logic is independent of the types of objects being sorted, so a generic method could be used. 21 Implementing Generic Components Pre-Java 5 Using Object for Genericity A generic MemoryCell class (pre-Java 5) 22 Implementing Generic Components Pre-Java 5 Using Object for Genericity To access a specific method of the object, we must downcast to the correct type. primitive types cannot be used. Only reference types are compatible with Object 23  Implementing Generic Components Pre-Java 5 Wrappers for Primitive Types Wrapper class: One typical use is to store a primitive type, and add operations that the primitive type either does not support or does not support correctly. Java provides a wrapper class for each of the eight primitive types. For instance, the wrapper for the int type is Integer. Each wrapper object is immutable (meaning its state can never change) 24  Implementing Generic Components Using Java 5 Generics 25 Simple Generic Classes and Interfaces When a generic class is specified, the class Description declaration includes one or more type parameters enclosed in angle brackets after the class name. Line 1 shows that the GenericMemoryCell takes one type parameter. In this instance, there are no explicit restrictions on the type parameter, so the user can create types such as GenericMemoryCell and GenericMemoryCell but not GenericMemoryCell. Inside the GenericMemoryCell class declaration, we can declare fields of the generic type and methods that use the generic type as a parameter or return type. 26 Simple Generic Classes and Interfaces The Diamond Operator Line 5 is annoying because since m is of type GenericMemoryCell, it is obvious that object being created must also be GenericMemoryCell; any other type parameter would generate a compiler error. Java 7 adds a new language feature, known as the diamond operator, that allows line 5 to be rewritten as GenericMemoryCell m = new GenericMemoryCell( ); 27 Simple Generic Classes and Interfaces The Diamond Operator 28  Simple Generic Classes and Interfaces Auto-Boxing/Unboxing between Primitives and their Wrapper Objects A Java Collection (such as List and Set) contains only objects. It cannot holds primitives (such as int and double). On the other hand, arrays can hold primitives and objects, but they are not resizable. To put a primitive into a Collection (such as ArrayList), you have to wrap the primitive into an object using the corresponding primitive wrapper class. // Pre-JDK 5 Integer intObj = new Integer(5566); // wrap an int to Integer by constructing an instance of Integer int i = intObj.intValue(); // unwrap Integer to int Double doubleObj = new Double(55.66); // wrap double to Double double d = doubleObj.doubleValue(); // unwrap Double to double 29 Reference: https://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGeneric.html Simple Generic Classes and Interfaces Auto-Boxing/Unboxing between Primitives and their Wrapper Objects The pre-JDK 5 approach involves quite a bit of codes to do the wrapping and unwrapping. JDK 5 introduces a new feature called auto-boxing and auto-unboxing to resolve this problem, by delegating the compiler to do the job. For example, // JDK 5 Integer intObj = 5566; // auto-box from int to Integer by the compiler int i = intObj; // auto-unbox from Integer to int by the compiler Double doubleObj = 55.66; // auto-box from double to Double double d = doubleObj; // auto-unbox from Double to double 30 Reference: https://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGeneric.html  Simple Generic Classes and Interfaces Enhanced for-each Loop (JDK 5) import java.util.List; import java.util.ArrayList; public class J5ForEachLoopTest { public static void main(String[] args) { // Use for-each loop on Array int[] numArray = {11, 22, 33}; for (int num : numArray) System.out.println(num); //11 //22 //33 // Same as: for (int idx = 0; idx < numArray.length; ++idx) System.out.println(numArray[idx]); // Use for-each loop on Collection List coffeeLst = new ArrayList(); coffeeLst.add("espresso"); coffeeLst.add("latte"); for (String coffee : coffeeLst) System.out.println(coffee.toUpperCase()); //ESPRESSO //LATTE } } 31 Reference: https://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGeneric.html Simple Generic Classes and Interfaces Generic Wildcard (?) and Bounded Type Parameters Wildcard (?) can be used to represent an unknown type in Generics: : called unbounded wildcard which accepts all types. Bounded Type Parameters have the forms: : called upper bounded type parameter which accepts the specified ClassName and its subtypes. The upper bound type is ClassName. Review Examples in the Book, Chapter 1, pages: 19 to 24. 32  Examples on Generic Generic Methods public class GenericMethodTest { // generic method printArray public static < E > void printArray( E[] inputArray ) { // Display array elements for(E element : inputArray) { System.out.printf("%s ", element); } System.out.println(); } public static void main(String args[]) { // Create arrays of Integer, Double and Character Integer[] intArray = { 1, 2, 3, 4, 5 }; Double[] doubleArray = { 1.1, 2.2, 3.3, 4.4 }; Character[] charArray = { 'H', 'E', 'L', 'L', 'O' }; System.out.println("Array integerArray contains:"); printArray(intArray); // pass an Integer array System.out.println("\nArray doubleArray contains:"); printArray(doubleArray); // pass a Double array System.out.println("\nArray characterArray contains:"); printArray(charArray); // pass a Character array } 33 } Reference: https://www.tutorialspoint.com/java/java_generics.htm  Examples on Generic Bounded Type Parameters Reference: https://www.tutorialspoint.com/java/java_generics.htm 34  Examples on Generic Generic Classes 35 Reference: https://www.tutorialspoint.com/java/java_generics.htm  Algorithms as a technology 36 Algorithms as a technology Algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. Reference: https://www.geeksforgeeks.org/introduction-to-algorithms/ 37 Algorithms as a technology Characteristics of an Algorithm Reference: https://www.geeksforgeeks.org/introduction-to-algorithms/ 38 Algorithms as a technology Algorithm Example: Example: Consider the example to add three numbers and print the sum. Step 1: Fulfilling the pre-requisites As discussed above, in order to write an algorithm, its pre-requisites must be fulfilled. The problem that is to be solved by this algorithm: Add 3 numbers and print their sum. The constraints of the problem that must be considered while solving the problem: The numbers must contain only digits and no other characters. The input to be taken to solve the problem: The three numbers to be added. The output to be expected when the problem the is solved: The sum of the three numbers taken as the input. The solution to this problem, in the given constraints: The solution consists of adding the 3 numbers. It can be done with the help of ‘+’ operator, or bit-wise, or any other method. Step 2: Designing the algorithm Now let’s design the algorithm with the help of above pre-requisites: Algorithm to add 3 numbers and print their sum: START Declare 3 integer variables num1, num2 and num3. Take the three numbers, to be added, as inputs in variables num1, num2, and num3 respectively. Declare an integer variable sum to store the resultant sum of the 3 numbers. Add the 3 numbers and store the result in the variable sum. Print the value of variable sum END Step 3: Testing the algorithm by implementing it. 39 Algorithms as a technology Algorithms and Data structures A data structure is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes, and so it is important to know the strengths and limitations of several of them. 40 Algorithms as a technology Suppose computers were infinitely fast and computer memory was free. Would you have any reason to study algorithms? The answer is yes, if for no other reason than that you would still like to demonstrate that your solution method terminates and does so with the correct answer. 1. Computers may be fast, but they are not infinitely fast 2. Memory may be inexpensive, but it is not free. Computing time is therefore a bounded resource. So is space in memory is bounded. You should use these resources wisely, and algorithms that are efficient in terms of time or space will help you do so. 41 Algorithms as a technology Algorithm Efficiency Different algorithms devised to solve the same problem often differ dramatically in their efficiency. These differences can be much more significant than differences due to hardware and software. 42 Algorithms as a technology Algorithms and other technologies You might wonder whether algorithms are truly that important on contemporary computers in light of other advanced technologies, such as: easy-to-use, intuitive, graphical user interfaces (GUIs), integrated Web technologies. The answer is yes. For example, consider a Web-based service that determines how to travel from one location to another. Its implementation would rely on : fast hardware a graphical user interface wide-area networking However, it would also require algorithms for certain operations, such as: finding routes (probably using a shortest-path algorithm) rendering maps 43 References 1. Data structures and algorithm analysis in Java by Mark Allen Weiss 44 Smart data structures, good algorithm and dumb code works a lot better than the other way around. Eric Raymond 45 Thank You 46