Computer Science: Data Structures
and Algorithms
Doubly Linked List: advantage, disadvantage - Answer- Advantage: quick insert to
beginning, quick removal from end
Disadvantage: slow search, not great for indexing
Data Structures: Discuss characteristics of a Dictionary - Answer- Use when: order is
unimportant, frequently adding and removing items, frequently looking up items
Why is looking up, adding, and removing elements from a dictionary or hash map an
O(1) operation? - Answer- Hash maps are built upon arrays: keys entered into a
dictionary/hash map are hashed first to find where the key/value pair should be
stored. This position is unique and can be used for fast lookups, as well as insertions
and deletions.
When searching in a regular list, Python iterates over the list to see if a given value
is in the list -- this is an O(n) operation. When looking to see if a value is in a hash
table, Python hashes the value that's sought and can go immediately to that position
in the array to see if there is a value there. That process of hashing and indexing is
an O(1) operation.
Similarly, as every item in a hash map has a unique position, adding or inserting
items does not require that eery other item shift index position; an items' position is
not dependent on other items in the array.
Explain why removing elements from or adding elements to an arbitrary location in a
Python list are O(n) operations. - Answer- Python lists are contiguous in memory.
When an item is removed or added to the middle of a list, all the subsequent items in
the list must be shifted either up or down by one position
What's the runtime for Bubble Sort? - Answer- O(n^2) (very bad);
best case O(n)
What's the runtime for Quick Sort? - Answer- O(n log n) (okay);
worst case O(n^2)
What's the runtime for Merge Sort? - Answer- O(n log n) (okay)
particularly good when number of items being sorted increases
What's the runtime for Insertion Sort? - Answer- O(n^2) (very bad);
best case O(n).
Its good when the number of items being sorted is small, but as N grows, runtime
slows dramatically.
What's the runtime for TimSort? - Answer- O(n) (fair);
worst case O(n log n) (okay)
, What's the runtime for Heap Sort? - Answer- O(n log n) (okay)
What's the runtime for Selection Sort? - Answer- O (n^2) (very bad)
What's the runtime for Tree Sort? - Answer- O(n log n) (okay);
What's the runtime for Shell Sort? - Answer- O(n log n) (okay);
What's the runtime for Bucket Sort? - Answer- Ω(n+k) (very good; close to O(log n)
or O(1)
What's the runtime for Radix Sort? - Answer- Ω(n+k) (very good; close to O(log n) or
O(1)
What's the runtime for Counting Sort? - Answer- Ω(n+k) (very good; close to O(log n)
or O(1)
What's the runtime for Cube Sort? - Answer- O(n)
6. What is the difference between a tree and a graph? - Answer- A tree is a restricted
kind of graph where there are no loops or cycles.
(Might require pen/paper)
Using the Python implementation of Quick Sort from the instructions:
Given the list [8, 4, 1, 6, 5, 2, 7, 3]:
When this function is initially called, what is the value of list? - Answer- [8, 4, 1, 6, 5,
2, 7, 3]
(Might require pen/paper)
Using the Python implementation of Quick Sort from the instructions:
Given the list [8, 4, 1, 6, 5, 2, 7, 3]:
When this function is initially called, what is the value of pivot? - Answer- 5
(Might require pen/paper)
Using the Python implementation of Quick Sort from the instructions:
Given the list [8, 4, 1, 6, 5, 2, 7, 3]:
When this function is initially called, what is the value of low? - Answer- [ 4, 1, 2, 3 ]
(Might require pen/paper)
Using the Python implementation of Quick Sort from the instructions:
Given the list [8, 4, 1, 6, 5, 2, 7, 3]:
When this function is initially called, what is the value of high? - Answer- [8, 6, 7]
Top 3 characteristics of Lists - Answer- Iterable,
Ordered,
