Exam 3 Review Fall 2024 PDF

Exam 3 Review Exam 3 - Thursday 5th Dec in class With Question/Answer Animations © 2019 McGraw-Hill Education. All rights reserved. Authorized only for...

Exam 3 Review Exam 3 - Thursday 5th Dec in class With Question/Answer Animations © 2019 McGraw-Hill Education. All rights reserved. Authorized only for instructor use in the classroom. No reproduction or further distribution permitted without the prior  Topics in Exam 2 Chapters 10, 11, 13, 18, 20, 21, 22, 23,24,25,28 from the textbook © 2019 McGraw-Hill Education  Question Types 1 - Fill in the blanks 2 - True/ False 3 – Problems 4 – Comparisons/ Matchings 5 – Multiple choice 6 – Yes/No © 2019 McGraw-Hill Education  Tips to do well 1 - Read the covered section from book 2 - Solve the exercises for these sections 3 – Go through lecture videos, slides and notes 4 - Go through Homeworks and Quizzes 5 – Go through activities 6 – Practice © 2019 McGraw-Hill Education  Tips to do well 1 - Exam is in class from 2.30 pm to 3.45 pm 2 - Keep paper, pen/pencil and eraser 3 – Keep calculator 4 – Read questions carefully 5 – If you can’t solve then move quickly to next question time is limited © 2019 McGraw-Hill Education  Identifiers An identifier is a sequence of characters that consist of letters, digits, underscores (_), and dollar signs ($). An identifier must start with a letter, an underscore (_), or a dollar sign ($). It cannot start with a digit. An identifier cannot be a reserved word. (See Appendix A, “Java Keywords,” for a list of reserved words). An identifier cannot be true, false, or null. An identifier can be of any length. © 2019 McGraw-Hill Education  Variables // Compute the first area radius = 1.0; area = radius * radius * 3.14159; System.out.println("The area is “ + area + " for radius "+radius); // Compute the second area radius = 2.0; area = radius * radius * 3.14159; System.out.println("The area is “ + area + " for radius "+radius); © 2019 McGraw-Hill Education  Declaring Variables int x; // Declare x to be an // integer variable; double radius; // Declare radius to // be a double variable; char a; // Declare a to be a // character variable; © 2019 McGraw-Hill Education  Assignment Statements x = 1; // Assign 1 to x; radius = 1.0; // Assign 1.0 to radius; a = 'A'; // Assign 'A' to a; © 2019 McGraw-Hill Education  Declaring and Initializing in One Step int x = 1; double d = 1.4; © 2019 McGraw-Hill Education  Named Constants final datatype CONSTANTNAME = VALUE; final double PI = 3.14159; final int SIZE = 3; © 2019 McGraw-Hill Education  Naming Conventions (1 of 2) Choose meaningful and descriptive names. Variables and method names: – Use lowercase. If the name consists of several words, concatenate all in one, use lowercase for the first word, and capitalize the first letter of each subsequent word in the name. For example, the variables radius and area, and the method computeArea. © 2019 McGraw-Hill Education  Naming Conventions (2 of 2) Class names: – Capitalize the first letter of each word in the name. For example, the class name ComputeArea. Constants: – Capitalize all letters in constants, and use underscores to connect words. For example, the constant PI and MAX_VALUE © 2019 McGraw-Hill Education  Numerical Data Types Name Range Storage Size  27 to 27  1 128 to 127  byte 8-bit signed negative 2 to the power 7 to 2 to the power 7 minus 1 left parenthesis negative 128 to 127 right parenthesis.  215 to 215  1 32768 to 32767  negative 2 to the power 15 to 2 to the power 15 minus 1 left parenthesis (negative 32768 to 32767 right parenthesis. short 16-bit signed  2 to 2  1 2147483648 to 2147483647  31 31 negative 2 to the power 31 to 2 to the power 31 minus 1 left parenthesis negative 2147483648 to 2147483647 right parenthesis. int 32-bit signed  263 to 263  1 long negative 2 to the power 63 to 2 to the power 63 minus 1 left 64-bit signed parenthesis i.e.,  9223372036854775808 to 9223372036854775807 that is, negative 9223372036854775808 to  9223372036854775807 right parenthesis. Negative range: float 32-bit I E E E negative range, negative -3.4028235 E + 38 to negative 1.4 E minus 45, positive range, 1.4 E minus 45 to 3.4028235 E + 38.  3.4028235E  38 to  1.4E  45 Positive range: 754 1.4E  45 to 3.4028235E  38 Negative range: double 64-bit I E E E negative range, negative 1.7976931348623157 E + 308 to negative 4.9 E minus 324, positive range, 4.9 E minus 324 to 1.7976931348623157 E + 308.  1.7976931348623157E  308 to  4.9E  324 Positive range: 754 4.9E  324 to 1.7976931348623157E  308 © 2019 McGraw-Hill Education  Reading Numbers From the Keyboard Scanner input = new Scanner(System.in); int value = input.nextInt(); Method Description nextByte() reads an integer of the byte type. nextShort() reads an integer of the short type. nextInt() reads an integer of the int type. nextLong() reads an integer of the long type. nextFloat() reads a number of the float type. nextDouble() reads a number of the double type. © 2019 McGraw-Hill Education  Numeric Operators Name Meaning Example Result + Addition 34 + 1 35  The symbol of minus Subtraction 34.0  0.1 34.0 minus 0.1 33.9 * Multiplication 300 * 3030 300 times 9000 / 1.0 / 2.0 1.0 divided by 2.0. division slash Division 0.5 % 20 % 3 symbol of modulo remainder 20 modulo remainder 3 Remainder 2 © 2019 McGraw-Hill Education  Integer Division +,  , *, /, and % 5 / 2 yields an integer 2. 5.0 / 2 yields a double value 2.5 5 % 2 yields 1 (the remainder of the division) © 2019 McGraw-Hill Education  Remainder Operator Remainder is very useful in programming. For example, an even number % 2 is always 0 and an odd number % 2 is always 1. So you can use this property to determine whether a number is even or odd. Suppose today is Saturday and you and your friends are going to meet in 10 days. What day is in 10 days? You can find that day is Tuesday using the following expression: © 2019 McGraw-Hill Education  6. Every letter in a Java keyword is in lowercase? a. true b. false Key:a It is true that the keywords in Java are in lowercase. For example, public, static, int, double, and void are the keywords.# 7. Which of the following is a valid identifier? a. $343 b. class c. 9X d. 8+9 e. radius Key:ae class is a keyword, which cannot be used as an © 2019 McGraw-Hill Education  Section 2.5 Variables 8. Which of the following are correct names for variables according to Java naming conventions? a. radius b. Radius c. RADIUS d. findArea e. FindArea Key:ad A single-word variable is in lowercase. In a multiple-word variable, the words are concatenated with the first word in lowercase and the first letter of each subsequent word in uppercase. © 2019 McGraw-Hill Education  How to Evaluate an Expression Though Java has its own way to evaluate an expression behind the scene, the result of a Java expression and its corresponding arithmetic expression are the same. Therefore, you can safely apply the arithmetic rule for evaluating a Java expression. 3 + 4 * 4 + 5 * (4 + 3) - 1 (1) inside parentheses 3 + 4 * 4 + 5 * 7 – 1 first (2) multiplication 3 + 16 + 5 * 7 – 1 (3) multiplication 3 + 16 + 35 – 1 (4) addition 19 + 35 – 1 (5) addition 54 - 1 (6) subtraction 53 © 2019 McGraw-Hill Education  Logical Operators Operator Name Description ! not logical negation logical && and conjunction logical || or disjunction ^ exclusive or logical exclusion © 2019 McGraw-Hill Education  Truth Table for Operator ! p !p Example (assume age = 24, weight = 140) fals true !(age > 18) is false, because (age > 18) is true. e fals !(weight == 150) is true, because (weight == true e 150) is false. © 2019 McGraw-Hill Education  Truth Table for Operator && p1 && Example (assume age = 24, weight p1 p2 p2 = 140) fals (age 18) && (weight > 140) is false, true false e because (weight > 140) is false. (age > 18) && (weight >= 140) is true, true true true because both (age > 18) and (weight >= 140) are true. © 2019 McGraw-Hill Education  Truth Table for Operator || p1 || Example (assume age = 24, weight = p1 p2 p2 140) fals fals false Blank e e (age > 34) || (weight 34) is false, but (weight e 14) || (weight >= 150) is false, true e e because (age > 14) is true. tru true true Blank e © 2019 McGraw-Hill Education  Truth Table for Operator ^ Example (assume age = 24, weight p1 p2 p1 ^ p2 = 140) fals fals false e e (age > 34) ^ (weight >= 140) is true, fals true true because (age > 34) is false but (weight e >= 140) is true. (age > 14) ^ (weight > 140) is true, fals true true because (age > 14) is true and (weight e > 140) is false. true true false Blank © 2019 McGraw-Hill Education  Examples (1 of 2) Here is a program that checks whether a number is divisible by 2 and 3, whether a number is divisible by 2 or 3, and whether a number is divisible by 2 or 3 but not both: TestBooleanOperato rs © 2019 McGraw-Hill Education  Examples (2 of 2) System.out.println("Is " + number + " divisible by 2 and 3? " + ((number % 2 == 0) && (number % 3 == 0))); System.out.println("Is " + number + " divisible by 2 or 3? " + ((number % 2 == 0) || (number % 3 == 0))); System.out.println("Is " + number + " divisible by 2 or 3, but not both? " + ((number % 2 == 0) ^ (numberTestBooleanOperato % 3 == 0))); rs © 2019 McGraw-Hill Education  Trigonometric Methods sin(double a) Examples: cos(double a) Math.sin(0) returns 0.0 tan(double a) Math.sin(Math.PI / 6) acos(double a) returns 0.5 asin(double a) Math.sin(Math.PI / 2) atan(double a) returns 1.0 Math.cos(0) returns 1.0 Math.cos(Math.PI / 6) Radians returns 0.866 toRadians(90) Math.cos(Math.PI / 2) returns 0 © 2019 McGraw-Hill Education  Exponent Methods exp(double a) Examples: Returns e raised to the power Math.exp(1) returns 2.71 of a. Math.log(2.71) returns 1.0 log(double a) Math.pow(2, 3) returns 8.0 Returns the natural logarithm Math.pow(3, 2) returns 9.0 of a. Math.pow(3.5, 2.5) returns log10(double a) 22.91765 Returns the 10-based logarithm Math.sqrt(4) returns 2.0 of a. Math.sqrt(10.5) returns 3.24 pow(double a, double b) Returns a raised to the power of b. sqrt(double a) Returns the square root of a. © 2019 McGraw-Hill Education  Rounding Methods double ceil(double x) x rounded up to its nearest integer. This integer is returned as a double value. double floor(double x) x is rounded down to its nearest integer. This integer is returned as a double value. double rint(double x) x is rounded to its nearest integer. If x is equally close to two integers, the even one is returned as a double. int round(float x) Return (int)Math.floor(x+0.5). long round(double x) Return (long)Math.floor(x+0.5). © 2019 McGraw-Hill Education  Rounding Methods Examples Math.ceil(2.1) returns 3.0 Math.ceil(2.0) returns 2.0 Math.ceil(-2.0) returns –2.0 Math.ceil(-2.1) returns -2.0 Math.floor(2.1) returns 2.0 Math.floor(2.0) returns 2.0 Math.floor(-2.0) returns –2.0 Math.floor(-2.1) returns -3.0 Math.rint(2.1) returns 2.0 Math.rint(2.0) returns 2.0 Math.rint(-2.0) returns –2.0 Math.rint(-2.1) returns -2.0 Math.rint(2.5) returns 2.0 Math.rint(-2.5) returns -2.0 Math.round(2.6f) returns 3 Math.round(2.0) returns 2 Math.round(-2.0f) returns -2 Math.round(-2.6) returns -3 © 2019 McGraw-Hill Education  min, max, and abs max(a, b) and min(a, b) Examples: Returns the maximum or Math.max(2, 3) returns 3 minimum of two Math.max(2.5, 3) returns parameters. 3.0 abs(a) Math.min(2.5, 3.6) Returns the absolute value returns 2.5 of the parameter. Math.abs(-2) returns 2 random() Math.abs(-2.1) returns 2.1 Returns a random double value in the range [0.0, 1.0). © 2019 McGraw-Hill Education  The random Method Generates a random double value greater than or equal to 0.0 and less than 1.0 (0 max) max = myList[i]; } © 2019 McGraw-Hill Education  Declaring Variables of Two-dimensional Arrays and Creating Two-dimensional Arrays int[][] matrix = new int; or int matrix[][] = new int; matrix = 3; for (int i = 0; i < matrix.length; i++) for (int j = 0; j < matrix[i].length; j++) matrix[i][j] = (int)(Math.random() * 1000); double[][] x; © 2019 McGraw-Hill Education  Two-dimensional Array Illustration matrix.length? 5 array.length? 4 matrix.length array.length? ?5 3 © 2019 McGraw-Hill Education  Declaring, Creating, and Initializing Using Shorthand Notations © 2019 McGraw-Hill Education  Lengths of Two-dimensional Arrays (1 of 2) int[][] x = new int; © 2019 McGraw-Hill Education  Lengths of Two-dimensional Arrays (2 of 2) int[][] array = array.length { array.leng {1, 2, 3}, th {4, 5, 6}, array.leng {7, 8, 9}, th {10, 11, 12} array.leng }; th array.leng th array.length ArrayIndexOutOfBoundsException © 2019 McGraw-Hill Education  Ragged Arrays (1 of 2) Each row in a two-dimensional array is itself an array. So, the rows can have different lengths. Such an array is known as a ragged array. For example, int[][] matrix = { matrix.length is 5 {1, 2, 3, 4, 5}, matrix.length is 5 matrix.length is 4 {2, 3, 4, 5}, matrix.length is 3 {3, 4, 5}, matrix.length is 2 {4, 5}, matrix.length is 1 {5} }; © 2019 McGraw-Hill Education  Ragged Arrays (2 of 2) © 2019 McGraw-Hill Education  Processing Two-Dimensional Arrays See the examples in the text. 1. (Initializing arrays with input values) 2. (Printing arrays) 3. (Summing all elements) 4. (Summing all elements by column) 5. (Which row has the largest sum) 6. (Finding the smallest index of the largest element) 7. (Random shuffling) © 2019 McGraw-Hill Education  Initializing Arrays With Input Values java.util.Scanner input = new Scanner(System.in); System.out.println("Enter " + matrix.length + " rows and " + matrix.length + " columns: "); for (int row = 0; row < matrix.length; row++) { for (int column = 0; column < matrix[row].length; column++) { matrix[row][column] = input.nextInt(); } } © 2019 McGraw-Hill Education  Initializing Arrays With Random Values for (int row = 0; row < matrix.length; row++) { for (int column = 0; column < matrix[row].length; column++) { matrix[row][column] = (int)(Math.random() * 100); } } © 2019 McGraw-Hill Education  Printing Arrays for (int row = 0; row < matrix.length; row++) { for (int column = 0; column < matrix[row].length; column++) { System.out.print(matrix[row][column] + " "); } System.out.println(); } © 2019 McGraw-Hill Education  Summing All Elements int total = 0; for (int row = 0; row < matrix.length; row++) { for (int column = 0; column < matrix[row].length; column++) { total += matrix[row][column]; } } © 2019 McGraw-Hill Education  Summing Elements by Column for (int column = 0; column < matrix.length; column++) { int total = 0; for (int row = 0; row < matrix.length; row++) total += matrix[row][column]; System.out.println("Sum for column " + column + " is " + total); } © 2019 McGraw-Hill Education  OO Programming Concepts Object-oriented programming (O OP) involves programming using objects. An object represents an entity in the real world that can be distinctly identified. For example, a student, a desk, a circle, a button, and even a loan can all be viewed as objects. An object has a unique identity, state, and behaviors. The state of an object consists of a set of data fields (also known as properties) with their current values. The behavior of an object is defined by a set of methods. © 2019 McGraw-Hill Education  Objects Class Name: Circle A class template Data Fields: radius is _______ Methods: getArea Circle Object 1 Circle Object 2 Circle Object 3 Three objects of the Circle class Data Fields: Data Fields: Data Fields: radius is 10 radius is 25 radius is 125 An object has both a state and behavior. The state defines the object, and the behavior defines what the object does. © 2019 McGraw-Hill Education  Classes (1 of 2) Classes are constructs that define objects of the same type. A Java class uses variables to define data fields and methods to define behaviors. Additionally, a class provides a special type of methods, known as constructors, which are invoked to construct objects from the class. © 2019 McGraw-Hill Education  Classes (2 of 2) class Circle { double radius = 1.0; Data field Circle() { } Constructors Circle(double newRadius) { radius = newRadius; } double getArea() { Method return radius * radius * 3.14159; } } © 2019 McGraw-Hill Education  UML Class Diagram UML Class Diagram Circle Class name radius: double Data fields Circle() Constructors Circle(newRadius: double) and methods getArea(): double getPerimeter(): double setRadius(newRadius: double): void circle2: Circle circle3: Circle UML notation circle1: Circle for objects radius = 1.0 radius = 25 radius = 125 © 2019 McGraw-Hill Education  Example: Defining Classes and Creating Objects (1 of 2) Objective: Demonstrate creating objects, accessing data, and using methods. TestSimpleCircl e © 2019 McGraw-Hill Education  Example: Defining Classes and Creating Objects (2 of 2) TV TestTV © 2019 McGraw-Hill Education  Constructors (1 of 2) Circle() { } Circle(double newRadius) { radius = newRadius; } Constructors are a special kind of methods that are invoked to construct objects. © 2019 McGraw-Hill Education  Basic Graph Terminologies (1 of 2) What is a graph? G=(V, E) Define a graph Directed vs. undirected graphs Weighted vs. unweighted graphs Adjacent vertices Incident Degree Neighbor loop © 2019 McGraw-Hill Education  Directed vs Undirected Graph Peter Jane Cindy Mark Wendy © 2019 McGraw-Hill Education  Basic Graph Terminologies (2 of 2) Parallel edge Simple graph Complete graph Spanning tree A D A D B E B E C C © 2019 McGraw-Hill Education  Representing Graphs Representing Vertices Representing Edges: Edge Array Representing Edges: Edge Objects Representing Edges: Adjacency Matrices Representing Edges: Adjacency Lists © 2019 McGraw-Hill Education  Representing Vertices String[] vertices = {“Seattle“, “San Francisco“, “Los Angles”, “Denver”, “Kansas City”, “Chicago”, … }; City[] vertices = {city0, city1, … }; public class City { } List vertices; © 2019 McGraw-Hill Education  Representing Edges: Edge Array int[ ][ ] edges = {{0, 1}, {0, 3} {0, 5}, {1, 0}, {1, 2}, … }; © 2019 McGraw-Hill Education  Representing Edges: Edge Object public class Edge { int u, v; public Edge(int u, int v) { this.u = u; this.v = v; } List list = new ArrayList(); list.add(new Edge(0, 1)); list.add(new Edge(0, 3)); … © 2019 McGraw-Hill Education  Representing Edges: Adjacency Matrix int[][] adjacencyMatrix = { {0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // Seattle {1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, // San Francisco {0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // Los Angeles {1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, // Denver {0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0}, // Kansas City {1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0}, // Chicago {0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // Boston {0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0}, // New York {0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1}, // Atlanta {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // Miami {0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, // Dallas {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0} // Houston }; © 2019 McGraw-Hill Education  Representing Edges: Adjacency Vertex List List[ ] neighbors = new List; Seattle neighbors 1 3 5 San Francisco neighbors 0 2 3 Los Angeles neighbors 1 3 4 10 Denver neighbors 0 1 2 4 5 Kansas City neighbors 2 3 5 7 8 10 Chicago neighbors 0 3 4 6 7 Boston neighbors 5 7 New York neighbors 4 5 6 8 Atlanta neighbors 4 7 9 10 11 Miami neighbors 8 11 Dallas neighbors 2 4 8 11 Houston neighbors 8 9 10 List neighbors = new ArrayList(); © 2019 McGraw-Hill Education  Representing Edges: Adjacency Edge List List[ ] neighbors = new List; Seattle neighbors Edge(0, 1) Edge(0, 3) Edge(0, 5) San Francisco neighbors Edge(1, 0) Edge(1, 2) Edge(1, 3) Los Angeles neighbors Edge(2, 1) Edge(2, 3) Edge(2, 4) Edge(2, 10) Denver neighbors Edge(3, 0) Edge(3, 1) Edge(3, 2) Edge(3, 4) Edge(3, 5) Kansas City neighbors Edge(4, 2) Edge(4, 3) Edge(4, 5) Edge(4, 7) Edge(4, 8) Edge(4, 10) Chicago neighbors Edge(5, 0) Edge(5, 3) Edge(5, 4) Edge(5, 6) Edge(5, 7) Boston neighbors Edge(6, 5) Edge(6, 7) New York neighbors Edge(7, 4) Edge(7, 5) Edge(7, 6) Edge(7, 8) Atlanta neighbors Edge(8, 4) Edge(8, 7) Edge(8, 9) Edge(8, 10) Edge(8, 11) Miami neighbors Edge(9, 8) Edge(9, 11) Dallas neighbors Edge(10, 2) Edge(10, 4) Edge(10, 8) Edge(10, 11) Houston neighbors Edge(11, 8) Edge(11, 9) Edge(11, 10) © 2019 McGraw-Hill Education  Representing Adjacency Edge List Using ArrayList List neighbors = new ArrayList(); neighbors.add(new ArrayList()); neighbors.get(0).add(new Edge(0, 1)); neighbors.get(0).add(new Edge(0, 3)); neighbors.get(0).add(new Edge(0, 5)); neighbors.add(new ArrayList()); neighbors.get(1).add(new Edge(1, 0)); neighbors.get(1).add(new Edge(1, 2)); neighbors.get(1).add(new Edge(1, 3));...... neighbors.get(11).add(new Edge(11, 8)); neighbors.get(11).add(new Edge(11, 9)); neighbors.get(11).add(new Edge(11, 10)) © 2019 McGraw-Hill Education  Modeling Graphs Graph UnweightedGraph WeightedGraph © 2019 McGraw-Hill Education  Graph and UnweightedGraph «interface» The generic type V is the type for vertices. Graph +getSize(): int Returns the number of vertices in the graph. +getVertices(): List Returns the vertices in the graph. +getVertex(index: int): V Returns the vertex object for the specified vertex index. +getIndex(v: V): int Returns the index for the specified vertex. +getNeighbors(index: int): List Graph Returns the neighbors of vertex with the specified index. +getDegree(index: int): int Returns the degree for a specified vertex index. +printEdges(): void Prints the edges. +clear(): void Clears the graph. +addVertex(v: V): boolean Returns true if v is added to the graph. Returns false if v is already in the graph. UnweightedGra +addEdge(u: int, v: int): boolean Adds an edge from u to v to the graph throws IllegalArgumentException if u or v is invalid. Returns true if the edge is added and false if (u, v) is already in ph the graph. Adds an edge into the adjacency edge list. +addEdge(e: Edge): boolean +remove(v: V): boolean Removes a vertex from the graph. +remove(u: int, v: int): boolean Removes an edge from the graph. +dfs(v: int): UnWeightedGraph.SearchTree Obtains a depth-first search tree starting from v. +bfs(v: int): UnWeightedGraph.SearchTree Obtains a breadth-first search tree starting from v.. TestGrap UnweightedGraph #vertices: List Vertices in the graph. h #neighbors: List Neighbors for each vertex in the graph. +UnweightedGraph() Constructs an empty graph. +UnweightedGraph(vertices: V[], edges: Constructs a graph with the specified edges and vertices int[][]) stored in arrays. +UnweightedGraph(vertices: List, Constructs a graph with the specified edges and vertices edges: List) stored in lists. +UnweightedGraph(edges: int[][], Constructs a graph with the specified edges in an array numberOfVertices: int) and the integer vertices 1, 2,.... +UnweightedGraph(edges: List, Constructs a graph with the specified edges in a list and numberOfVertices: int) the integer vertices 1, 2, …. © 2019 McGraw-Hill Education  Graph Visualization GraphVie Displayabl DisplayUSMa w e p © 2019 McGraw-Hill Education  Graph Traversals Depth-first search and breadth-first search Both traversals result in a spanning tree, which can be modeled using a class. UnweightedGraph.SearchTree -root: int The root of the tree. -parent: int[] The parents of the vertices. -searchOrder: List The orders for traversing the vertices. +SearchTree(root: int, parent: Constructs a tree with the specified root, parent, and int[], searchOrder: List) searchOrder. +getRoot(): int Returns the root of the tree. +getSearchOrder(): List Returns the order of vertices searched. +getParent(index: int): int Returns the parent for the specified vertex index. +getNumberOfVerticesFound(): int Returns the number of vertices searched. +getPath(index: int): List Returns a list of vertices from the specified vertex index to the root. +printPath(index: int): void Displays a path from the root to the specified vertex. +printTree(): void Displays tree with the root and all edges. © 2019 McGraw-Hill Education  Depth-First Search The depth-first search of a graph is like the depth-first search of a tree discussed in §25.2.3, “Tree Traversal.” In the case of a tree, the search starts from the root. In a graph, the search can start from any vertex. Input: G = (V, E) and a starting vertex v Output: a DFS tree rooted at v Tree dfs(vertex v) { visit v; for each neighbor w of v if (w has not been visited) { set v as the parent for w; dfs(w); } } © 2019 McGraw-Hill Education  Depth-First Search Example (1 of 2) © 2019 McGraw-Hill Education  Depth-First Search Example (2 of 2) Seattle 2097 Boston 983 Chicago 1331 214 807 1003 New York 787 Denver 533 1267 1260 599 888 San Francisco 1015 Kansas City 381 1663 864 496 Los Angeles 1435 Atlanta 781 810 Dallas 661 239 Houston 1187 Miami TestDF S © 2019 McGraw-Hill Education  Applications of the DFS Detecting whether a graph is connected. Search the graph starting from any vertex. If the number of vertices searched is the same as the number of vertices in the graph, the graph is connected. Otherwise, the graph is not connected. Detecting whether there is a path between two vertices. Finding a path between two vertices. Finding all connected components. A connected component is a maximal connected subgraph in which every pair of vertices are connected by a path. Detecting whether there is a cycle in the graph. Finding a cycle in the graph. © 2019 McGraw-Hill Education  The Connected Circles Problem ConnectedCircle s © 2019 McGraw-Hill Education  Breadth-First Search The breadth-first traversal of a graph is like the breadth-first traversal of a tree discussed in §25.2.3, “Tree Traversal.” With breadth-first traversal of a tree, the nodes are visited level by level. First the root is visited, then all the children of the root, then the grandchildren of the root from left to right, and so on. © 2019 McGraw-Hill Education  Breadth-First Search Algorithm Input: G = (V, E) and a starting vertex v Output: a BFS tree rooted at v bfs(vertex v) { create an empty queue for storing vertices to be visited; add v into the queue; mark v visited; while the queue is not empty { dequeue a vertex, say u, from the queue process u; for each neighbor w of u if w has not been visited { add w into the queue; set u as the parent for w; mark w visited; } } } © 2019 McGraw-Hill Education  Breadth-First Search Example (1 of 2) Queue: isVisited = 0 true Queue: 1 2 isVisited = true, isVisited = true, 3 isVisited = true Queue: 2 3 isVisited = 4 true © 2019 McGraw-Hill Education  Breadth-First Search Example (2 of 2) Seattle 2097 Boston 983 Chicago 1331 214 807 1003 New York 787 Denver 533 1267 1260 599 888 San Francisco 1015 Kansas City 381 1663 864 496 Los Angeles 1435 Atlanta 781 810 Dallas 661 239 Houston 1187 Miami TestBFS © 2019 McGraw-Hill Education  Applications of the BFS Detecting whether a graph is connected. A graph is connected if there is a path between any two vertices in the graph. Detecting whether there is a path between two vertices. Finding a shortest path between two vertices. You can prove that the path between the root and any node in the BFS tree is the shortest path between the root and the node. Finding all connected components. A connected component is a maximal connected subgraph in which every pair of vertices are connected by a path. Detecting whether there is a cycle in the graph. Finding a cycle in the graph. Testing whether a graph is bipartite. A graph is bipartite if the vertices of the graph can be divided into two disjoint sets such that no edges exist between vertices in the same set. © 2019 McGraw-Hill Education  Introduction to Java Programming and Data Structures Twelfth Edition Chapter 29 Weighted Graphs and Applications Copyright © 2020 Pearson Education, Inc. All Rights Reserved © 2019 McGraw-Hill Education  Objectives 29.1 To represent weighted edges using adjacency matrices and adjacency lists (§29.2). 29.2 To model weighted graphs using the WeightedGraph class that extends the AbstractGraph class (§29.3). 29.3 To design and implement the algorithm for finding a minimum spanning tree (§29.4). © 2019 McGraw-Hill Education  Weighted Graph Animation https://liveexample.pearsoncmg.com/dsanimation/WeightedGr aphLearningTooleBook.html © 2019 McGraw-Hill Education  Representing Weighted Graphs Representing Weighted Edges: Edge Array Weighted Adjacency Matrices Adjacency Lists © 2019 McGraw-Hill Education  Representing Weighted Edges: Edge Array (1 of 2) int[][] edges = {{0, 1, 2}, {0, 3, 8}, {1, 0, 2}, {1, 2, 7}, {1, 3, 3}, {2, 1, 7}, {2, 3, 4}, {2, 4, 5}, {3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6}, {4, 2, 5}, {4, 3, 6} }; © 2019 McGraw-Hill Education  Representing Weighted Edges: Edge Array (2 of 2) 0 1 2 3 4 Integer[][] adjacencyMatrix = { 0 null 2 2 null 8 null {null, 2, null, 8, null }, 1 2 3 null 7 3 null {2, null, 7, 3, null }, 2 null 4 7 null 4 5 {null, 7, null, 4, 5}, 3 8 3 4 null 6 {8, 3, 4, null, 6}, {null, null, 5, 6, null} 4 null null 5 6 null }; © 2019 McGraw-Hill Education  Edge Adjacency Lists (1 of 2) java.util.List[] neighbors = new java.util.List; neighbors WeightedEdge(0, 1, 2) WeightedEdge(0, 3, 8) neighbors WeightedEdge(1, 0, 2) WeightedEdge(1, 3, 3) WeightedEdge(1, 2, 7) neighbors WeightedEdge(2, 3, 4) WeightedEdge(2, 4, 5) WeightedEdge(2, 1, 7) neighbors WeightedEdge(3, 1, 3) WeightedEdge(3, 2, 4) WeightedEdge(3, 4, 6) WeightedEdge(3, 0, 8) neighbors WeightedEdge(4, 2, 5) WeightedEdge(4, 3, 6) WeightedEdg e © 2019 McGraw-Hill Education  Edge Adjacency Lists (2 of 2) For flexibility, we will use an array list rather than a fixed-sized array to represent list as follows: List list = new java.util.ArrayList(); © 2019 McGraw-Hill Education  WeightedGraph UnweigtedGraph Defined in Figure 28.9. WeightedGraph +WeightedGraph() Constructs an empty graph. +WeightedGraph(vertices: V[], edges: int[][]) Constructs a weighted graph with the specified edges and the number of vertices in arrays. +WeightedGraph(vertices: List, edges: Constructs a weighted graph with the specified edges and the List) number of vertices. +WeightedGraph(edges: int[][], Constructs a weighted graph with the specified edges in an array numberOfVertices: int) and the number of vertices. +WeightedGraph(edges: List, Constructs a weighted graph with the specified edges in a list numberOfVertices: int) and the number of vertices. +printWeightedEdges(): void Displays all edges and weights. +getWeight(int u, int v): double Returns the weight on the edge from u to v. Throw an exception if the edge does not exist. +addEdge(u: int, v: int, weight: double): void Adds a weighted edge to the graph and throws an IllegalArgumentException if u, v, or w is invalid. If (u, v) is already in the graph, the new weight is set. +getMinimumSpanningTree(): MST Returns a minimum spanning tree starting from vertex 0. +getMinimumSpanningTree(index: int): MST Returns a minimum spanning tree starting from vertex v. +getShortestPath(index: int): ShortestPathTree Returns all single-source shortest paths. WeightedGrap TestWeightedGrap h h © 2019 McGraw-Hill Education  Minimum Spanning Trees A graph may have many spanning trees. Suppose that the edges are weighted. A minimum spanning tree is a spanning tree with the minimum total weights. For example, the trees in Figures (b), (c), (d) are spanning trees for the graph in Figure (a). The trees in Figures (c) and (d) are minimum spanning trees. Total w: 10 (a 6 7 10 5 8 5 ) 8 42 10 5 7 (b) 7 8 5 7 7 8 12 Total w: Total w: 38 38 (c 6 7 5 (d) 6 ) 5 5 7 8 5 7 7 8 © 2019 McGraw-Hill Education  Prim’s Minimum Spanning Tree Algorithm Input: G = (V, E) with non-negative weights. Output: a MST MST minimumSpanningTree() { Let V denote the set of vertices in the Find a vertex V–T graph; in that has the Let T be a set for the vertices in the spanning tree; smallest weighted Initially, add the starting vertex to T; edge connecting to a vertex in T. while (size of T < n) { find v in T and u V – T with the in weight on the edge (u, v), smallest as shown in the figure; add u to T; } } © 2019 McGraw-Hill Education  Minimum Spanning Tree Algorithm Vertices already in Vertices not currently in V - T the spanning tree the spanning tree T u v © 2019 McGraw-Hill Education  Minimum Spanning Tree Algorithm Example (1 of 6) © 2019 McGraw-Hill Education  Minimum Spanning Tree Algorithm Example (2 of 6) © 2019 McGraw-Hill Education  Minimum Spanning Tree Algorithm Example (3 of 6) © 2019 McGraw-Hill Education  Minimum Spanning Tree Algorithm Example (4 of 6) © 2019 McGraw-Hill Education  Minimum Spanning Tree Algorithm Example (5 of 6) © 2019 McGraw-Hill Education  Minimum Spanning Tree Algorithm Example (6 of 6) © 2019 McGraw-Hill Education D LIST © 2019 McGraw-Hill Education nt.. © 2019 McGraw-Hill Education move © 2019 McGraw-Hill Education sert © 2019 McGraw-Hill Education s for List Nodes public class Node { // Instance variables: private Object element; private Node next; public Node() { this(null, null); } public Node(Object e, Node n) { element = e; next = n; } // Accessor methods: public Object getElement() { return element; } public Node getNext() { return next; } // Modifier methods: public void setElement(Object newElem) { element = newElem; } public void setNext(Node newNext) { next = newNext; } } © 2019 McGraw-Hill Education  class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; } } © 2019 McGraw-Hill Education  public class LinkedListTraversal { public static void main(String[] args) { // Create a linked list Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); // Traverse and print the linked list traverse(head); } © 2019 McGraw-Hill Education  public static void traverse(Node head) { Node current = head; while (current != null) { System.out.println(current.data); current = current.next; } } } © 2019 McGraw-Hill Education at the Head 1. Allocate a new node 2. Insert new element 3. Have new node point to old head 4. Update head to point to new node © 2019 McGraw-Hill Education  Removing at the Head 1. Update head to point to next node in the list 2. Allow garbage collector to reclaim the former first node © 2019 McGraw-Hill Education  Inserting at the Tail 1. Allocate a new node 2. Insert new element 3. Have new node point to null 4. Have old last node point to new node 5. Update tail to point to new © 2019 McGraw-Hill Education ADT (§4.2) The Stack ADT stores Auxiliary stack arbitrary objects operations: Insertions and deletions – object top(): returns follow the last-in first- the last inserted out scheme element without Think of a spring- removing it loaded plate dispenser – integer size(): returns Main stack operations: the number of elements stored – push(object): inserts an – boolean isEmpty(): element – object pop(): removes indicates whether no and returns the last elements are stored inserted element © 2019 McGraw-Hill Education face in Java Java interface public interface Stack { corresponding to public int size(); our Stack ADT public boolean isEmpty(); Requires the public Object top() definition of throws EmptyStackException; class EmptyStackException public void push(Object o); Different from public Object pop() the built-in Java throws EmptyStackException; class java.util.Stack } © 2019 McGraw-Hill Education ptions Attempting the In the Stack ADT, execution of an operations pop operation of ADT and top cannot be may sometimes performed if the cause an error stack is empty condition, called an Attempting the exception execution of pop Exceptions are said or top on an empty to be “thrown” by stack throws an an operation that EmptyStackExcepti cannot be executed on © 2019 McGraw-Hill Education  Stack Animation https://liveexample.pearsoncmg.com/dsanimation/S tackeBook.html © 2019 McGraw-Hill Education ns of Stacks © 2019 McGraw-Hill Education  Queues © 2004 Goodrich, Tamassia eue ADT © 2019 McGraw-Hill Education  ADT (§4.3) The Queue ADT stores Auxiliary queue arbitrary objects operations: Insertions and deletions – object front(): returns follow the first-in first-out the element at the front scheme without removing it Insertions are at the rear of – integer size(): returns the queue and removals are the number of elements stored at the front of the queue – boolean isEmpty(): Main queue operations: indicates whether no – enqueue(object): inserts an elements are stored element at the end of the Exceptions queue – object dequeue(): removes – Attempting the and returns the element at execution of dequeue or the front of the queue front on an empty queue throws an EmptyQueueException © 2019 McGraw-Hill Education Enqueue 1, 2, 3, 4 Dequeue FIFO 1 1 2 3 4 2 3 4 front back front back Queue © 2019 McGraw-Hill Education ementation © 2019 McGraw-Hill Education mple 5 2 7 1 front back Shows a queue in some intermediate state. © 2019 McGraw-Hill Education ations © 2019 McGraw-Hill Education  Initial back front Enqueue 1,2,3,4 1 2 3 4 front back Dequeue twice 3 4 front back © 2019 McGraw-Hill Education  Enqueue 7,8,9,10 3 4 7 8 9 10 front back Enqueue 11, 12 11 12 3 4 7 8 9 10 Queue is full back front Dequeue twice 11 12 7 8 9 10 back front © 2019 McGraw-Hill Education Example Operation Output Q enqueue(5) – (5) enqueue(3) – (5,3) dequeue() 5 (3) enqueue(7) – (3,7) dequeue() 3 (7) front() 7 (7) dequeue() 7 () dequeue() “error” () isEmpty() true () enqueue(9) – (9) enqueue(7) – (9,7) size() 2 (9,7) enqueue(3) – (9,7,3) enqueue(5) – (9,7,3,5) dequeue() 9 (7,3,5) © 2019 McGraw-Hill Education s of Queues © 2019 McGraw-Hill Education  Queues A queue represents a waiting list. A queue can be viewed as a special type of list, where the elements are inserted into the end (tail) of the queue, and are accessed and deleted from the beginning (head) of the queue. Data1 Data2 Data3 Data3 Data2 Data2 Data1 Data1 Data1 Data3 Data3 Data2 Data1 Data2 Data3 © 2019 McGraw-Hill Education  Queue Animation https://liveexample.pearsoncmg.com/dsanimation/Q ueueeBook.html © 2019 McGraw-Hill Education ed Queue Use an array of size N in a circular fashion Two variables keep track of the front and rear f index of the front element r index immediately past the rear element Array location r is kept empty normal configuration Q 0 1 2 f r wrapped-around configuration Q 0 1 2 r f © 2019 McGraw-Hill Education perations We use the Algorithm size() modulo return (N - f + r) mod N operator Algorithm isEmpty() (remainder of return (f = r) division) Q 0 1 2 f r Q 0 1 2 r f © 2019 McGraw-Hill Education ations (cont.) Operation enqueue Algorithm enqueue(o) throws an exception if size() = N  1 then if the array is full throw FullQueueException This exception is else implementation- Q[r]  o dependent r  (r + 1) mod N Q 0 1 2 f r Q 0 1 2 r f © 2019 McGraw-Hill Education ations (cont.) Operation Algorithm dequeue() dequeue throws if isEmpty() then an exception if the throw EmptyQueueException queue is empty else This exception is o  Q[f] specified in the f  (f + 1) mod N queue ADT return o Q 0 1 2 f r Q 0 1 2 r f © 2019 McGraw-Hill Education rface in Java Java interface public interface Queue { corresponding to public int size(); our Queue ADT public boolean isEmpty(); Requires the public Object front() definition of throws EmptyQueueException; class public void enqueue(Object o); EmptyQueueException public Object dequeue() No throws EmptyQueueException; corresponding } built-in Java class © 2019 McGraw-Hill Education s of Queues © 2019 McGraw-Hill Education  Application: Round Robin Schedulers We can implement a round robin scheduler using a queue, Q, by repeatedly performing the following steps: 1. e = Q.dequeue() 2. Service element e 3. Q.enqueue(e) The Queue 1. Deque the 2. Service the 3. Enqueue the next element next element serviced element Shared Service © 2019 McGraw-Hill Education