Fundamentals

Question 1

default values of primitive numeric types

Answer 1

0 (page 84)

Question 2

default values of boolean types

Answer 2

false (page 84)

Question 3

default values of reference types

Answer 3

null

Question 4

default no-argument constructor default instance values

Answer 4

default equal primitive, boolean and reference default values (page 84)

Question 5

equality of reference variables

Answer 5

== tests whether or no they have the same identity: wether the references are equal. equals() tests whether the data-type values are the same and can be implemented by the client.

Question 6

Bags

Answer 6

A collection where removing items is not supported-its purpose is to provide clients with the ability to collect items and then to iterate through the collected items. Can also test if bag is empty and find its number of items. (Page 124)

Question 7

Dijkstra’s Two-Stack Algorithm

Answer 7

Push opera da onto the operand stack
Push operators onto the operator stack
Ignore left parentheses
For right parenthesis, pop an operator, pop the requisite number of operands, and push onto the operand stack the result of applying that operator to this operands

Question 8

Linked List

Answer 8

A recursive data structure that is either empty (null) or a node having a generic item and a reference to a linked list.

Question 9

Insert at beginning LL

Answer 9

Time it takes is independent of length of the list.

Question 10

Remove from beginning LL

Answer 10

Running time is independent of the length of the list.

Question 11

Insert at the end LL

Answer 11

Need a link to the last node in the list. Every method that modifies the list needs code to check whether that variable needs to be modified.

Question 12

Insert/remove at other positions LL

Answer 12

Take time proportional to the length of the list. Doubly-linked list is the standard solution.

Question 13

Harmonic Sum

Answer 13

1 + 1/2 + 1/3 + … 1/n ~ ln n

Question 14

Triangular Sum

Answer 14

1 + 2 + 3 + … + n ~ n**2/2

Question 15

Geometric Sum

Answer 15

1 + 2 + 4 + 8 + … + n = 2n - 1 ~ 2n when n = 2**n

Question 16

Stirling’s Approximation

Answer 16

log2n! = lg1 + lg2 + lg3 + … + lgn ~ nlgn

Question 17

Binomial Coefficient

Answer 17

n on top, k on bottom (n choose k), number of ways to choose an unordered subset of k from a fixed set of n elements n!/k!(n-k)! ~ n**k/k! when k is small

Question 18

Exponential Approximation

Answer 18

(1-1/x)**x ~ 1/e

Question 19

LL Queue Implementation

Answer 19

First is head of LL, last is end of LL. Enqueue at end, dequeue at beginning of list.

Question 20

Iterators implementation

Answer 20

Class implements Iterable, the class then overwrites an iterator method which returns an Iterator. A private class then implements Iterator and implements hasNext, remove and next (usually not remove).

Question 21

LL vs ArrayList Stack

Answer 21

LL: Every operation takes constant time in worst case but extra time and space to deal with the links
AL: Every operation takes constant amortized time but less wasted space
AL is faster overall time, but LL ensures that no operation will be much larger than any other.