Final review cards Flashcards
(89 cards)
1
Q
Computational complexity?
A
- How does the speed of the operation depend on N number of digits?
- Addition- Doing thing in for loop N times, other things once
- little operations dont depend on N, they are constants
- c1+c3+c2*N- only focus on N not constants
- Multiplication- some things done N times, some things done N squared times, some things done once
- Takes time proportional to N- O(N) order of N- addition O(N), multiplication O(N^2)
2
Q
How many bits N do we need to represent m?
A
between log2m and log2m+1
3
Q
List types info
A
- Arrays have constant time access
- Arraylist- ordered set of elements. For reference type, they objects are not in the arraylist they are referenced by it
- Linked list- nodes and objects- reference to first (head) and last (tail)- addFirst, removeFirst, addLast, removeLast
- For doubly linked list, removing last item is easier- dont have to loop through everything
4
Q
Time complexity in list types
A
ArrayList SLinkedList DLinkedList
- AddFirst O(N), O(1), O(1)
- removeFirst O(N), O(1), O(1)
- addLast O(1), O(1), O(1)
- removeLast O(1), O(N), O(1)
- remove(i) O(N), O(N), O(N)
5
Q
Abstract Data Structure (ADT)
A
-defines data type by values and operations from user prospective, ignores implimentation, more abstract than data structure
6
Q
Stack
A
-push, pop, isEmpty, peek- last in, first out
7
Q
Queue
A
enqueue, dequeue-first in, first out
-slow when implemented with arraylist- requires shift, or with expanding array, slow- use circular array. if needs to be expanded move head to front
8
Q
bubble sort
A
- time O(N^2)
- repeatedly loop through list, for each iteration if two elements in wrong order, swap them
- have to use temp variable for swap
- at end of first pass, largest is at end of list but smallest element can be anywhere
- add continue boolean to determine if switches are made
- add variable bc walk is one shorter each time
- best case, 1, worst case N*N/2
- passes through 1 more time after sorted to make sure it doesnt need to be sorted again
9
Q
Selection sort
A
- split list into 2, part at front is sorted, grow it by one. go through rest, find min, tack on to one that is sorted
- swaps min with element at beginning
- how many passes through inner loop? N(N-1)/2
- O(N)^2
- regardless of best or worse case, same amount of time
10
Q
Insertion sort
A
Insert element at index k into correct position with respect to elements at indices k, k-1
- shift items, down, insert each item one by one in correct place
- Best case, time N. Worst case N^2
11
Q
1+2+3….N
A
sequence that adds to n(n+1)/2
12
Q
Induction steps
A
For all n>=x, P(n) is true
- prove base case (P(x))
- For any k >=x, if P(k) is true, then P(k+1) is true
13
Q
Tower of hanoi
A
-Uses recursion
-tower(n-1)
-
14
Q
Call stack
A
stack which recalls which methods are being called
-call stack is used for recursion (factorial 2 is pushed, factorial 1 is pushed, 1 is popped 2 is popped )
15
Q
Fast power method
A
- divide by 2, either multiply x^n * x^n if even, x^n * x^n * x if odd, aka if 0 in binary 1 mult, i 1 in binary 2 mult
- still slower, multiplying bigger numbers- (mult is O(N) so longer num takes more time).
- fast recursive is same amount of time as iterative
16
Q
Binary search
A
search by going to middle of list, if greater checking before if lower checking after, changing mid to list subset mid
- can call recursively changing low or high in calling of method
- it is called
- O(log2n)- time that binary search, power x^n, converting to binary takes
17
Q
Fast computing time
A
- need something faster than n squared- this can potentially take minutes, hours, years
- need sorting that is between O(n) (not gonna be faster than order n) but faster than n^2
18
Q
Mergesort
A
- break list into 2 equal part
- sort each half recursively- continue to break in half until each list is 1, then merge
- merge two halves (look at head of each, add bigger. when one is empty, add rest of other list)
- proportionate to n log n (close to n, less than n squared)
- way better for big numbers than other sort methods
- slower than quicksort because it uses an extra list
19
Q
quicksort
A
-remove pivot- item on list
make a list of elements less than pivot, list of elements greater or equal to pivot
-recursively sort
-not same size- if bad pivot, all in same list
-concatenate list one and list 2
-dont need new lists- can be done in place. can use orig array only- no extra memory
-move items greater than pivot after, move items lower than pivot before
20
Q
recurrence relation
A
- sequence of numbers where t(n) is defined in terms of earlier numbers
- in computing- time it takes to solve a problem
- ex c+t(n-1) -> c + c + t(n-2) … cn + t(0)
- aka time it takes is proportional to N
- time for quicksort is n squared (bad pivot)- do middle of 3 values
21
Q
Big O
A
t(n) is a function that describes the time it takes for an algorithm on input size n, need to describe how t(n) grows as n becomes large (asymptotic)
-unlike limit, compare it to simple squation like n squared
-for graphs t(n) and g(n) for any larger number, t(n) is asymptotically bounded above by g(n)
t(n) is O(g(n)) if there are two constants n0 and c such that for all n>n0 t(n) < c g(n)
22
Q
Big omega Ω
A
- Lower bounds- at least___ time to do function of size n
- bound below asymptotically g(n) if beyond a certain n0 g(n) is below f(n)
- 2 constants (like big O)
- same rules as bigO
23
Q
constant factor rule
A
f(n) is O(g(n)) and a is positive constant
-af(n) is O(g(n))
24
Q
sum rule
A
f1(n) is O(g(n)) and f2(n) is O(g(n)) then f1(n) + f2(n) is O(g(n))
if f1(n) is O(g1(n)) and f2(n) is O(g2(n)) then f1(n) + f2(n) is O(g1(n) + g2(n))
25
product rule
if f1(n) is O(g1(n)) and f2(n) is O(g2(n)) then f1(n) * f2(n) is O(g1(n) * g2(n))
26
transitivity rule
if f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) is O(h(n))
27
big theta
t(n) and g(n) are two functions, t(n) is Θ(g(n) if t(n) is O(g(n)) and Ω(g(n))- 2 c constants
28
best and worse case
tbest(n) is runtime on best case
tworst(n) is runtime on worst case inputs
ex. remove in arraylist- if its 1, worst case theta(N) best case theta(1)
29
Limit rules
if limit t(n)/g(n) = 0; t(n) is O(g(n))
t(n) is not omega(g(n))
if limit t(n)/g(n) = infinity then t(n) omega(g(n)), t(n) not O(g(n))
if limit t(n)/g(n) = c (between 0 and infinity) then t(n) is theta(g(n))
30
String hashcode in java
s[i]x^s.length-1-i so that words with same letters in diff orders have diff hashcodes
31
hash function in java
hashCode(), compress by mod numbuckets (m is array length) allows for moving to keys in list
32
collision
-two or more keys k map to same hash value.
33
load factor of hash table
```
number of (key, value) pairs in map / number of buckets
-want to keep load factor below one
```
34
Depthfirst tree traversal
- preorder- if root is not empty, visit root, depthfirst (child)
- postorder- if root is not empty, for each child of root, depthfirst (child) visit root
- call stack for depthfirst
35
Non-recursive tree traversal (stack)
- Use a stack
- push the root
- current = s.pop, visit
- for each child push the child
- goes to right of tree
- always pre-order(even if visit after pushing)
36
tree traversal (queue)
- enqueue root, dequeue current
- enqueue children
- are visited by depth- row by row
- breadth first traversal
37
binary tree
each node has at most two children
- maxnode of binary tree 2^h+1 -1
- minnode = h+1
- each node has leftchild and rightchild
38
depthfirst binary tree
- if root is not empty, visit rooot
| - preorder root.left, preorder root.right (or postorder)
39
inorder binary tree
- inorder (left) then visit root then inorder right
40
expresion tree
- operators and values
- 3 + 4 *2 ,(4 * 2) is subtree
- leaves are operands,internal are operators
- inorder gives expression in order
41
types of expressions
-prefix *ab
infix a*b
postfix ab*
42
evaluate expression tree
- postorder traversal
| - if root is a leaf return, else operator, evaluate tree on 2 children (recursively)
43
Binary search tree definition
- same as binary tree node
- element is called key (comparable), unique
- for each node, every key of left subtree is less than key of node, right subtree greater than key of node
- inorder traversal visits nodes in order
- Works as binary search (in special case of balanced tree)- add/ remove to ensure balance
44
Find in BST
-if root isnt null and root isnt key, return find(root.left,key)
45
Find min/max in BST
- if root is null return null, if left of root is null return root, else findmin (root.left)
- max is same but with right
46
Add node BST
- if rood is empty, new node becomes root
- if key is less than root, add(root.left, key) if key is more than root, root = add (root.right,key)
- return root
47
remove node BST
- if root is null, return null
- check if key is greater or less than root, recursively removie left or right subtree
- if equals root (one you want to remove). if left or right subtree is null, root is right or left (one not null)
- else copy key of smallest of right subtree into root
- remove it from right subtree
- NEED TO UNDERSTAND, NOT MEMORIZE
48
balanced vs unbalanced BST
- balanced- height = log(n+1)-1
- n = 2^h+1-1
- unbalanced- height = n+1
- best case (unbalanced) O(1) for all functions, but worst case (unbalanced) O(n) for all functions
49
Priority queue
set of comparable elements or keys
- like a queue but we have a more general defintion of what element to remove next
- ADT- can add, removeMin (highest priority- 1 priority)
- implement with heap
50
Complete binary tree
-binary tree of heigh h that has every level less than h full, and all nodes at level h are as left as possible
51
min heap definition
complete binary tree with unique comparable elements, such that each nodes key is less than its childrens key
52
add element to heap
- need to stay complete binary tree, be bigger than parent
- add tree to next node, swap it with its parent
- recursively swap with parent until parent is smaller than child
- cur = new node at next leaf position
- while cur!=root and cur elem < cur parent elem, swap current and parent
53
remove min to heap
- remove root element
- lose last node in tree, stick value in place of root
- swap down tree- find min of two children and swap with root recursively
- tmp = root.element
- remove leaf note and put element into root
- while cur has a left child and cur element is less than currents left element) or right element), swap element with minchild.
54
heap (array implementation )
-positions in tree in order correspond to indices starting at 1
-relations within array-
parent = child/2.
left = 2*parent
right = 2*parent +1
55
buildheap
-create new array
-for the size, add items to list, have them upheap
-best case O(n)
-Worst case- nlogn
or
-assume array already contains element, for 2 to size, upheap
56
removemin heap implementation
-tmpElem = heap[1]
-heap[1] = heap[size]
-heap[size] = null
-size = size-1
downheap(1,size)
57
fast build heap
- half the nodes on a tree (at least) are leaves
- start at size/2, work to 1 (first non-leaf node), downheap (other nodes are already heaps)
- speed of n
58
heapsort
- given a list with size elements
- build a heap
- repeatedly call removemin and put the removed elements in a list
- can be done in place- swap first and last element, first value to end (separate list), downheap current first element
- backwards order list
59
Definition of a graph
A directed graph is a set of vertices V = {vi: iE1...n}
and a set of ordered pairs of these vertices called edges
-generalization of other types of structures (lists, trees)
60
Terminology of graphs
- in degree- number of edges going into a vertex
- Out degree- number of edges going out of vertex
- Path- sequence of edges such that the end of one edge is the start vertex of the next edge
- cycle- path where last vertex is same as first
- directed acyclic graph- no cycles- used to capture dependencies
61
How to implement a graph?
- class vertex with adj list and element
- might need class edge with endvertex and weight, with vertex class with edgelist
- reference- names are keys for a hashmap
- boolean visited, make sure false before traversal
62
Ways of representing adjecency
- List of adjecencies
- Matrix- 2d boolean array with 1 and 0 for if there is an adjacency with that node.
- if graph is dense (close to n^2 num of edges), want a matrix. if graph is sparse ( close to n) want a list.
63
Recursive graph traversal
- depthfirst- specify starting vertex- can only visit reachable nodes by path from vertex
- start by visiting v (start node)- for all (v,w) if w isnt visted, recursively visit
- ends up getting called in call tree (no cycles)
64
depth first non-recursive
-push v, while stack not empty, pop, push non visted (w)
65
breadth first non-recursive
enqueue v, while q isnt empty, dequeue and enqueue unvisited edges
-guaranteed to find shortest path first
66
inheritance
- classes extend other classes- ex. beagle extends dog extends animal, inherets methods and items from classes
- subclass inherits fields and methods of superclass
- constructors not inherited
67
constructer chaining
- can have many constructors with different parameters
| - call super class's constructor ex. in dog class call super(home), inherited from superclass.
68
overloading
- ex. add method in linked list class overloaded- can add element or element at index
- same method name, different parameter types
- within a class or between class and superclass
69
overriding
- dont change signature
- between classes
ex. string hashcode vs object hashcode
70
Object class
- root of tree of objects
| - object class is root- automatically inherited
71
Object toString class
class name + @ + hashcode in base 16
72
interface
- like a class, but only method signatures are defined
- ex list interface- arraylist implements list interface
- can declare something as a list, can only use list methods (not arraylist methods for ex). can create method for generic link type
- perhaps interface shape with getArea and getPerimeter
- must implement all methods of interface
73
relationship between classes and interfaces
- classes extend other clases
- classes can implement other interface(s)
- interfaces extend other interfaces
74
Abstract class
- like a class, can have fields and methods with bodies
- like an interface, can have methods with only signatuers
- cannot be instantiated, but it has constructors. constructors called in subclasses.
75
comparable interface
- has one method- compareTo
- returns 0 if equals, pos if greater, neg if less than
- keys in trees, priority queue, Strings are comparable
- make comparable method in class that compares, for ex. radii
76
iterator interface
- want to visit all objects in collection- might have multiple
- boolean hasNext, next()
- method created by class
77
iterable interface
- class is able to generate an iterator
- constructor generates iterator
- needs iterator method- call the iterator
78
primary type conversion
- diff primitive types have diff num of bytes- can convert to wider (double, long) or narrower (boolean, char)
- widen by promotion (int * double) or narrow by casting
- For narrowing need to enter type
79
class type conversion
- class dog wider than class beagle (even though subclass has more methods and fields)
- Dog myDog = new Beagle();// this is widening
80
polymorphism
- different methods with the same name, method defined by object. method type can be narrower
- ex. printing an obj, if obj is Dog, uses Dog toString method
81
.class file
-"byte code" - format that has class name, fields, methods, superclass
82
class Class
- class descriptor
- object taht contains all info about a class
- getSuperClass, getMethods, getFields, getName
- extends object class
- when getClass is called, returns class descriptor
- when getClass is called on class descriptor, get Class class
83
Garbage
- Item that is no longer referenced/ pointed to
| - myDog new Beagle ("Bob"; myDog = new Terrier "Tim", Bob is garbage
84
Garbage collection
- Java virtual machine maintains linked list of all objects by hashcode
- What to do when space fills up
- Mark (build graph and identify live objects)
- Sweep (remove garbage)
- Use another list to keep track of gaps (free space) between objects. Adding new object shrinks gap, add new node to live object list
85
Garbage collector graph
- Vertices correspond to reference variables in call stack and to objects. Edges correspond to references
- For each vertex, traverse call stack and mark as visited
86
public vs private
- if unspecified, available to anything in same package
- public- available to any package
- private- needs public method to access
- don't use modifiers within a method- only exist while method is on call stack
87
Inheritance with private and public
- if in same package, inherits public and unspecified, not private
- if in different package, only public
- can extend public classes across packages, but cannot extend unspecified class in diff class
88
static modifier
- ex. count number of objects that have been created
| - cannot have a static class, but can inside classes
89
final modifier
cannot extend class
| -can have static and final
