• Wrong document? Swap it for free
  • Written by students who passed
  • Immediately available after payment
  • Read online or as PDF
Sell
Where do you study
Your language
Document preview thumbnail
Preview 2 out of 15 pages
Exam (elaborations)

Computer Science: Data Structures and Algorithms Questions and Answers

Document preview thumbnail
Preview 2 out of 15 pages

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)

Content preview

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,

Document information

Uploaded on
August 18, 2024
Number of pages
15
Written in
2024/2025
Type
Exam (elaborations)
Contains
Questions & answers
$12.99

Wrong document? Swap it for free Within 14 days of purchase and before downloading, you can choose a different document. You can simply spend the amount again.
Written by students who passed
Immediately available after payment
Read online or as PDF

Seller avatar
Reputation scores are based on the amount of documents a seller has sold for a fee and the reviews they have received for those documents. There are three levels: Bronze, Silver and Gold. The better the reputation, the more your can rely on the quality of the sellers work.
Freshy
3.6
(11)
Sold
65
Followers
4
Items
6964
Last sold
1 week ago



Why students choose Stuvia

Created by fellow students, verified by reviews

Quality you can trust: written by students who passed their tests and reviewed by others who've used these notes.

Didn't get what you expected? Choose another document

No worries! You can instantly pick a different document that better fits what you're looking for.

Pay as you like, start learning right away

No subscription, no commitments. Pay the way you're used to via credit card and download your PDF document instantly.

Student with book image

“Bought, downloaded, and aced it. It really can be that simple.”

Alisha Student

Working on your references?

Create accurate citations in APA, MLA and Harvard with our free citation generator.

Working on your references?

Frequently asked questions