CMPT 280 FINAL EXAM WITH COMPLETE SOLUTIONS 100% VERIFIED
A list
A list is an abstract data type (ADT) that manages a collection of data with a linear
ordering
"extends"
functionality of a data structure -> this allows us to take an existing data structure class
and add new functionality or modify existing ADT functionality or to create specialization
of a more generic ADT
Ex: an extension of LinkedSimpletree280<String> to ExpressionTree
"implements"
when a class implements an interface, it agrees to provide implementations for all
methods declared in that interface
this ensures that any object of the class can be treated as an instance of the interface,
allowing for polymorphism and code reuse.
What is an interface?
Interface is a reference type, similar to a class that can contain only constants, method
signatures, default methods, static methods and nested types.
If the list is sorted, for example, then the position of an element has meaning; the fifth
element in the list is the fifth smallest element. Otherwise, the position of an element
indicates only the element's rank in the list order.
stacks and queues are linear data structures
,A linked list
A linked list consists of a series of nodes in a linear order. Each node represents a
different position in the list. Each node contains two pieces of data: the data element at
the position in the list represented by the node, and a reference to the node
representing the next position in the list. The node representing the last position in the
list contains a “null” reference for the next node, indicating that there is no next node.
Selection Sort
is one of the simplest sorting algorithms and is only used to sort lists between 10 to 20
elements. The Selection Sort selects the current smallest element and then swapping it
into place. This process happens continuously by finding the smallest element in the
array and swapping it into the correct position until the list is sorted.
Bubble Sort
this algorithm sorts lists by allowing the lowest or highest values to the top and then
sorting the list by comparing adjacent values and swapping them into the correct order.
it becomes inefficient when sorting a large amount of data
Merge Sort
This type of algorithm is usually used when the length of the array is very high. O(nlogn)
time
The list is split into two halves and is sorted by a recurring algorithm. After each half is
sorted, the list is then merged back together.
This is stable, merge sort can be used with linked lists without taking up any more
,space.
This implementation is not in-place since need O(n) additional place for the temp
variable.
Insertion Sort
used for sorting a smaller array of around 10 to 20 elements, small data sets or nearly
sorted data
.An Insertion Sort compares a key element with the previous element. If the algorithm
finds that the previous elements are greater than the key element, it moves the previous
element into the next place.
This is in-place and stable.
QuickSort
Similar to the Merge Sort, the QuickSort algorithm is a divide and conquer algorithm. It
chooses an element as a pivot and then partitions the list with all elements less than the
chosen pivot to the left and places the elements greater than the pivot to the right.
Quick Sort is a little faster than merge sort
Being unstable, sensitive to the choice of the pivot and vulnerable to the worst case
O(nlogn) on average and best case
O(n^2) in the worst case
in-place but not stable
, for(int j=0; j < n; j++) {
for(int k=0; k < j; k++) {
allons_y(j,k);
}
}
allons_y() is O(1)
n2+n+1
Does there exist a function f (n) for which the code from the previous question is Θ( f
(n))?
Yes
The function t(n) = 3n log 5n + 8√n + 12n^5/2 + 100 is:
O(n^5/2)
A list
A list is an abstract data type (ADT) that manages a collection of data with a linear
ordering
"extends"
functionality of a data structure -> this allows us to take an existing data structure class
and add new functionality or modify existing ADT functionality or to create specialization
of a more generic ADT
Ex: an extension of LinkedSimpletree280<String> to ExpressionTree
"implements"
when a class implements an interface, it agrees to provide implementations for all
methods declared in that interface
this ensures that any object of the class can be treated as an instance of the interface,
allowing for polymorphism and code reuse.
What is an interface?
Interface is a reference type, similar to a class that can contain only constants, method
signatures, default methods, static methods and nested types.
If the list is sorted, for example, then the position of an element has meaning; the fifth
element in the list is the fifth smallest element. Otherwise, the position of an element
indicates only the element's rank in the list order.
stacks and queues are linear data structures
,A linked list
A linked list consists of a series of nodes in a linear order. Each node represents a
different position in the list. Each node contains two pieces of data: the data element at
the position in the list represented by the node, and a reference to the node
representing the next position in the list. The node representing the last position in the
list contains a “null” reference for the next node, indicating that there is no next node.
Selection Sort
is one of the simplest sorting algorithms and is only used to sort lists between 10 to 20
elements. The Selection Sort selects the current smallest element and then swapping it
into place. This process happens continuously by finding the smallest element in the
array and swapping it into the correct position until the list is sorted.
Bubble Sort
this algorithm sorts lists by allowing the lowest or highest values to the top and then
sorting the list by comparing adjacent values and swapping them into the correct order.
it becomes inefficient when sorting a large amount of data
Merge Sort
This type of algorithm is usually used when the length of the array is very high. O(nlogn)
time
The list is split into two halves and is sorted by a recurring algorithm. After each half is
sorted, the list is then merged back together.
This is stable, merge sort can be used with linked lists without taking up any more
,space.
This implementation is not in-place since need O(n) additional place for the temp
variable.
Insertion Sort
used for sorting a smaller array of around 10 to 20 elements, small data sets or nearly
sorted data
.An Insertion Sort compares a key element with the previous element. If the algorithm
finds that the previous elements are greater than the key element, it moves the previous
element into the next place.
This is in-place and stable.
QuickSort
Similar to the Merge Sort, the QuickSort algorithm is a divide and conquer algorithm. It
chooses an element as a pivot and then partitions the list with all elements less than the
chosen pivot to the left and places the elements greater than the pivot to the right.
Quick Sort is a little faster than merge sort
Being unstable, sensitive to the choice of the pivot and vulnerable to the worst case
O(nlogn) on average and best case
O(n^2) in the worst case
in-place but not stable
, for(int j=0; j < n; j++) {
for(int k=0; k < j; k++) {
allons_y(j,k);
}
}
allons_y() is O(1)
n2+n+1
Does there exist a function f (n) for which the code from the previous question is Θ( f
(n))?
Yes
The function t(n) = 3n log 5n + 8√n + 12n^5/2 + 100 is:
O(n^5/2)
