Abstraction

Question 1

State what is meant by an abstract data type

Answer 1

Is a collection of data. When we want to use an abstract data type, we need a set of basic operations

Question 2

List the basic operations that abstract data types have to follow

Answer 2

1. Create a new instance of the data structure
2. Find an element in the data structure
3. Insert a new element into the data structure
4. Delete an element from the data structure
5. Access all elements stored in the data structure in a systematic manner

Question 3

Give examples of abstract data types

Answer 3

1. Stacks
2. Queues
3. Linked Lists
4. Binary Trees
5. Hash Tables

Question 4

How does a stack work

Answer 4

Items are piled on items on top. The item that is accessible is the one on top of the stack. If we try to find an item in the stack and take it out, we are likely to cause pile to collapse.
The baseofstackpointer will always point to the first slot in the stack.
The topofstackpointer will point to the last element pushed onto the stack.
When an element is removed from the stack, the topofstackpointer will decrease to point to the element now at the top of the stack.

Question 5

Explain how a queue works

Answer 5

Items added to the queue, get added to the end (endofqueuepointer)
When the item at the front of the queue leaves, we need to move all the other items one step forward. This creates a circular queue where we adjust the frontofqueuepointer

Question 6

Explain how an insertion sort works

Answer 6

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Question 7

State the advantages of insertion sort

Answer 7

1. Simple
2. Efficient in practice compared to bubble sort
3. Only requires a constant memory space
4. Can sort the list as it receives it

Question 8

State the disadvantages of insertion sort

Answer 8

1.Less efficient for large lists

Question 9

State how a binary search works

Answer 9

Repeated checking of the middle item in an ordered search list and discarding the half of the list which does not contain the search item

Question 10

What are the advantages of binary search?

Answer 10

1. Faster to search for items than other algorithms

2. Simple algorithm

Question 11

What are the disadvantages of binary search?

Answer 11

1. Not needed for small amount of elements
2. Works on lists already sorted
3. Lacks efficiency is the list doesn’t have direct access
4. Hash lookups are faster