# CS 61B

Time: Sat 10/27/17 2 pm (moved from Tue 10/24/17 10 am)

## Trees onto Heap & Priority Queues

Property of a min/max heap? Is it easier to find a min or a max item in a min heap? What'll be the best/worst height of a heap (if drawn like a tree) for n nodes? What are the procedures of adding an item to a tree or of removing an item from a tree? (The entry removal is a little more difficult.)

What's the result tree after removing the minimum from the following min heap `[0, 1, 4, 8, 2, 6, 8, 9]`?

A heap can be stored in an array--begin with index 0 or index 1?

Additionally, if possible, how can we use a min heap to implement a max heap?

## Bits

Assume integers are represented by 32 bits. If they are unsigned, how many distinct integers can be stored?

Think of a way to represent negative numbers. Does storing a sign bit by itself efficient when going into computation--4 different cases of adding numbers, whoa?! What's the number of distinct integers (signed) this can represent?

Check out two's complement--is this option a little bit easier, or not? Is the heavy math computation easier less troublesome without the various 4 cases? What's the range now? What's the min/max integer in two's complement, written in hexadecimal?

How do we negate an integer in two's complement?

There's a weird number within the range that the integer itself is its own negation.

Common bitwise operations: `&`, `|`, `~`, `^`, `<<`, `>>` and `>>>`.

## Hashing

There's quite a close relationship between `Object.equals()` and `Object.hashCode()`. What's a perfect hashing?

In a best/worst scenario, what's the runtime of inserting/finding an element in a hash set (with external linked list)?

Can this improved by tying to another data structure other than linked list?

## Generics

Why do we care using generics? What's a generic type parameter?

Generics have to be around classes; after all (pretty much) everything is just an object, like literally, with type erasure.

Practice

1. Will the following class compile?

``````public final class Algorithm {
public static <T> T max(T x, T y) {
return x > y ? x : y;
}
}``````
2. Write a generic method to exchange the positions of two different elements in an array.

``````public final class Algorithm {
public static <T> void swap(T[] a, int i, int j) {
/* Code here */
}
}``````
3. Will the following code compile?

``````public static void print(List<? extends Number> list) {
for (Number n : list)
System.out.print(n + " ");
System.out.println();
}``````
4. Given the following classes:

``````class Shape { /* ... */ }
class Circle extends Shape { /* ... */ }
class Rectangle extends Shape { /* ... */ }

class Node<T> { /* ... */ }``````

Will the following code compile? If not, why?

``````Node<Circle> nc = new Node<>();
Node<Shape> ns = nc;``````

Questions selected from The Java™ Tutorials: Questions and Exercises: Generics.