hschafer

In lecture, we talked about the idea of the binary search algorithm, but did not end up implementing it. This reading will look at the implementation for the algorithm since it's not uncommon to be asked to implement the code for this algorithm on an interview for a job involving programming. The end of the reading is a reference of the complexities of the operations we have learned so far

Binary Search

Review: Algorithm Idea

In lecture, we discussed how to search a sorted array for a value. The naive algorithm that just starts at the beginning and traverses to the end or until it finds the element. With the language we discussed in lecture, we would say that worst case this "linear search" would take O(n) time where n is the number of elements in the array.

We then discussed a smarter idea which divides the array in half repeatedly. Start by looking at the middle element of the array and compare it to the target value, there are three options

hschafer

Looping over Map objects

Imagine we have a Map<String, Double> that maps city names to their populations (in millions, from 2017 via Google via this source). We could imagine the following values being added to our Map

Map<String, Double> populations = new TreeMap<String, Double>();
populations.put("Seattle", 0.724);
populations.put("Los Angeles", 4.0);
populations.put("New York", 8.623);
populations.put("Chicago", 2.716);
populations.put("Philadelphia", 1.581);

hschafer

I'm a frayed you don't remember Strings

The next assignment deals with a lot of manipulations of Strings, so this example should help remind everyone how to work with Strings in their programs.

I want to write a method called dashes that takes a String and puts dashes between all the characters. If the given String is null, the method should throw an IllegalArgumentException. For example, the call

System.out.println(dashes("hello")); // Output: h-e-l-l-o

First attempt

hschafer

Remember that our goal for today's lecture and tomorrow's section is to get you practicing how to read recursive code and understand how it works. It's okay if the process of how to come up with a solution is still kind of hazy, since this is a skill that comes with practice; Thursday's section is all about getting you to solve problems recursively.

Working with Digits

When solving problems recursively, there are usually common patterns that show up in various types of problems depending on what type of data you're working with. In lecture with the writeStars example, we saw how to write something that could be written like a loop using recursion instead. In this example, we will work with an example that will show another common pattern: working with digits of a number.

Say we wanted to write a method called repeatDigits that takes a number n and returns the number that resulted from repeating each digit of n twice. For example repeatDigits(123) should return 112233 while `repeatDigit

hschafer

A recursive example of dashes

A quick review of an iterative dashes

If we recall from earlier in the quarter we implemented a method called dashes which took a String parameter and returned a new String that was equivalent to the given parameter with dashes inserted between every character. For example, a call to dashes("pupper") would return the String

"p-u-p-p-e-r"

Previously we implemented an iterative solution that looked something like this:

hschafer

In the next lecture, we will be discussing an extension of the Inheritance/Polymorphism topic that was introduced in 142 (or should have been introduced in your 142 equivalent course). My goal is you go into the next lecture being able to confidently solve the type of problem that would appear on a 142 exam like this practice problem.

If you do not feel like you remember the material to solve this type of problem, you should read the textbook chapter 9.1 or review the lecture slides or watch the Panopto recording from the 142 website from last quarter.

Below is a list of terminology you should be familar with and my walkthrough of the above problem.

Terminology

Inheritance is a way to form an is-a relationship between two classes. If you have a class called A and you write a new class public class B extends A, you are saying that B

hschafer

This is a document describing some of my best practices for studying for 143 exams. Obviously you might have different study habits that work best for you, but I wanted to share some general studying strategies to help you out.

Start studying early and often

Cramming technically helps you learn, but the learning is pretty shallow and quickly forgotten. It is far better to study a little bit every day rather than trying to fit all the studying into the late hours before the exam. It might be a bit more work, but the payoff is worth it!

Stay healthy

It's really easy to be overwhelmed with the stress of all your classes and put taking care of yourself on the back burner. This is not a good thing and you should still prioritize being healthy while studying for exams. Surprisingly, your brain is part of your body so keeping your body healthy keeps your brain healthy. This means making sure to stay hydrated, eat a balanced diet of things other than chips and Oreos, and maintain a normal sleep schedule.

It's

hschafer

IntTree contains

A common functionality for objects of binary tree classes and other classes that contain data is to see whether or not they contain a certain value. Let's give this functionality to objects of our IntTree class by implementing contains, which will return a boolean value depending on whether or not the given int value is in our IntTree. We start with the method stub

// This class represents a tree of integers
public class IntTree {
    private IntTreeNode overallRoot;
    
 //constructors and other methods

hschafer

Comparing based on boolean values

Imagine we have the following class which stores information about the environmental impact of a company. A shell of our class might look like

public class EnvImpact {
    private String companyName;
    private double emissions; // emissions emitted
    private int violations; // total violations committed
    
    // Can't just use emissions because 

hschafer

In this reading, we will learn about the last new data structure of the quarter!

I think you have some priority issues

Consider if you were writing software for a hospital to manage the waiting list of patients. Your system should be able to add new patients in to the waiting list and remove a patient that should be served next; both of these operations should be as efficient as possible. Why not use a Queue for this situation? Doesn't it efficiently implement add and remove (both in O(1) time)?

Well, this problem is a bit different than ones we've seen before because in real life, we don't really care about who showed up at the hospital first, but rather who is in the most urgent need for help. If we were to use a plain old Queue, we would be serving patients in a first-in-first-out (FIFO) manner; this means someone who stubbed their toe would be seen before someone with a life-threatening wound just because they showed up first, which does not seem right.

Instead, we would want a data structu