Introduction to Computer Science 2

CS 114: Introduction to Computer Science II John Tsai Engineer in Residence, Facebook Announcements Facebook Internships Facebook offers a 12-week software engineering internship each summer to undergraduate students. For more details or if you're interested in this opportunity for summer 2019, please reach out to me via email with a resume and a brief (2-sentence) statement of why you're interested. Programming Team I will be running competitive programming practices Thursdays 5-7pm starting today (Feb 14) in GITC 3710. This is excellent practice for interviews, and a lot of fun! Please sign up here: https://goo.gl/forms/gc1JQk8kmJhePIzy2 Instructor Meetings We have a little over two weeks until Midterm 1. Please schedule your meetings with me before then! Thanks to the ~45 of you who have done so already! Lecture 7: Big-O Notation Warmup (5 minutes) How would you group the following algorithms by running time: - Guess My Number - Linear search - Binary search - Max of list - Min of list - Mode of list Motivation Big-O notation, which we will discuss in this lecture, was developed as a way to measure the relative running time of algorithms in a way that is independent of the computing platform an algorithm is running on. public boolean linearSearch(int[] numbers, int k) { for (int i = 0; i < numbers.length; i++) { if (numbers[i] == k) { return true; } } return false; } Running Example: Linear Search • Determining Input Size • Counting Operations • Deﬁnition of Big-O • Classifying Algorithms Agenda • Determining Input Size • Counting Operations • Deﬁnition of Big-O • Classifying Algorithms Agenda public boolean linearSearch(int[] numbers, int k) { for (int i = 0; i < numbers.length; i++) { if (numbers[i] == k) { return true; } } return false; } Running Example: Linear Search • Determining Input Size • Counting Operations • Deﬁnition of Big-O • Classifying Algorithms Agenda We count all operations whose time is independent of the size of the input. Examples: Reading an element of an array, assigning a variable, adding/subtracting/multiplying/dividing, comparing values. For reasons we will soon see, this is somewhat arbitrary. Counting Operations public boolean linearSearch(int[] numbers, int k) { for (int i = 0; i < numbers.length; i++) { if (numbers[i] == k) { return true; } } return false; } Running Example: Linear Search • Determining Input Size • Counting Operations • Deﬁnition of Big-O • Classifying Algorithms Agenda

CS | 114 | Introduction to Computer Science 2 | lecture notes | CS 114: Introduction to Comput

pset05.pdf-CS 114: Introduction to Computer Science

but will instead operate on the assumption that there exist some really good ones. HashMaps support CRUD operations, just as our other data structures do. They are listed here, but to learn about additional methods, please read the Java documentation for the HashMap class at https://docs.oracle.com/javase/8/ docs/api/java/util/HashMap.html . • Create: This is done using the put() function, which allows you to insert a key-value pair. • Read: This is done using the get() function, which allows you to read the value of a given key. • Update: This is done using the put() function, which allows you to over- ride the current value in a key-value pair. • Delete: This is done using the remove() function, which removes a key from the map. All of the above operations run in constant time (assuming we use a good hash function, which is generally true in practice). 5 HashSets A HashSet is simply a degenerate version of a Map ; i.e. one without values. We explored HashSets earlier in the course, but at this point you should have a complete understanding of a HashSet’s inner workings. 6 Conclusion HashMaps and hashing are a fairly new but incredibly useful concept. As we saw earlier in the course, HashSets can greatly increase the performance of an algorithm; HashMaps do the same in a more ﬂexible way. Hashing and maps are used almost daily by software engineers and are tested extensively in interviews. In particular, the O ( n ) solutions of many interview problems involve these structures. 4

CS | 114 | Introduction to Computer Science 2 | lecture notes | but will instead operate on th

CS 114: Introduction to Computer Science II Lecture 16: CRUD & Lists John Tsai 4/1/19 (006); 4/2/19 (006) 1 Checkpoint At this point in the course, we have discussed a number of mathematical and coding basics, big-O notation, and sorting. We will now move on to Unit 4, in which we will study a number of data structures . So far, we know of two main data structures: arrays , which are ﬁxed-length ordered structures containing a number of Java primitives or objects, and sets , which are dynamic-length unordered structures containing a unique number of Java objects. From now until Midterm 2, we will explore several new data structures. 2 CRUD 2.1 Deﬁnition CRUD, in addition to being stuﬀ that one will ﬁnd on the streets of Manhattan, is a common software engineering pattern. It stands for “ C reate/ R ead/ U pdate/ D elete”. These are four very common operations that we will want to execute on each of our data structures. When I am designing software, I often keep these four operations in mind. For example, I used to work at a company that built a piece of software for “testing” in the retail industry. (Consider, for example, the idea of McDonald’s all-day breakfast. Something like this is not an obvious proﬁt-maker, and so what large chains often do is roll out these changes at a few stores and then compare their sales numbers to similar stores to see if the isolated change aﬀects proﬁts.) I spent some time designing a dashboard that listed all such analyses for a given client, and organizing the dashboard’s functionality by Create (create a new analysis or analyses), Read (ﬁnd all analyses that match given criteria), Up- date (change analysis parameters; run analyses), and Delete (remove analyses) helped me keep my thoughts clear and build an organized, extensible product. 1 2.2 CRUD in sets In a set, for example, we create elements using the .add() operation, read ele- ments using the .contains() operation, and delete elements using the .remove() operation. Updating an element of a set can be done by removing and adding. 2.3 CRUD in arrays In an array, we do not create or delete elements, since all of our slots are prede- ﬁned. We read elements using the array[i] notation, and we update elements using the array[i] = 5 notation. 3 Lists 3.1 Motivation In this class, we will explore the concept of a List . Like many software en- gineers, I have an unfortunate tendency to toss around the terms array and list interchangeably, but it is important to know what the distinction is. An array is a ﬁxed-width ordered data structure containing n elements; in other words, when we create an array, we cannot change its length. A list , however, is deﬁned in computer programming to mean a variable -width data structure that contains n elements but can be easily modiﬁed to contain more or less. 3.2 Deﬁnition List s in Java are interfaces , just like Set s. A List deﬁnes several methods, such as add() , get() , set() , and remove() , which correspond to the CRUD operations. There are several diﬀerent ways to implement a variable-width data structure that supports all of these operations, which is why Java deﬁnes a List as an interface and oﬀers several implementations of this interface. Please read the List documentation at https://docs.oracle.com/javase/8/docs/api/ java/util/List.html . 3.3 ArrayLists An ArrayList is a structure in which elements of the list are maintained in a Java array, which is increased in size as needed. Speciﬁcally, it maintains a property called capacity that increases as needed to ensure the ArrayList is big enough to hold all the items we put in it. In practice, programmers will generally assume that capacity is handled optimally without worrying about it, but capacity can be ﬁne-tuned using the methods provided in the ArrayList class. Please read the ArrayList documentation at https://docs.oracle. com/javase/8/docs/api/java/util/ArrayList.html . The performance of each of the key operations is noted below. 2

CS 114: Introduction to Computer Science II Midterm Exam 2 Review John Tsai April 18, 2019 Team Name: Round 1: 20 points (2 each) 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 1 Round 2: 20 points (2 each) 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 2 Round 3: 30 points (3 each) 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 3 Final Round You may gamble up to 30 points on this round. Points gambled: Answer: 4

All courses in CS

Popular Documents