Flashcards
DSA: Lecture 4
Cards in this deck (43)
- 1hyhy?hy hy.
- 2What does the Dictionary ADT model?A searchable collection of key-element items
- 3What are the main operations of the Dictionary ADT?Searching, inserting, deleting items
- 4Applications of the Dictionary ADT?Address book, credit card authorization, mapping host names
- 5What are the Dictionary ADT methods? Describe them.findElement(k) -- if(dictionaryHasItem with key k), return its element
else return special element NO_SUCH_KEY
insertItem(k,o) -- inserts item (k,o) into dictionary
removeElement(k) -- same as find, but remove before returning element - 6New operations of Ordered Dictionary ADT (4 of them)closestKeyBefore(k)
closestElemBefore(k)
closestKeyAfter(k)
closestElemAfter(k) - 7What is a lookup table?An ordered dictionary implemented with a sorted sequence.
- 8How does this sorted sequence work?1. Store items of dictionary in array-based sequence, sorted by key
2. Use external comparator for the keys - 9What is a lookup table most effective for?Small size and little changes
- 10What is a binary search tree?A binary tree storing keys at internal nodes and satisfying:
key(u) <= key(v) <= key(w)
where u is node in left subtree of v, w is in right subtree of v - 11Do external nodes store items?No.
- 12In what order does inorder traversal visit keys?In increasing order
- 13Explain how Search works1. To search for a key k, start at root
2. Compare k with key of current node;
found if ==
go left is <
go right if >
3. If leaf is reached, key isn't found and return NO_SUCH_KEY - 14Try to write down the pseudocode for findElement.
- 15How does insertItem(k, o) work?1. Search for key k
2. If k != in tree, let w be leaf reached by search (temp leaf)
3. Insert k at node w and expand w into internal node - 16How does removeElement(k) work/1. Search for key k
2. If k = in tree, let v = node storing k
3. If v hasLeftChild(w), remove(v and w)
4. If v hasNoLeafChild, find internal node w that follows v (in order)
5. Copy key(w) into v
6. Remove w and left child z (a leaf) - 17Performance of Dictionary ADTSpace used -- O(n)
findElement, insertItem, removeElement -- O(h) where h = height of tree
Height h = O(n) worst case
= O(log n) best case - 18What is an AVL tree?An AVL tree is a binary search tree so that for every internal node v, the heights of v's children can differ at most 1.
- 19Height of AVL tree running time?O(log n)
How to solve this is in slides 4a. - 20Why would you restructure an AVL tree?To make it balanced. (slides 4a, slide 18)
- 21How does inserting a node work? Explain.1. Call restructure for the proper grandchild of an unbalanced node,
2. One (single or double) rotation is always enough to restore the balance in an AVL tree after insertion. - 22How does removal work in an AVL tree?1. Begins as in a binary search tree, which means the node removed will become an empty external node. Its parent, w, may cause an imbalance.
- 23What are the running times in AVL trees for: a single restructure, find, insert, and remove.Single restructure -- O(1),
Find -- O(log n)
Insert -- O(log n)
remove -- O(log n) - 24What is sorting?Given a set A = {a1, a2, ... , an}
and total ordering "<=" defined on A,
find a permutation i(1), ..., i(n) of indices, such that:
a(1) <= a(2) <= a(3) <= ... <= a(n) - 25Give a generic sorting algorithm
- 26How does insertion sort work?Divide: split L by putting first elem in L1 and rest in L2,
Recur: sort list L2
Conquer: insert elem in L1 into sorted list L2 - 27What is the running time of insertion sort?O(n^2)
- 28How does merge sort work?Divide: split L by putting first half in L1 and rest in L2,
Recur: sort lists L1 and L2
Conquer: merge lists L1 and L2 - 29Look at merge sort example in 4bN I C E M E M E
- 30Total running time of merge sort?O(n log n)
- 31How does selection sort work?1. Split L by putting smallest element in L1 and rest in L2
2. Selection sort list L2
3. Append element in L1 to front of sorted list L2 - 32What is the running time of selection sort?O(n^2)
- 33How does quick sort work?Divide: split L in equal-sized L1 and L2, with all elements in L1 that are < elem in L2
Recur: sort lists L1 and L2
Conquer: append list L2 to the end of L1 - 34What is the running time of quick sort?O(n^2) worst case,
Average: O(n log n) - 35Look at quick sort example in Lecture 4bk
- 36Also check summary of sorting algorithms in lect 4bK LEL
- 37What are 2 often used sorting methods that do not fit into the divide-and-conquer scheme?Bubble sort (O(n^2) method)
Shell sort - 38How does bubble sort work?Moves largest element to the end by "bubble comparisons"
- 39Describe a key-type property1. Keys are used as indices into array and can't be arbitrary objects
2. No external comparator.
3. Must be ORDINAL (e.g. int or char) - 40Describe a stable sort propertyThe relative order of any two items with the same key is preserved after the execution of the algorithm.
- 41As always, do HWand look at sorting meme vid
- 42How does storing a set in a list work?1. Implement a set with a linked list
2. Elements are stored sorted according to some ordering
3. Space used is O(n) - 43What are the 3 operations related to merging sets?Union, intersect and subtract
Information
- Description
- Flashcards on DSA: Lecture 4, created by krisbraz on 21/03/2015.
- Created by
- krisbraz
- Views
- 1
- Rating