CC4 - Finals Flashcards
- Aka Last-In-First-Out (LIFO)
- Top – entry/exit point
Stacks
– Insert or push some item “x” onto the stack.
* Before this operation, the stack if often checked if it has enough capacity to accommodate the new item
* If stack is full, an overflow would occur
Push (x)
- – Removing the most recent item or element from the stack.
- Must ensure that the stack is not empty before this operation
- If stack contains no item, popping would cause an underflow error
Pop( )
- – Returns the copy of the item or element at the top of the stack.
- The item itself is not removed from the stack
- This operation is also called peek
Top( )
- – It will return true if the stack is empty, false otherwise.
- Normally applied before the pop operation to avoid stack undeflow
IsEmpty( )
- – It will return true if the stack is full, false otherwise.
- Normally applied before the push operation to avoid stack overflow
- Not used when dynamic memory allocation is used
IsFull()
- generates an empty stack object and reserves necessary storage space
Create
– removes all elements from the stack and releases memory allocated to stack
Destroy
Array Implementation
- the top of the stack is at the beginning of the array, which is inefficient due to the need to shift elements
- the top is at the end, which is* more efficient as it only requires constant time* for push and pop operations.
- uses an array to store data, with a variable “top” tracking the current position of the top element, and the array size defining the maximum capacity, where the top is incremented on push and decremented on pop.
Disadvantage of Array Implementation of Stacks
- Size of stack needs to be specified at compile time
- If an application requires less space than the array size, storage space will be wasted
- The program will crash if application requires more storage space at runtime
- uses a pointer to track the top of the list, with elements added and removed only at that top, ensuring a Last-In, First-Out data structure.
Linked-List Implementation
Push
- Create a new node
- Copy element to the new node
- Link pointer of new node is set to point to pre-existing front node
- Head pointer is re-set to point to the new node
Pop
- Topmost element is copied for removal
- A new pointer is created to point to front mode
- Head pointer is reset to point to the next node
- Using the new pointer, front node is deleted
: inserts an element on the front of the list
* insertFront(x)
: returns and removes the element at the front of the list
* removeFront()
: inserts an element on the back of the list
* insertBack(x)
: returns and removes the element at the end of the list
* removeBack()
: inserts an element on the front of the list.
1) Allocate a new node
2) Have new node point to old head
3) Update head to point to new node
insertFront(x)
: returns and removes the element at the front of the list.
1) Update head to point to next node in the list.
2) Return element of previous head and delete the node.
removeFront()
: inserts an element on the back of the list.
1) Allocate a new node
2) If tail is NULL, update head and tail to point to the new node; otherwise.
* Have the old tail point to the new node.
* Update tail to point to new node.
insertBack(x)
: returns and removes the element at the end of the list.
1) No efficient way of doing.
2) Typically would not use a linked-list if this operation is commonly used
removeBack()
- Most programming languages use stacks to manage subroutine calls by storing necessary information like return addresses, parameters, and local variables in an activation record on the stack, which is then popped off when the subroutine returns.
Recursion Implementation
O(N) vs O(1)
- O(N) represents linear time complexity, where the time taken by an algorithm grows proportionally to the size of the input data (N),
- O(1) represents constant time complexity, meaning the time taken remains the same regardless of the input size.
Advantages & Disadvantages of Stacks
Advantages of Stacks
* Helps manage the data in particular way (LIFO) which is not possible with Linked list and array.
* When function is called the local variables are stored in stack and destroyed once returned. Stack is used when variable is not used outside the function.
* It gives control over how memory is allocated and deallocated.
* Stack frees you from the burden of remembering to cleanup(read delete) the object
* Not easily corrupted (No one can easily inset data in middle)
Disadvantages of Stacks
* Stack memory is limited.
* Creating too many objects on the stack will increase the chances of stack overflow
* Random access not possible
is a legal combination of operands and the operators.
algebraic expression
is the quantity (unit of data) on which a mathematical operation is performed.
- may be a variable or a constant
Operand
is a symbol which signifies a mathematical or logical operation between the operands. Example of familiar operators include +,-,*, /, ^
Operator
the expressions in which operands surround theoperator, e.g. x+y, 6*3 etc this way of writing the Expressions is called ___________
infix notation
Postfix notation are also Known as
Reverse Polish Notation (RPN)
They are different from the infix and prefix notations in the sense that in the postfix notation, operator comes after the operands, e.g. xy+, xyz+* etc.
- is another way of writing arithmetic expression.
Postfix notation
Prefix notation also Known as _____________
Polish notation
operator comes before the operands, e.g. +xy, *+xyz etc.
Prefix notation
- When an operand lies between two operators that have the same priority, the operand associates with the operator on the left. (a + b – c) (a * b / c / d)
Tie Breaker
- Sub expression within delimiters is treated as a single operand, independent from the remainder of the expression. [(a + b) * (c – d) / (e – f)]
Delimeters
is normally implemented by placing necessary information about the subroutine (including the return address, parameters, and local variables) onto a stack.
subroutine call
A subroutine call is normally implemented by placing necessary information about the subroutine (including the return address, parameters, and local variables) onto a stack.
This information is called an ________.
activation record
is special type of LinkedList.
- FIFO (First-in, First-out) data structure. That is, the first element to be added awill be the first element to be removed, and so forth.
- Like a stack, a it does not support removal of element in the middle; it only supports deletion from the head of the queue and insertion at the end of the queue.
Queue
Three main operations
Enqueue - a list-like structure that provides restricted access to its elements.
- may only be inserted at the back
Dequeue - removed from the front
Peek – returns the top value
Comparison of Array-Based and Linked Queues
- All member functions for both the array-based and linked queue implementations require constant time.
- The space comparison issues are the same as for the equivalent stack implementations.
- Unlike the array-based stack implementation, there is no convenient way to store two queues in the same array, unless items are always transferred directly from one queue to the other.
- Given a list of data find the location of a particular value or report that value is not present
Searching
- If items are sorted then we can divide and conquer
- dividing your work in half with each step
- generally a good thing
Searching in a Sorted List
- A fundamental application for computers
- Done to make finding data (searching) faster
Sorting
– The data collection to be sorted is kept in the main memory.
Internal Sorting
– The sorting of data stored on secondary devices. Data is sorted in the main memory and written back to the secondary device.
External Sorting
- an iterative sorting algorithm that repeatedly steps through the list, comparing adjacent elements and swapping them if they are in the wrong
- 1 order, gradually moving the largest elements to the end of the list until the entire list is sorted.
Bubble Sort
Dis/Advantages of Bubble sort
Advantage
* Easy to understand
* Easy to implement
* No demand for large amounts of memory
* Once sorted, data is available for processing
Disadvantage
1. Sorting takes a long time
Best/Worst case of Bubble sort
Best-case O(n)
Worse-case O(n2) – reverse sorted
- Slightly better performance
- Efficient than bubble sort
- O(n2) – both best- and worse-case complexity
Selection Sort
Dis/Advantages of Selection sort
Advantage
* The main advantage of the selection sort is that it performs well on a small list.
* Because it is an in-place sorting algorithm, no additional temporary storage is required beyond what is needed to hold the original list.
* Its performance is easily influenced by the initial ordering of the items before the sorting process.
Disadvantage
1. The primary disadvantage of the selection sort is its poor efficiency when dealing with a huge list of items.
1. The selection sort requires n-squared number of steps for sorting n elements.
1. Quick Sort is much more efficient than selection sort
Key Differences Between Bubble Sort and Selection Sort
- In the bubble sort, each element and its adjacent element is compared and swapped if required. On the other hand, selection sort works by selecting the element and swapping that element with the last element. The selected element could be largest or smallest depending on the order i.e., ascending or descending.
- The worst-case complexity is same in both the algorithms, i.e., O(n2), but best complexity is different. Bubble sort takes an order of n time whereas selection sort consumes an order of n2 time.
- Bubble sort is a stable algorithm, in contrast, selection sort is unstable.
- Selection sort algorithm is fast and efficient as compared to bubble sort which is very slow and inefficient.
- Simple sorting algorithm
- Array is virtually split into a sorted and unsorted part
Insertion Sort
Algorithm of Insertion Sort
To sort an array of size n in ascending order:
1. Iterate from arr[1] to arr[n] over the array.
2. Compare the current element (key) to its predecessor.
3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
Dis/Advantages of Insertion sort
Advantage
* The main advantage of the insertion sort is its simplicity.
* It also exhibits a good performance when dealing with a small list.
* The insertion sort is an in-place sorting algorithm, so the space requirement is minimal.
Disadvantage
1. The disadvantage of the insertion sort is that it does not perform as well as other, better sorting algorithms
1. With n-squared steps required for every n element to be sorted, the insertion sort does not deal well with a huge list.
1. The insertion sort is particularly useful only when sorting a list of few items
Implementation of Insertion Sort
- The first step is to create a method that takes in input the array to be sorted, sort arr as seen in line 3 in the code above.
- The second step is to create an outer for loop which will iterate over each element of the array as shown in line 5.
- The third step is to create a separate iterator, j which will check for the ascending order of elements in the list, as shown in line 7.
- The fourth step is the inner while loop:
a. As shown in line 9 the while loop must satisfy two conditions: the value of j must be greater than 0, and the value at index j-1, must be greater than the value at index j.
b. If this condition holds true then, as shown from lines 11 to 14, the key is set to the value at index j.
c. Then the values at j and j-1 are swapped.
d. The value of j is reduced by 1 and the loop continues till one of the conditions breaks. - This continues for every iteration of the outer for loop till that also breaks.
- Divide and conquer algorithm
- Merge() function – merging 2 halves
Merge Sort
Dis/Advantages of Merge sort
Advantage
* It can be applied to files of any size.
* Reading of the input during the run-creation step is sequential ==> Not much seeking.
* If heap sort is used for the in-memory part of the merge, its operation can be overlapped with I/O
Disadvantage
1. Requires extra space »N
1. Merge Sort requires more space than other sort.
1. Merge sort is less efficient than another sort
