Computer Science CS50 Lecture Notes - Priority Queue, Binary Tree, Symbol Table

74 views12 pages

suryumg9

2 Jul 2022

School

Harvard University

Department

Computer Science

Course

Computer Science CS50

Professor

For unlimited access to Class Notes, a Class+ subscription is required.

Document Summary

Empty or node with links to left and right binary trees. Height of complete tree with n nodes is lg n . Array representation of a heap-ordered complete binary tree. Largest key is a[1], which is root of binary tree. Can use array indices to move through tree. Parent of node at k is at k/2. Children of node at k are at 2k and 2k+1. https://cs. ericyy. me/algorithms-1/week-4/index. html. Add node at end, then swim it up. 9 private void swim(int k) { while (k > 1 && less(k/2, k)) { exch(k, k/2); k = k/2; public void insert(key x) { pq[++n] = x; swim(n); Exchange root with node at end, then sink it down. 16 private void sink(int k) { while(2*k <= n) { int j = 2*k; if(j < n && less(j, j+1)) j++; if(!less(k, j)) break; exch(k, j); k = j; public key delmax() { Key max = pq[1]; exch(1, n-1); sink(1); pq[n+1] = null; return max; https://cs. ericyy. me/algorithms-1/week-4/index. html.

Related Questions

29. Consider the Cocktail Sort (code 4) algorithm described in the appendix. What is the fewest number of lines of code that would have to be added, removed, or changed in order for this algorithm to sort from largest to smallest? (A) Everything inside the second for loop. (B) 3 (C) 1 (D) 2 (E) Everything inside both for loops. Binary answers For the following questions you are to use your choices as they were the representation of a binary number. More precisely, A = 24, B = 23, C = 22, D = 21, and E = 20 position in a base 2 number. For example if you wanted to answer the number 23, you would translate it first as base 2 number, which is 10111, you would blacken A, C, D and E.2 Lets look at this process on your answer sheet, we have these 5 circle you can blacken. Normally you only pick one, here you might have to blacken more than one! @ ® © D ® Following the previous example, the answer we want to input is 23, its binary representation is 10111, hence the circle you would blacken are the following:

33. Base10 is the set of numbers created from the digits {0,1,2,3,4,5,6,7,8,9}. Whereas base2, which is the set of numbers created with {0,1}. We could similarly define base; as the ordered set of characters created from {X,Y,Z}. What is the following basez number, Yxz, in base ? Random graph For this section you will need to look at the classes Graph and GraphNode present in the appendix. A Graph consists of a number of nodes, each of which has connections to other nodes in the graph. You can think of nodes as a representation of a person in a social network (e.g. Facebook). The ArrayList connectedTo variable in GraphNodes is the list of friends that particular person has. For example, in the following graph, the node O is friends with node 1 and 2. On the other hand, node 2 and node 1 are not friends, hence the lack of link. 0-0 In the constructor of the Graph, the process of connecting nodes is randomized. Moreover, we will not allow a node to be connected to itself and we are going to assume that the arguments passed to the Graph constructor respect the following conditions: n > 2, and n > nbConnections. Pay close attention to the character order

8. Write a class called WordSet representing a set of String objects which can contain an arbitrary number of strings, limited only by the memory available to the Java Virtual Machine. A set is a collection of elements, however, unlike a list, a set cannot contain duplicate elements. Therefore, as its name implies, a WordSet object cannot contain duplicate Strings that is, if one attempts to da String to a Wordset, and the wordset already contains an element which is equal to this string, the attempt will fail and the state of the Wordset will not change. All String comparisons performed in the methods defined in the Wordset class are done in a Case SENSITIVE manner. Note that in the method descriptions below, the phrase "this Wordset" means "the Wordset on which the method in question is called." Your Wordset class MUST provide the following INSTANCE methods • A constructor, which takes no parameters and initializes the new Wordset ohject so that it contains no elements • A method called add(), which takes as its only parameter a string and returns a value of type boolean. If this Wordset already contains a string which is equal to the parameter string, or the parameter String is null, then the state of this Wordset does not change and the method return false; otherwise, the parameter String is added to this Wordset. and the method returns true. • A method called remove().which takes as its only parameter a string and returns a value of type boolean. If this wordSet contains a string which is equal to the parameter String this string is removed from the WordSet and the method returns true. On the other hand, if the string parameter is null or this Wordset does not contain a string which is equal to the parameter string, then the state of this wordset does not change, and the method return false. • A method called get.size(), which takes no parameters and returns the number of strings currently stored in this Wordset. This method MUST NOT change the state of this Wordset. • A method called isMember(). which takes as its only parameter a string and retumsa value of type boolean which is true if this wordset contains the parameter String false otherwise. If the parameter String is null, this method also return false. This method MUST NOT change the state of this wordset. • A method called computebirrerence().which takes as its only parameter a Wordset and returns a new Wordset representing the difference between this wordset and the parameter Wordset: in other words, the WordSet returned by this method contains all the strings that are in this wordset, but not in the parameter Wordset. If the parameter Wordset contains all the elements of this WordSet or this WordSet contains no elements, then this method returns a new Wordset containing no elements. Finally, if the parameter Wordset is null or contains ne strings, then this method returns a new wordset which contains all the elements of this wordset. This method MUST NOT change the state of this wordset or the parameter Wordset. • A method called tostring , which takes the parameters and turns a string which is the textual representation of this wordset. This textual representation consists of the concatena tion of the following clements - The String - The text representation of each clement in the WordSet; cach pair of adjacent clements is separated by the String", but this String MUST NOT appear before the first clement or after the last element - The String") The order in which the elements of this Wordset appear in the textual representation generated by the tostring() method does not matter. If the WordSet contains to Brings, then the textual representation returned by this method is ". Note that you MUST respect proper encapsulation practices that is, the attributes and methods of your class MUST be declared using the proper visibility modifier NINT Um an array list (of string) to keep track of the string stored in a wordt ob joot Is there a method defined in the Array loist class which determines whether in clementis already wored in an array ist, and which will do a case-sensitive comparison when liked on an Arraylint of strings? See the pages 24-26 of this examination for information about potentially useful methods defined by the ArrayList class WRITE YOUR Wordset CLASS IN THE SPACE BELOW:

Computer Science CS50 Lecture Notes - Priority Queue, Binary Tree, Symbol Table

Document Summary

Get access

Related Documents

Computer Science CS50 Lecture Notes - Linked List, Insertion Sort, Graham Scan

CSC263H1 Lecture Notes - Lecture 2: Longest Path Problem, Binary Tree, Heapsort

CMPT 225 Lecture Notes - Lecture 6: Binary Search Tree, Priority Queue, Binary Tree

Related Questions