UNC-CH COMP 410

Poll Everywhere Questions and Replies

Sorts, Skiplist and Trie

• "stable" sorts means... ?
• "in place" sort means... ?
• T/F: no sort can be better than O(N log N)
• Worst case time complexity of skiplist "find"
• Average case time complexity of skiplist "insert"
• Liklihood of worst case for skiplist

Euler, Hamilton, P, NP

• Are these 2 graphs isomorphic?
• Are these 2 graphs isomorphic?
• Are these 2 graphs isomorphic (this is how a program see this problem)?
• Euler Circuit?
• Euler Path?
• Hamilton Circuit?
• Hamilton Path?
• Hamilton Path?
• Hamilton Circuit?
• Hamilton Path?
• T/F: Every tree has no Hamiltonian path
• T/F: Cyclic graph and Hamiltonian path
• Hamiltonian path?
• Euler path?
• T/F: Every tree has no Euler path

Graph Algs: topo sort, SSSP, Dijkstra, MST

• linear for graphs?
• space use for adjacency matrix implementation
• space use for adjacency list implementation
• For digraph shown, which is a valid topo sort?
• For digraph shown, which is a valid topo sort?
• T/F: a graph that is a tree has no valid topo sort?
• T/F: a graph that is a tree has at least 2 valid topo sorts?
• T/F: a graph that is a tree has as many valid topo sorts as it has leaves?
• Topo sort on a graph that is a BST?
• weighted digraph shortest path
• unweighted digraph shortest path
• unweighted graph, MST
• weighted graph, MST
• How many MSTs in this graph
• How many MSTs in this graph
• Greedy algorithm

Basic Graph Theory

• Max number of edges in a graph
• T/F: In digraph with N nodes, longest path has length N-1
• T/F: In digraph with N nodes, node with no out-edges implies no cycles
• The digraph shown is ...
• T/F: If digraph is bipartite then it is a tree
• T/F: Acyclic Digraph is strongly connected
• Language generated by FSM
• Model USA people social connections
• Model USA states airlines connections
• Connecting planar graphs

More Binary Heaps

• Node location after a delMin?
• Node location after 2 delMins?
• Node location after insert 10 ?
• Worst case time complexity of getMin ?
• Worst case time complexity of delMin ?
• Worst case time complexity of N inserts to construct?
• Worst case time complexity of "magic build" to construct?
• Worst case time complexity to sort, have all N numbers at once?
• Worst case time complexity to sort, get N numbers one at a time?
• complexity of sorting with heap?

Binary Heap, Priority Queue

• PrQUE as linked cell list... worst case time for "enq"?
• PrQUE as linked cell list... worst case time for "front"?
• PrQUE as Balanced BST ... worst case time for "enq"?
• PrQUE as Balanced BST ... worst case time for "front"?
• Is this figure a valid min bin heap?
• Is this figure a valid min bin heap?
• Is this figure a valid min bin heap?
• Heap or No Heap?
• Heap or No Heap?

BST Balance, Sorting

• Worst case of sort with list with insort op?
• Worst case of sort with BST (no balancing)?
• Average case of sort with BST (no balancing)?
• Worst case of sort with AVL (balanced BST)?
• Worst case of sort with Splay tree (balanced BST)?
• Worst case of sort with min Binary Heap ?
• Worst case of sort with min Binary Heap (more exact)?
• Worst case of sort with BST (not balanced, more exact)?
• Worst case of sort with AVL (balanced, more exact)?

Hashing, Hash Tables, HashMap

• In hash table, load lambda is...
• In hash table with chaining, load lambda tells us...
• T/F: In hash table with chaining, when lambda hits 1 table is full...
• T/F: In hash table with probing, when lambda hits 1 table is full...
• In hash table with probing, worst case for insert?
• In hash table with chaining, worst case for insert?
• T/F: In hash table with chaining, worst case for insert is O(1)
• TreeMap vs. HashMap
• T/F? Hashing can help us sort N items faster than N log N (it's T, but costs space)

Sets, Set of int

• member in set implemented as linked list
• add in set implemented as linked list
• add in set implemented as array list
• add in set implemented as array
• member in set implemented as (balanced) BST

More BST

• why use recursion?
• How many recursive calls made in recursive "height" computation?
• worst case complexity of insert on BST
• average case complexity of insert
• max # nodes in BST with height 15
• min # nodes in BST with height 15
• T/F: for any set of keys, there is one BST
• Traversal for keys in alpha order
• T/F: BST for sorting is better than Bubble Sort
• Worst case time complexity of post-order traversal

Trees, Traversal, BST

• Node height in a tree
• Node depth in a tree
• Tree height
• In-Order traversal
• Breadth-First traversal
• Adding to a Binary Search Tree

Runtime Stack, Heap, Recursion

• How much runtime memory needed for this code?
• How much runtime memory needed for this code?
• How much runtime memory needed for this code?
• How much runtime memory needed for this code?
• Meaning of "garbage collection" in Java

StackSet

• Worst case time complexity of push (linked cells)
• Worst case time complexity of pop (linked cells)
• Worst case time complexity of peek (linked cells)
• Worst case time complexity of contains (linked cells)
• Best case time complexity of push (linked cells)

Time Complexity, Big Oh

• Worst case time complexity of Bubble Sort
• Worst case complexity of Sorting into a List
• Which is worse that O(N^2)?
• Complexity of Code sample
• Another Big Oh for O(N^3) algorithm?

Lists, Stacks, Queues

• LIST with links, Big Oh of get?
• LIST with array, Big Oh of get?
• LIST with array, Big Oh of remove?
• LIST with links, Big Oh of add?
• LIST with links, best case Big Oh of add?
• STACK with array, Big Oh of push?
• STACK with links, Big Oh of push?
• QUEUE with array, Big Oh of deque?
• QUEUE with links, Big Oh of deque?

Getting Started

• Used Poll Everywhere before?
• Experience with JavaScript
• Definition of 'abstraction'