Cit 594

Front 1

When is it appropriate for a class x to extend a class y?

Back 1

-when X is a kind of y

- when it makes sense for x objects to have all the operations of y.

Front 2

In general, should you use inheritance or composition? why?

Back 2

-inheritance inherits all the method

-composition just some specific methods, need getters and setters. Use when x is not a kind of y.

Front 3

when methods are private..

Back 3

easier to debug because no other methods are changing it at the same tme

Front 4

Quicksort's complexity- average case

Back 4

-keep partitioning and sort

-O(nlog2n)- log2n is depth

Front 5

Quicksort's complexity- worst case

happened when?

Back 5

O(n^2)

-when the array is already sorted/inversely sorted

Front 6

Pivot's value for Quicksort

Back 6

best: median--guaranteeO(nlogn)

Front 7

Plausible choice for pivot value for Quicksort

Back 7

median of the three- pick three values and find their median

Front 8

Two ways of creating thread

Back 8

1) class Animation extends Thread{...}

2) class Animation implements Runnable{...}. Require public void run()

Front 9

When start() called, what happened?[extends Thread]

Back 9

request a scheduler to run the thread. The thread will be in the ready state.

Front 10

signature of extends Thread

Back 10

class Animation extends Thread{

public void run() {}

}

Animation anim = new Animation();

anim.start();

Front 11

signature of implements Runnable interface

Back 11

class Animation implements Runnable {

}

Runnable requires run method

Animation anim = new Animation();

Thread myThread = new Thread(anim);

myThread.start();

Front 12

What happens when you call a Thread's start() method?

Back 12

Thread's state changes to be ready.

Front 13

What happens when you call a Thread's run() method?

Back 13

Thread's state to running.

Front 14

What is monitor?

Back 14

Monitor is a set of multiple routines which support thread synchronization. None of the routines in the monitor can be executed by a thread until that thread acquires the lock

Front 15

When does a thread die?

Back 15

When it finished its run() method.

Front 16

daemon thread

Back 16

thread that will be automatically terminated when all non-daemon threads die. They usually run background supporting tasks for normal threads.

Front 17

Livelock

Back 17

when two or more processes repeatedly change state and at the same time block one another

Front 18

if an object is mutable,..

Back 18

every access to it must be synchronized

Front 19

When a Thread enters synchronized code, what does this prevent other Threads from doing? (Be precise.)

Back 19

To execute their code blocks

Front 20

What object is used by a synchronized instance method as a monitor?

Back 20

the object's monitor

Front 21

What object is used by a synchronized static method as a monitor?

Back 21

the monitor of the Class object

Front 22

Give two possible reasons for using a synchronized statement rather than a synchronized method.

Back 22

1) want to synchronize only some part of the method

2) when synchronize requires to have different object monitors

Front 23

Distinguish between parallelism and concurrency.

Back 23

Parallellism is when two or more processes run simultaneously, while concurreny is when two or more prcesses run aynchronously.

Front 24

What is a "check-then-act" error, and why is it always an error?

Back 24

It allows other threads to execute during the gap.

Front 25

What is a data race, and what must you synchronize in order to avoid having one?

Back 25

when two threads try to modify same data space at the same time. The end result becomes unpredictable. Synchronize the method that will modify the data

Front 26

When does a deadlock occur?

Back 26

when two or more processes are waiting to get a lock form one another, or waiting for one another to finish

Front 27

What does it mean to say that an operation is atomic?

Back 27

when the operation happens all at once, meaning no other threads can access the same data while the operation is being performed

Front 28

present the following graph [insert picture] as an adjacency matrix.

Back 28

element[i][j] has a mark if i and j are connect.

- the matrix is symmetric about the main diagonal

Front 29

Represent the following graph [insert picture] as an edge set.

Back 29

nodeset = {1,2,3}

edgeset = {(1,2),(1,3)}

Front 30

Represent the following graph [insert picture] as an adjacency set.

Back 30

nodeset = {1,2,3}

1>{p,q}

p = (1,2), q = (1,3)

Front 31

When searching a graph, what are the two techniques for avoiding getting caught in a cyclic loop?

Back 31

1. keep a set of nodes that are already explored

2. mark the nodes itself as having been explored

Front 32

What are the fields in a Plex?

Back 32

-Containers

-Contents

- Origins

-destinations

Front 33

Mention three ways in which a hypergraph might extend the notion of a graph.

Back 33

-Edges may originate from and/or point to graphs or other edges

- nodes may be in many graphs at the same time

- it is a collection of zero or more graphs

Front 34

What validity rules apply to the fields of a Plex?

Back 34

-If plex x is a container of plex y, then plex y is a content of plex x.

-If plex y is an origin of plex x, then plex x is a destimation of plex y.

Front 35

If a Plex implements a node in a regular (non-hyper) graph, what are the contents of each field of that Plex?

Back 35

-content set is empty.

-container set contains a single graph that the node is is

-origin set contains edges that point to the node

-destination set contains edges that come out of the node

Front 36

If a Plex implements a graph, what are the contents?

Back 36

-container, origin and destination are empty. Content set has the graph

Front 37

If a Plex implements an edge, what are the contents?

Back 37

-container set is empty

-content set has a single graph which is where the edge is in

-origin set contains the node which the edge comes from

-destination set contains the node which the edge points to

Front 38

What is the name of the open-source alternative to Google's MapReduce?

Back 38

Hadoop

Front 39

Briefly define "sequential cutoff".

Back 39

when there is no need to split the work into more than one process

Front 40

what does invoke in fork do?

Back 40

create an instance of the class which is a recursive task

- should be called from sequential code only

Front 41

Create a subclass of Thread. What's it in forkjoin?

Back 41

create an incrementor

Front 42

Override run. Forkjoin?

Back 42

compute()

Front 43

Call start. Forkjoin?

Back 43

invoke

Front 44

Put a result in a shared field. Forkjoin?

Back 44

join

Front 45

Call run directly. Forkjoin?

Back 45

none

Front 46

join. Forkjoin?

Back 46

join but forkjoin returns the value as well

Front 47

map in Mapreduce

Back 47

map key to a value. Add to a hashmap

Front 48

reduce in MapReduce

Back 48

count # of occurrences in the hashmap then emit back

Front 49

Forkjoin vs Mapreduce

Back 49

- Forkjoin takes advantage of multiple cores and recursively partitions a task into smaller tasks

- MapReduce does one big spilt and doesn't communicate till reduce

-Forkjoin limites by the size as it runs on a single node

-Mapreduce scales well for larger input

Front 50

RAM =?

Back 50

Random Access Machine

Front 51

RAM model's assumptions

Back 51

1) There is one single processing unit

2)There is an arbitrarily large amount of memory

3) Accessing any arbitrarily chosen memory location takes unit time

Front 52

RAM model breaks down when?

Back 52

when an array is too large to fit the memory

Front 53

Thread-based or shared-memory processing

Back 53

Threads share memory and communicate by reading/writing to that memory

Java out of the box

Front 54

Message passing parallel processing

Back 54

Threads/ Actors sends messages to one another

Front 55

Overhead

Back 55

costs incurred by parallel algorithm but not sequential algorithm

Front 56

What are the overhead?

Back 56

- 1) synchronization

2) communication

3) contention (for shared memory ~ lock)

4) extra computation

Front 57

CTA =?

Back 57

Candidate Type Architecture

Front 58

Amdahl's law?

Back 58

Some proportion of P can be run in parallel, 1-P run in sequential

- will run in 1/(P/N) + (1-P) = the maximum speedup

- the more data, the more speedup we will get

Front 59

what is load imbalance?

Back 59

when one process has much less work to do that others, resulting in idle time

Front 60

Java's concurrency rules:

Back 60

1)its the mutable state

2) make fields final unless they need to be mutable

3) Document your synchronization policy

Front 61

What is an actor?

Back 61

lightweighted thread with its own private memory

Front 62

Model of concurrency's elements:

Back 62

1)actor

2) shared memory

2) STM: software transactional memory- if the value change, update. No, otherwise.

Front 63

Pros for function programming:

Back 63

immutable values are automatically thread-safe.

Front 64

Moore's law:

Back 64

Processor is getting faster and faster in foreseeable future, stated by an Intel co founder.

Front 65

Functional Programming characteristics:

Back 65

1) function is treated as a value

2)Functions act like functions in mathematics

3) Immutable values are strongly overemphasized than mutable values.

Front 66

Scala advantages:

Back 66

1) shorter verbosity

2) not designed for concurrent programs

3) Scala is more consistent. All values are objects in Scala, but not in Java(primitives)

4) principle of uniform access. doesn't need to know what what type it is function or value

Front 67

var vs val

Back 67

var is mutable; val is immutable

Front 68

Unit type's value

Back 68

()

Front 69

null in Java == ..in scala

Back 69

Option type

Front 70

"You can write a Fortran program in any language."

Back 70

You can write a crappy program in any language.

Front 71

Scala's map

Back 71

List(1,2,-3,-4) map (_abs)

returns List(1,2,3,4)

Front 72

Scala's filter

Back 72

List(1,2,-3,-4) filter(_>=0)

returns List(1,2)

Front 73

Scala's foldl

Back 73

list = List(10,2,3)

list.foldLeft(0)(_-_)

return 0-10-2-3 = -15

Front 74

Scala's foldr

Back 74

list = List(10,2,3)

list.foldRight(0)(_-_)

return (10-(2-(3-0)))

Front 75

Scala's reduceLeft

Back 75

list = List(10,2,3)

list.reduceLeft(_-_)

return 10-2-3 = -15

Front 76

minimaxing

Back 76

choose the max among those mins

Front 77

Heuristic function

Back 77

computes at a given node what your best move will be

Front 78

As you minimax on a game tree, the PBV at the node you start from (where it is your move) will never ____________.

Back 78

be lower than the PBV of the node's parent--beta cutoff

Front 79

As you minimax on a game tree, the PBV at a node where it is the opponent's turn will never ____________.

Back 79

be higher than the PBV of the node's parent--alpha cutoff

Front 80

To maximize the amount you can prune a game tree, in what order should you explore nodes?

Back 80

top to bottom

Front 81

Define state space

Back 81

consists of:

1) a set of states

2) a set of operators

Front 82

Define "best first search."

Back 82

search for the node that seems to be closest to the goal state

Front 83

Define "heuristic."

Back 83

is a rule of thumb used to decide what's the best choice given the current state, incorporating knowledge of the problem space.

Front 84

Define "blind search."

Back 84

searching algorithm which doesn't utilize any knowledge of the problem

Front 85

What does it mean to say that a heuristic is "optimistic"?

Back 85

never overestimate the distance from the current state to the goal

Front 86

In the A* algorithm formula f(N) = g(N) + h(N), what are N, g, h, and f?

Back 86

N= current node

g = distance from start state to the node

h = estimated distance from the node to the goal

f = our best guess form the start state to the goal, passing though N

Front 87

When searching a state space, what is the single most important way to minimize the size of the state space?

Back 87

choose a good choice of operators

Front 88

Is the A* algorithm a best-first search technique? If so, how? If not, why not?

Back 88

Yes. We are given a node to find the best possible move from there.

Front 89

Under what circumstances will A* find a best solution?

Back 89

if h(n) is optimistic

Front 90

What are the space requirements for an A* search?

Back 90

may require exponential storage

Front 91

How does IDA* differ from an iterative deepening search?

Back 91

instead of using g(N) to cut off searching, use f(N) instead (the estimated total depth). If longer, don't search.

Front 92

What are the space requirements for an IDA* search?

Back 92

linear in length of the path

Front 93

list match {|

case a @ List(b @ _, c @ _*) => s"After $b in $a comes $c"

| }

List(1, 2, 3, 4, 5)

Back 93

After 1 in List(1,2,3,4,5) comes List(2,3,4,5)

Front 94

Pseudorandom number

Back 94

look random but are predictable if you know the algorithm

Front 95

linear congruential method

Back 95

r = (a*r +b)%m; a and b are big prime numbers, m is 2^32 or 2^64

Front 96

seed?

Back 96

initial value of r (random number)

Front 97

What is another name for a Gaussian distribution?

Back 97

Normal curve with mean = 0.0 and sd = 1.0

Front 98

It's usually a good idea to put the word static in front of Random random = new Random(). Why?

Back 98

because we want the random to be based on the same random function, as we want an equally likely sampling. So we want the random to be static, not an instance

Front 99

runtime of stupid sort

Back 99

O((n+1)!)

Front 100

Scala's equivalent of static:

Back 100

companion object

Front 101

sealed classes(Scala)

Back 101

all subclasses are declared on the same file

Front 102

Trait (Scala) = Java....

Back 102

interface

Front 103

substring(a,b)

Back 103

not including position b

Front 104

singleton object

Back 104

there is only one copy of the object

Front 105

referential transparency

Back 105

1) deterministic

2) side-effect free

Front 106

function literal

Back 106

parameter_list => function_body

Front 107

higher-order function

Back 107

ones that take function as a parameter or return function as a result

Front 108

get method from map

Back 108

return Some(value)

Front 109

getOrElse(4,"Hello")

Back 109

will return a string!!! Problem.

Front 110

Tail recursive

Back 110

if the recursive call is the very last thing it does

Front 111

Factorial's tail recursive version

Back 111

factorial(n) { return factorial1(n,1)}

factorial1(n, a){if n ==0 return a

return factorial1(n-1, n*a)

}

Front 112

What is currying?

Back 112

Currying is a way to make partially applied functions

Front 113

best technique from genetic algorithm:

Back 113

sexual reproduction with a small mutation rate

Front 114

curve fitting's gene:

Back 114

a,b,c,d,e,f

Front 115

curve fitting's chromosome:

Back 115

[a,b,c,d,e,f]

Front 116

Advantages of probabilistic matching

Back 116

1) theres more genetic diversity as all has some chance to be a parent

2) best organisms will contribute most to the next generation

Front 117

Genetic algorithms are

Back 117

1) fun

2) mind-bogglingly slow

3)good for a vey few types of problems- use when you see no other way to tackle the problem

Front 118

Binary search

Back 118

-keep changing the range to compare based on the value in the middle

Front 119

Binary search's complexity

Back 119

O(logn)

Front 120

Bubble sort

Back 120

last element is the largest

Front 121

Bubble sort's complexity

Back 121

O(n^2)

Front 122

Bubble sort's loop invariant

Back 122

for all j > outer, if i < j, then a[i] <= a[j]

Front 123

selection sort

Back 123

swap the smallest value with the one at the location

Front 124

selection sort's complexity

Back 124

O(n^2)

Front 125

Selection sort's loop invariant

Back 125

for all i, if outer <= i <= inner, then a[min] <= a[i]

Front 126

Insertion sort

Back 126

insert to the right position starting from the beginning

Front 127

Heapsort

Back 127

- sifting up

-remove the right most leave to be the root then sift again

-works for only balanced and left-justified binary tree!!

Front 128

Heapsort's complexity

Back 128

O(nlogn)

Front 129

when's Heapsort better than Quicksort?

Back 129

when we need a guaranteed worst time, especially when n is large.

Front 130

When is Quicksort better than Heapsort?

Back 130

The average performance is better. If n is not too large, quicksort is a better choice.

Front 131

Define heap

Back 131

left-justified tree whose children has smaller values than their parents

Front 132

Define heap property

Back 132

children's values are less than or equal to parent's

Front 133

When representing a binary tree as an array,the right child of the root is at index ________.

Back 133

2*i +2, root value is at the beginning

Front 134

When representing a binary tree as an array,the left child of the root is at index ________.

Back 134

2*i +1

Front 135

a binary tree is balanced if...

Back 135

the tree has two children at depth 0 to n-2

Front 136

Which nodes of the binary tree automatically have the heap property?

Back 136

leaves

Front 137

During Heapsort, what is the maximum number of nodes that can fail to have the heap property?

Back 137

1 child of each node, and the leafs so for n nodes at depth k( n – 2 ^ k) / 2

Front 138

case class in Scala

Back 138

-automatically create

1) equals, hashCode, toString, and copy methods

Front 139

Alpha-beta searching is based on what two assumptions?

Back 139

1. The opponent is rational.

2. the opponent algorithm is similar to player's algorithm.

Front 140

What algorithm type is effectively a depth-first search on a virtual tree?

Back 140

Backtracking algorithm

Front 141

What algorithm type uses at least two recursive calls at each level?

Back 141

Divide and Conquer algortihm

Front 142

What type of algorithm can be described by "do what is best in the short term, and hope the long term works out"?

Back 142

Greedy algorithm

Front 143

Define "heuristic."

Back 143

a rule of thumb used to evaluate which option to look at first

Front 144

define satisficing

Back 144

stop as soon as the solution found is good enough

Front 145

Describe a genetic algorithm for arranging dates.

Back 145

1. Randomly create 100 ways of arranging dates

2. Repeat 1000 times {

3. Calculate the sum of the difference between the rating of each date

3. keep 10 ways that have the lowest value

4. for each way, keep the dates that the rating difference is less than 10, and shuffle the rest}

Front 146

Name or otherwise indicate three different problems for which a greedy algorithm works well.

Back 146

Activity-selection problem, Fractional Knapsack, Huffman coding

Front 147

A dynamic programming algorithm can find an optimal solution to a problem if, for that problem, the "principle of optimality" holds. What is this principle?

Back 147

Whatever the initial state is, remaining decisions must be optimal with regard to the state resulting from the first decision.