Flashcards
Common 241 Questions
Cards in this deck (15)
- 1Give the formal definition of f(n) = O(g(n))For some constant A, f(n) <= Ag(n), for all sufficiently large n
- 2Every recursive algo includes two different types of execution. What are they, and what role do they play?Recursive execution: defined in terms of itself, the method executes on the result of the method. Continues until terminated by a base case.
Base case execution: execution that terminates the recursive loop when some condition has been reached eg. some variable has reached 0. - 3What is the fundamental characteristic of a recursive data structure?Fundamental characteristic of a recursive data structure is that it can be described in terms of itself
- 4Binary SearchCheck the midpoint – this either finds the value or gives us a new range to search in which is only half the size.
Implement recursively - 5How does selection sort work?Find the smallest item in the list. Swap it with the first item. Find the smallest item in the remainder of the list, swap it with the
first item of the remainder. Repeat until finished. - 6How does Insertion Sort work?Process the array one element at a time. Insert each new element into its correct position among the previously processed elements.
- 7How does Merge Sort work?(Pre) Split the array into two pieces of nearly equal size,
(Rec) Sort the pieces,
(Post) Merge the results together - 8What is the difference between truly random and "psuedo-random" numbers?Truly random numbers are generated
by observation of some unpredictable physical process.
Psuedo-Random numbers seem random but if the initial seed is known as well as the algorithm, then they can be predicted
with 100% accuracy. - 9What are generic types and what is their importance in ADTs for collections?Generic types allow us to define a class so that it stores, operates on, and manages objects whose type is not specified until the class is instantiated.
They are important in collections because there is no need for separate interfaces for each type of ADT. - 10How are the ADTs and behaviour of stacks and queues similar? How do they differ?They are both linear data structures, that support the same behaviour peek; add; remove.
Stack is LIFO, Queue is FIFO - 11What is the difference between a static and a dynamic data structure?A static data structure is one whose structure is fixed at the time it is created and cannot be changed. i.e we cannot change the structure of an array. A dynamic data structure is one whose structure can change. i.e linked lists
- 12What are the two conditions that distinguish a heap from a general binary tree?Parent node is greater than or equal too its at most two children.
Heap is a balanced complete tree. - 13How do the input and output operations of a priority queue differ from those of a normal queue?In a priority queue, every item is added with an associated priority. When an item is removed, it is always the item with the highest priority.
In a standard queue, items are added and removed in first in, first out order. - 14Why is a heap a natural data structure for representing a priority queue ADT?A heap arrangement is ordered by priority. It shares the same order of removal that a queue has. Adding items is efficient with O(logn) efficiency. And removing the highest priority element is O(1) as it is always at the top of the queue.
- 15What is quick sort- Choose one of your data items called the pivot.
- Split the remaining data into the items smaller than the pivot and the items larger than (or equal to) the pivot.
- Put all the small items before the pivot and all the large items after the pivot.
- Sort those two groups individually
Information
- Description
- Flashcards on Common 241 Questions, created by Tom Weatherall on 11/06/2019.
- Created by
- Tom Weatherall
- Views
- 0
- Rating