UC Berkeley – Computer Science
CS61B: Data Structures
Final, Spring 2018
This test has 12 questions worth a total of 400 points and is to be completed in 170 minutes. There is also an additional 30 point question that is part of midterm 2. The exam is closed book, except that you are allowed to use three double sided written cheat sheets (can use front and back on all 3 sheets). No calculators or other electronic devices are permitted. Give your answers and show your work in the space provided. Write the statement out below in the blank provided and sign. You may do this before the exam begins.
“I have neither given nor received any assistance in the taking of this exam.”
# 0 1 2 3 4 5 6
Points
# 17 448 339
46 10 011 13 12
37 13 (mt2)
TOTAL
Points
400 + 30
Signature: ___________________________
Name: __________________________
SID: ___________________________
Three-letter Login ID: _________
Login of Person to Left: _______
Login of Person to Right: ______
Exam Room: _____________________
32
24
24
40
55
51
30
Tips:
• • •
• •
• • •
Hint: Use Math.max instead of if statements to save space on coding problems.
There may be partial credit for incomplete answers.
There are a lot of problems on this exam. Work through the ones with which you are comfortable first. Do not get overly captivated by interesting design issues or complex corner cases you’re not sure about.
Not all information provided in a problem may be useful, and you may not need all lines. Unless otherwise stated, all given code on this exam should compile. All code has been compiled and executed before printing, but in the unlikely event that we do happen to catch any bugs in the exam, we’ll announce a fix. Unless we specifically give you the option, the correct answer is not ‘does not compile.’
○ indicates that only one circle should be filled in.
□ indicates that more than one box may be filled in.
For answers which involve filling in a ○ or □, please fill in the shape completely.
Optional. Mark along the line to show your feelings Before exam: [____________________☺]. on the spectrum betweenand☺. After exam: [____________________☺].
UC BERKELEY Login: _______
0. So it begins (1 point). Write your name and ID on the front page. Write the exam room. Write the IDs of your neighbors. Write the given statement and sign. Write your login in the corner of every page. Enjoy your free point☺.
1. Graph basics. a) (12 points). For the graph below, give the DFS preorder, DFS postorder, and BFS order using 61A as the source. Assume that DFS and BFS do not restart when they run out of vertices to process. You may not need all seven blanks. Assume that ties are broken in alphanumeric order (i.e. the edge 61A→61B would be considered before 61A→61C).
b) (4 points). Give a topological sort for all vertices in the graph from part a.
_____ _____ _____ _____ _____ _____ _____
c) (8 points). For the graph below, give the MST in the order that the edges are added by Prim’s algorithm starting at the top vertex (containing a circle), and the order added by Kruskal’s algorithm. Identify each edge with its weight, e.g. 0 refers to the edge at the top right of the image. You may not need all blanks.
DFS Preorder
_61A_ _____ _____ _____ _____ _____ _____
DFS Postorder
_____ _____ _____ _____ _____ _____ _____
BFS Order
_____ _____ _____ _____ _____ _____ _____
Edges in MST in order added by Prim’s __0__ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____
Edges in MST in order added by Kruskal’s _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____
2
CS61B FINAL, SPRING 2018
Login: _______
d) (4 points). For the graph from part c, do the edges of the MST change if we add 1000 to every edge weight? Do not worry about edge order.
○Yes ○No
e) (8 points). For the graph below, let x be the unknown weight of edge DE. Can the marked edges (in
bold) be a valid minimum spanning tree? If so, for what values of x? If not, why not?
○Valid MST, range of valid x: ___________________
○ Never a valid MST, because: _________________________ _____________________________________________________________
f) (8 points). For the graph below (same as part e), can the marked edges (in bold) be a shortest paths tree rooted at B? If so, for what values of x? If not, why not?
○ Valid SPT rooted in B, range of valid x: __________
○ Never a valid SPT rooted in B, because: __________ _____________________________________________________________
3
UC BERKELEY Login: _______
2. Sorting.
a) (8 points). Suppose that we have an initial array of unsorted symbols: [@, #, $, %, &, *], where no two symbols are considered equal. Suppose that we are in the middle of insertion sort and have reached the state where the array contains [&, #, $, @, %, *].
Mark each of the following propositions as true, false, or not enough information (NEI).
○T ○F ○NEI ○T ○F ○NEI ○T ○F ○NEI ○T ○F ○NEI
& is the smallest element of the array. * is the largest element of the array. &<#
%<@
b) (8 points). Suppose we have the array [6, 1, 4, 7, 3, 2, 5, 8]. Suppose we use 6 as the pivot, and partition using Tony Hoare’s partitioning scheme.
Give the array immediately after the first swap: ______________________
Give the array after the entire partition operation is complete: _______________________
c) (6 points). Given an array, suppose that x < y, and that x appears to the right of y. What happens to the inversion count if we swap x and y? Fill in completely all boxes that are possible.
□ It can decrease. □ It can increase. □ It can stay the same.
d) (6 points). What happens to the inversion count if we min-heapify an array using bottom up
heapification? Fill in all that are possible.
□ It can decrease. □ It can increase. □ It can stay the same.
e) (5 points). A 61B student studying for his final observes that the time for the get operation in a hash table is constant, so long as the items in a hash table are evenly distributed. Inspired, the student proposes a sort called HashSort that works very simply: the HashSort class contains a single instance variable HashMap
The student notes that this would take infinite memory to store all possible arrays, but claims that if you somehow had infinite memory, the algorithm would have constant runtime for an input array of length N. Is the student correct that HashSort is constant time? If yes, explain why the puppy, cat, dog bound does not apply. If not, explain why the student is wrong.
○ Yes / ○ No. Explanation: _______________________________________________
4
CS61B FINAL, SPRING 2018
Login: _______
3. Back to the First Half of the Semester.
a) (16 points). Given two IntLists defined as follows, fill in the append method below so that it non- destructively creates a new IntList with y appended to the end of x. For example, if x is 3 → 4 → 5, and y is 9→10→11, then the result should be 3→4→5→9→10→11. You may not need all lines.
public class IntList {
public int first;
public IntList rest;
public IntList(int f, IntList r) { first = f; rest = r; }
public static IntList append(IntList x, IntList y) { if (_____________________) {
} }
_________________;
} else {
_____________________________________________________
_____________________________________________________
}
b) (16 points). Suppose we modify our IntList class so that it can be iterated over. Fill in the code below so that iteration works correctly. You do not need to complete part a correctly to do this problem. You may not need all lines.
public class IntList implements Iterable
… // same as in part a
@Override
public Iterator
return ___________________________________________;
}
public static class IntListIterator implements Iterator
____________________________________________________________
}
public boolean hasNext() {
return __________________________________________________
}
public Integer next() {
} }
}
___________________________________________________________
___________________________________________________________
___________________________________________________________
5
UC BERKELEY Login: _______
c) (6 points). Suppose we have an IntList from part b called L. There are three ways to iterate over L, shown below. Assume that print is a method that simply calls System.out.print.
for (int x : L) {
print(x);
}
Iterator
= L.iterator();
while (it.hasNext()) {
print(it.next());
}
IntListIterator it =
(IntListIterator)
L.iterator();
while (it.hasNext()) {
print(it.next());
}
One.java Two.java Three.java
Suppose we changed our IntListIterator class in IntList from public to private. For each of our four files, what happens? Fill in one bubble per line.
IntList.java: One.java: Two.java: Three.java:
○Fails to compile ○ Compiles
○Fails to compile ○ Compiles but works incorrectly ○ Compiles and works correctly ○Fails to compile ○ Compiles but works incorrectly ○ Compiles and works correctly ○Fails to compile ○ Compiles but works incorrectly ○ Compiles and works correctly
d) (8 points). Suppose we have a software system that makes a huge number of calls to a very large ArrayList
In terms of practical runtime and space usage, would we expect our IntArrayList to perform better, almost exactly the same, or worse?
Runtime of IntArrayList: ○ Better ○ No measurable difference ○ Worse
Brief justification for your answer: ______________________________________________________
Space usage of IntArrayList: ○ Better ○ No measurable difference ○ Worse
Brief justification for your answer: ______________________________________________________ 4. PNH (0 points). When was the oldest surviving film recorded? Name something that happens in it.
6
CS61B FINAL, SPRING 2018
Login: _______
5. Hash Codes (13 points). Suppose we have the class defined below.
public class SneakySnake {
public static final String UUIDString = “64de13c7fc79154d0570a12f268df”; private int seed;
public Random random;
public SneakySnake(int s) { seed = s; random = new Random(seed); }
@Override
public boolean equals(Object other) {
SneakySnake o = (SneakySnake) other;
return this.UUIDString.equals(o.UUIDString) && this.seed == o.seed;
}
@Override
public int hashCode() {
… }
}
For each of the hashCode() implementations below, fill in whether the implementation is valid, valid but slow, or invalid. A hashcode is valid if the methods of a hash table implementation (e.g. HashSet) always return the correct results. A hashcode is considered “valid but slow” if hash table operations are guaranteed to be correct, but are asymptotically much slower than otherwise possible with a better hash code. A hashcode is invalid if the code either doesn’t compile, or some operations don’t work as expected.
hashCode() implementation
return UUIDString;
return UUIDString.hashCode(); return seed;
return random.nextInt();
Random hashcodeRand = new Random(10);
return hashcodeRand.nextInt();
valid valid but slow
invalid
○ ○ ○
○ ○ ○
○ ○ ○
○ ○ ○
○ ○ ○
Small Area of Total Peace and Tranquility. Please, enjoy your stay.
7
UC BERKELEY Login: _______
6. More Graphs! As usual, throughout this problem, assume that our graphs have no edges that connect a node to itself, and that there is at most one edge between any two nodes.
a) (25 points). For each of the following propositions about graphs, mark Always True, Sometimes True, or Always False.
○AT ○ST ○AF ○AT ○ST ○AF
○AT ○ST ○AF ○AT ○ST ○AF ○AT ○ST ○AF
○AT ○ST ○AF
A* finds a correct shortest path (if it exists) from a source vertex to the goal vertex.
Suppose we have a goal node in mind. BFS finds a correct shortest path (if it exists) from a source vertex to that goal vertex in an unweighted graph.
The MST of a graph contains the largest edge in a graph.
Given a valid topological sort, the last vertex has no outgoing edges.
The middle vertex in a topological sort of 3 or more vertices has no edge going into it.
Given a graph with all positive edges except one or more negative edges leaving the start node, Dijkstra’s algorithm finds a correct shortest paths tree.
○AT ○ST ○AF
Consider a variant of Dijkstra’s algorithm DAV1 that tries to find a target node and stops as soon as the target node is enqueued. DAV1 finds a correct shortest path to the target on a graph with no negative edges.
○AT ○ST ○AF
Consider a variant of Dijkstra’s algorithm DAV2 that tries to find a target node and stops as soon as the target node is dequeued. DAV2 finds a correct shortest path to the target on a graph with no negative edges.
b) (12 points). For this problem, consider only graphs with non-negative edge weights.
Naively, you’d assume that storing the shortest paths from a start vertex to every other vertex would require storing V – 1 lists, one for each target vertex, requiring O(V2) space. However, we proved in lecture that the shortest paths actually form a tree, allowing us to store a single “shortest paths tree” in O(V) space.
Suppose that we instead want to store the second shortest paths from a start vertex to every other vertex for which a second shortest path exists. Do the resulting edges form a tree? If yes, explain why. If not, give a counter-example.
○ Yes, there exists some sort of second-shortest-paths-tree because: _______________________ _______________________________________________________________________________
○ No, because (include drawing with no more than 5 nodes):
8
CS61B FINAL, SPRING 2018
Login: _______
7. Can you do that? For each of the following problems, select Yes and provide an explanation OR select No and provide a counterexample (for full credit) or an explanation (for partial credit).
a) (10 points). One way to implement insertion sort as described in class is to call travel(0), travel(1), travel(2), …, travel(N-1), in that order, where travel(i) is a helper function where the chosen item swaps itself with its left neighbor repeatedly as long as its left neighbor is greater than it. In other words, each item is the traveler exactly once, and traveling means heading as close to the front as possible. Suppose that we instead call travel in the reverse order, e.g. travel(N-1), travel(N-2), …, travel(0). Does this also work? Assume that the travel operation is exactly as above. If yes, explain why. If no, give a counter-example.
○ Yes, because: ______________________________________________________________
○ No, counter-example: ________________________________________________________
b. (12 points). Consider a new MST algorithm: Pruskal’s Algorithm. For Pruskal’s algorithm, we assume a connected weighted undirected graph. The algorithm is the following: Create a Set
○ Yes, because: ______________________________________________________________ ○ No, counter-example (no more than 5 nodes):
c. (10 points). Suppose we want to create a new class called MutationSafeHeapMinPQ.
public class MutationSafeHeapMinPQ
public void add(K item) { … }
public K min() { … }
public K removeMin() { … } }
The only difference between this and the HeapMinPQ from lecture is that our new class’s reporting methods (min and removeMin) must always return the correct result, even if previously added items in the priority queue are modified. In other words, it handles mutable objects perfectly fine, even if they change while in the PQ.
Is it possible to implement such a class? If so, briefly describe how. If not, explain why not. Don’t worry about runtime.
○Yes: _______________________________________________________________________
○ No, because: ________________________________________________________________
9
UC BERKELEY Login: _______
8. Weird Sorts.
a) (12 points). Suppose we create a new sorting algorithm called PartitionHybridSort(input, lo, hi, subsort) where input is an input array of integers, lo is the lowest index in the array to be sorted, hi is the highest index in the array to be sorted, and subsort is the sorting routine to use in step 3:
1. If hi – lo <= 1, return.
2. Partition around input[lo] (i.e. the leftmost item of the current subproblem). 3. Use subsort to sort the left and right subproblems.
Give the worst case runtime for the function calls below. Give your answer as a function of only N in big theta notation. Each represents a different choice of subsort. For example, InsertionSort is a reference to an insertion sort implementation for integer arrays.
PartitionHybridSort(input, 0, N, InsertionSort)
PartitionHybridSort(input, 0, N, Mergesort)
PartitionHybridSort(input, 0, N, LSDSort)
PartitionHybridSort(input, 0, N, PartitionHybridSort)
Θ(_____________)
Θ(_____________) Θ(_____________) Θ(_____________)
b) (12 points). In lecture, our implementation of LSD sort used counting sort as subroutine to sort by each digit. Suppose that we used Mergesort as a subroutine instead of counting sort. Let’s call this new algorithm LSDMergesort.
The Mergesort used as a subroutine by LSDMergesort is exactly like regular Mergesort, except that its merge operation compares only one digit of an input to decide which is larger. For example, the merge operation would ordinarily consider 361 to be less than 410, but if we’re sorting on the final digit, it will consider 361 to be larger than 430 (since 1 > 0).
Just like regular LSD sort, LSDMergesort would sort by the last digit, then second to last digit, and so forth. We can define LSDQuicksort in a similar way. Assume our LSDQuicksort uses shuffling, always picks the leftmost pivot, and uses Tony Hoare’s partitioning scheme.
For each of these two new sorts, give their worst case runtime in terms of N and W, where W is the number of digits in each key. For simplicity, assume all keys have the same number of digits. Don’t worry about the alphabet size R. Also state whether or not they always return the right answer, and give an explanation for why.
Worst case
runtime LSDMergesort Θ(__________) LSDQuickSort Θ(__________)
Always works correctly? ○Yes ○No ○Yes ○No
Explanation for why it always works or not.
10
CS61B FINAL, SPRING 2018
Login: _______
9. Dijkstra’s Runtime (24 points). In lecture, our cost model for Dijkstra’s algorithm was to count the number of add, changePriority, and removeMin calls. We showed that we make V calls to add, O(E) calls to changePriority, and O(V) removeMin calls. Using a binary heap-based PQ that allows priority updates and can handle all three operations in O(log V) time, Dijkstra’s algorithm therefore requires O(E log V + V log V) time.
For each of the priority queue implementations below, give a tight asymptotic runtime bound for each add, changePriority and removeMin operation, and also provide the total runtime for Dijkstra’s algorithm. Assume that our graph has vertices numbered from 0 to V – 1.
The approaches to consider are:
1. TrinaryMinHeapPQ: Exactly the same as the PQ used in lecture (and described above), except that nodes can have up to 3 children instead of 2.
2. UnorderedArrayPQ: The PQ is a Double[] array. The ith entry in the array holds the priority value of the ith vertex stored as a Double. Any vertices that have been removed have a null value. Adding a new vertex increases the size of the array by 1.
3. OrderedLinkedListPQ: Each node in the linked list holds a vertex number and a priority value as a double. Items are stored in increasing order of priority.
Give your answers in terms of E and V. Do not simplify expressions involving E and V, e.g. don’t simplify O(E log V + V log V) into O(E log V).
add changePriority removeMin
Total runtime
TrinaryMinHeapPQ UnorderedArrayPQ OrderedLinkedListPQ
O( )O( )O( ) O() O()O() O() O()O() O() O()O()
10. By the Numbers (40 points).
Give the best and worst case number of compareTo calls needed for each task below. Give exact values! Do not include calls to equals, usages of primitive comparison operators, etc. The answer fomay be zero.
Best Worst
_____ _____ Solving puppy, cat, dog for N = 3.
_____ _____ Insertion sorting 5 numbers.
_____ _____ Inserting 5 numbers into an initially empty binary search tree.
_____ _____ Finding the successor (smallest item larger than) the root in a BST with 7 items. _____ _____ Merging a sorted array of size 20 with a sorted array of size 30 to yield a sorted result. _____ _____ Bottom up heapification of an array of 7 items.
_____ _____ Binary searching an ordered array of 7 numbers for a key.
_____ _____ Using counting sort to sort 52 cards by suit (heart, diamond, spade, club).
11
UC BERKELEY Login: _______
11. Sheep Herding. You are a shepherd and have found your way to the heart of Grigometh’s maze. Your prize awaits: a line of golden sheep stands before you. You may take as many as you wish, as long as you follow the rules. Your goal is to take the sheep with the greatest total value. The rules are:
1. You must take the first sheep.
2. Walk forward between A and B spots, inclusive. If there are no sheep left, you are done. Otherwise, repeat step 1, where the sheep you just walked to is the new first sheep.
Four examples follow:
• values={1,0,1,-1,1,0,10},A=2,B=3,best=13
• values={0,2},A=2,B=3,best=0
• values={5,2,-3,2,2,10,5,3,3,4},A=3,B=5,best=19 • values={2,1,-3,6,8,-2,-1,4},A=2,B=3,best=11
Throughout this problem, assume that the correct answer is always small enough to fit into an integer, and that B ≥ A > 0. Note that A cannot be zero, otherwise we could keep picking the same sheep.
a) (8 points). To test your understanding, suppose we have values = {5, 2, -3, 2, 2, 10}, A = 2,andB = 3, computebest.
best: ______________
b. (20 points). Fill in the naive recursive solution below.
public static int maxSheepNaive(int[] values, int A, int B) { return maxSheepNaiveHelper(values, A, B, 0);
}
/** Returns the max value if we take sheep with values[c] as well as the
* subsequent sheep(s) with maximum total value according to the rules. */
public static int maxSheepNaiveHelper(int[] values, int A, int B, int c) { if (___________________) {
______________________________
}
int best = _____________;
for (int s = ___;__________________; s += 1) {
______________________ maxSheepNaiveHelper(____________________);
____________________________________________________
____________________________________________________
____________________________________________________
} // hint: For particularly concise code, use Math.max somewhere.
return best;
}
12
CS61B FINAL, SPRING 2018
Login: _______
c) (20 points). Unfortunately, the solution from part b can be exponential in runtime. Memoization is one way to speed things up considerably, but an even better approach is to use dynamic programming. The tricky part is deciding what subproblems you need to solve.
Your goal: Come up with a useful subproblem definition such that Q(N) is the solution to each subproblem, and the solution to the entire problem can be easily calculated given all Q(N).
Describe your subproblem briefly in English, and fill in your values for Q(N) in the table given below. Hint if you’re stuck: Consider drawing a DAG, where an edge from i to j indicates that subproblem i is useful for solving subproblem j.
Description of Q(N) (optional, ungraded): ______________________________________ values = {2, 1, -3, 6, 8, -2, -1, 4}, A = 2, B = 3, best = 11
values[N] 2 1 -3 6 8 -2 -1 4 Q(N)
Note: Only your table values will be graded for part c! DAG drawing (optional, ungraded):
d) (7 points). Give the runtime of the dynamic programming solution in big Theta notation in terms of N, A, and B. You may not need all variables.
13
UC BERKELEY Login: _______
12. IntSibTree. During lecture, we talked about an alternate way of implementing a tree known as a sibling tree. In a sibling tree, each node stores an item, a link to its first child (if any), and a link to its first sibling (if any). For example, the abstract tree given on the left would be represented as the structure on the right. Here i means item, s means sibling, and c means child. For this problem, assume that our tree contains only non-negative integers!
a) (10 points). Fill in the largestSibling method in the IntSibTree class below. For example, if called on the node containing 2, the method would return 4. You may not need all lines.
public class IntSibTree {
public int item;
public IntSibTree sibling; // link to first sibling
public IntSibTree child; // link to first child
/** Returns largest item from siblings of t (including t) or 0 if null. */ public static int largestSibling(IntSibTree t) {
if (t == null) { return 0; }
____________________________________________________
____________________________________________________
____________________________________________________
}
public static int secondLargestSibling(IntSibTree t) { // code not shown } }
b) (13 points). Suppose we want to add a post order method to the IntSibTree class that performs a post order visit of the IntSibTree using the Visitor pattern from lecture. Fill in the method below. You may not need all lines. The Visitor interface is defined below the method.
public static void postOrder(IntSibTree t, Visitor v) {
if (t == null) { __________________ } // Note: postOrder is part of _____________________________________ // the IntSibTree class. _____________________________________ // For above graph, should visit _____________________________________ // in order 2, 7, 6, 4, 1, 3, 5.
}
public interface Visitor { // The Visitor interface is not public void visit(IntSibTree t); // part of the IntSibTree class.
}
14
CS61B FINAL, SPRING 2018
Login: _______
c) (28 points). Let the “max path” be the path that has the maximum total weight in the entire tree, where the weight of a path is defined as the sum of the integers along the path. For example, the max path for the tree on the left has weight 70, and the tree on the right has max path weight 110 (and doesn’t include the root). An empty tree has a max path weight of zero.
Fill in the MaxPathFinder class such that the code below prints the weight of the best path. Your visitor may be destructive, but is not required to be destructive. You may not need all lines.
THIS PROBLEM IS HARD. DON’T SPEND TOO LONG ON IT!
Visitor v = MaxPathFinder();
IntSibTree.postOrder(ist, v); //ist is some IntSibTree
System.out.println(v.result());//prints 70 for left example, 110 for right
public class MaxPathFinder implements Visitor { _________________________________
public MaxPathFinder() { ____________________________________________
}
public void visit(IntSibTree t) { _________________________________________________________________ _________________________________________________________________ _________________________________________________________________ _________________________________________________________________ _________________________________________________________________ _________________________________________________________________
}
public int result() {
____________________________________________
}
} // And now you’re done! Unless you want another crack at Flight…
15
UC BERKELEY Login: _______
13. (30 points). Flight Planning. This problem will be scored under two special rules:
1. Your score for this problem does not count towards your final exam score, but will instead be added to your score on problem 9 of midterm 2. If that total exceeds 30 points, the overflow is gold points.
2. If you fill in the bubble below, we’ll give you 10% credit instead of grading your answer.
○ I’ll just take 10% credit, please don’t grade my answer.
Consider the SNRPLTE (shortest no-repeats-path less than exists) method below. It returns true if there exists a path in the graph from s to t that:
1. Has total weight less than or equal to W.
2. Has no repeated vertices, i.e. each vertex appears at most once.
/** Returns true if there is a path from s to t in G with weight <= W. */ public static boolean SNRPLTE(Graph G, int s, int t, int W) { ... }
For example, SNRPLTE returns true on the graph to the right fors = 0, t = 2, and any value ofWthat is greater than or equal to 0. SNRPLTE handles undirected and directed edges.
Suppose that the runtime of SNRPLTE is Θ(F(V, E)), where F(V, E) is some unknown function that is Ω(V + E).
Given an undirected unweighted graph G, where each node is an airport, and each edge indicates that there exists a flight between the two airports, suppose we want to know if there exists a path that visits every airport exactly once, which we’ll call a world tour. In other words, you want to write the method below:
/** Returns true if there exists a world tour of the graph G. */
public static boolean WTE(Graph G) { ... } // G is unweighted and undirected
Give a concise but thorough explanation of how you could solve WTE for a given graph using SNRPLTE. Your algorithm must have runtime Θ(F(V, E)), i.e. the same as SNRPLTE. Give your algorithm as a numbered list of steps. You may not modify the SNRPLTE method in any way.
16