Comp 401 Final Exam

Front 1

Liskov's Substitution Principle

Back 1

Any method that expects an object of type superclass must be able to use in its place an object of any subclass.

Front 2

When do we need to be careful about using inheritance?

Back 2

Anytime we start to override we are probably violating the substitution principle, be careful with overriding.

Front 3

What is type specific code, and how is it overcome

Back 3

Type specific code is code is writen for different data types. This is overcome by writing generic methods.

Front 4

What is an object's state? What is a stable state?

Back 4

An object's state is the value of it's attributes. An object is in a stable state when the values of its attributes make the invariants true.

Front 5

What is a class invariant and loop invariant.

Back 5

Class invariant - the loosest definition of a data structure that must always be true for the object to be legal.
Loop invariant - something which must be true before and after each iteration of a loop is run.

Front 6

Difference between static and dynamic arrays?

Back 6

Static size is set at compile time, its memory is permanetly bound, and its size is fixed. Dynamic can be given at runtime if necessary.

Front 7

Specialization and generalization in relation to inheritance

Back 7

We specialize when we move from a superclass to a subclass. We generalize when we move from a subclass to a superclass

Front 8

Polymorphism, static polymorphism, and dynamic polymorphism?

Back 8

Polymorhpism - a single thing can take on more than one form.
Static polymorphism - compile time, implemented in method overloading.
Dynamic polymorphism - based on inheritance and the substitution principle. This can include dynamic (or late) binding.

Front 9

Deep copy and shallow copy

Back 9

Deep copy is a clone. A shallow is an alias. Deep copy is equivilant and a shallow copy is identical

Front 10

Sorting contract

Front 11

Selection sort - definition, or idea behind it

Back 11

Named selection sort because we select the largest item in the unsorted part of the array and move it to the front of the sorted part. Invariant : Everything in the sorted part is greater than everything in the unsorted part

Front 12

What is the time complexity of selection sort?

Back 12

n^2

Front 13

Insertion sort - definition, or idea behind it

Back 13

we take the first element of the unsorted part and look through the sorted part to find the position where this new element is to be inserted, such that the sorted part remain sorted.

Front 14

Insertion sort, time complexity

Back 14

n^2

Front 15

Stages of software, the irony behind it

Back 15

Design
implementation
component testing
release
maintenance
Initially it was though that, for large projects, design and implementation would take the longest and be the most expensive, but it turns out that maintenance of the code is the most expensive.

Front 16

Single responsibilty principle

Back 16

Each things should do one thing and do it well. It states that every object should have a single responsibility, and that all its services should be narrowly aligned with that responsibility. The principle forms part of cohesion, a concept widely used in software development.

Front 17

Dependency inversion

Back 17

rely on abstraction, not implementation

Front 18

Early binding, late binding, pros of each

Back 18

Early Binding, is done at compile time.
Pros: Simple.
Fast.

Late binding, done at execution times.
Pros: Flexible.

Front 19

For each loops

Back 19

how the fuck do these work?

Front 20

Apparent type and actual type, definitinons and for z.draw()

Back 20

apparent type is the type at compile time. Actual type is the type at build.

for them to be different,apparent type must be an interface or superclass.
At early binding, z is a shape, so the apparent type is shape. At late binding, z is either a square/rectangle/circle/star, so the actual type is one of these things.

Front 21

Big Oh of F(n) when F(n) = n^4 + 2^n + log(n)

Back 21

O(2^N)

Front 22

Describe the difference between a recursive and iterative function

Back 22

An iterative function uses looping and works through the method only once. A recursive function calls itself in the body of the function, and works on a smaller set of data with each call of the function. Creates a new instance in the activation record with each call

Front 23

What are the two main parts of a recursive algorithm?

Back 23

The base case and the recursive case.

Front 24

What is a recursive definition?

Back 24

Is one in which the thing being defined is part of the definition.

Front 25

Questions to ask when choosing a java collection

Back 25

Are duplicates allowed? If not, then choose set.
Do the elements need to be kept in a fixed, stable order? If so, use a list.
Do the elements need to be accessed by a general key? Then use a map.
Elements accessed by an int (index)? Then use a list
Or by it's value? Then use a set or collection.

Front 26

What is the effect of applying indirection?

Back 26

It reduces coupling. Also allows for fewer duplicate copies by adding link nodes.

Front 27

What are the naming conventions for the following:

Class, Method or data member, Constant Data Member, local variable, package

Back 27

Class: Timer
Method: ensureCapacity
Consant MAX_CARDS
Local Variable: count or houseNumber
Package: all lowercase

Front 28

Stack memory and heap memory

Back 28

Stack memory only contains the activation records, and local variables (these are contained within the activation record). Heap Memory contains the objects used by member functions.

Front 29

What is in the activation record?

Back 29

The parameters, local variables, etc, that define the member function

Front 30

What is a loop invariant?

Back 30

A loop invariant is a condition that is necessarily true immediately before and immediately after each iteration of a loop

Front 31

What is the operation time for get in a binary search tree?

Back 31

O(log n)

Front 32

What is the operation time for set in a binary search tree?

Back 32

σ(log n)

Front 33

What is the operation time for insert in a binary search tree?

Back 33

σ(log n)

Front 34

What is the operation time for delete in a binary search tree?

Back 34

σ(log n)

Front 35

What is a binary search tree?

Back 35

A binary search tree is a binary tree whose elements are ordered such that for any node in the tree, all elements to the left are less than the node and all elements to the right are greater than the node.
The left and right subtrees are also binary search trees.

Front 36

Describe insertion sort.

Back 36

The element at the end of the unsorted list is picked and puts it in the right spot in the sorted portion.

Front 37

Describe selection sort.

Back 37

Picks the largest value in the unsorted list and puts it at the beginning of the sorted portion.

Front 38

What is the operation time for get in an array?

Back 38

O(1)

Front 39

What is the operation time for set() in an array?

Back 39

O(1)

Front 40

What is the operation time for insert in an array?

Back 40

O(n)

Front 41

What is the operation time for delete in an array.

Back 41

O(n)

Front 42

What is the operation time for get in a linked list or linked set?

Back 42

O(n)

Front 43

What is the operation time for set() in a linked list or linked set?

Back 43

O(n)

Front 44

What is the operation time for insert in a linked list or linked set?

Back 44

O(1)

Front 45

What is the operation time for delete() in a linked list or linked set?

Back 45

O(1)

Front 46

What is a tree?

Back 46

A tree is a hierarchical structure consisting of a collection of nodes, one of which is the root. All nodes, except for the root, have a single predecesssor called the parent, and zero or more children

Front 47

On a tree, what is a node with no children called?

Back 47

A leaf or external node

Front 48

In a tree, what nodes with common parents are called:

Back 48

Siblings

Front 49

In a tree, what is the degree of a node?

Back 49

The number of children that it has

Front 50

In a tree, what is the degree of the tree?

Back 50

Also called it's arity, it is the largest degree of all it's nodes.

Front 51

In a tree, what is a path and path length?

Back 51

A path is a sequence of unique, connected nodes. The path length is the number of nodes it contains. The depth of a node in a tree is the length of the path from the tree's root to the node.

Front 52

In a tree, what is the height of a node?

Back 52

The length of the longest path from the node to a leaf descendant.

Front 53

What are the three binary tree traversals and how to they work?

Back 53

Preorder: If a node is not null, then it visits the node. The it recursively calls the function on the node's left child. Then it recursively calls the method on the node's right child

InOrder: If the node is not null, then the method is called recursively on the node's left child. Then it visit's the node. Then it recursively calls the method on the node's right child.

Postorder: If the node is not null, then it recursively calls the method on the node's left child. Then it recursively calls the method on the node's right child. Then it visits the node

Front 54

What is the invariant of a balanced BST?

Back 54

The height difference between a left and right node can only be 1.

Front 55

What is the implementation of a recursive height function for a Binary Search Tree?

Back 55

int heightRec (BSTNode node) {
return 1 + max (heightRec(node.getLeft()), heightRec(node.getRight());
}