Comp 250 Exam 3 Questions PDF

Comp 250 Exam 3 Questions For Exam 3 you will be assigned 5 randomly chosen questions from the following list. Please answer the questions thoroughly. Any part of the answer that is missing or incomplete will result in lost points. You will NOT have access to y...

Comp 250 Exam 3 Questions For Exam 3 you will be assigned 5 randomly chosen questions from the following list. Please answer the questions thoroughly. Any part of the answer that is missing or incomplete will result in lost points. You will NOT have access to your textbook or any notes during the exam. 1.​ Explain algorithm analysis and Big O notation. How and why is it used in software development? a.​ algorithm analysis i.​ studying an algorithm’s performance in terms of the time and space as the input grows. ii.​ Used to predict the execution time and memory usage and determine the scalability of algorithms iii.​ Time Complexity: Measures how execution time grows with input size. iv.​ Space Complexity: Measures the additional memory required by the algorithm. b.​ Big O notation i.​ a mathematical notation the describes the upper bound of an algorithm’s growth rate ii.​ Simplifies performance analysis by focusing on the worst-case scenario and ignoring constant factors​ iii.​ The big-Oh notation is widely used to characterize running times and space bounds in terms of some parameter n, which is defined as a chosen measure of the “size” of the problem c.​ How and why is it used in software development? i.​ It shows easy comparison how two or more algorithms will behave when the inputs increase ii.​ Can show bottlenecks and areas for improvement iii.​ Ensures that software can handle the increased input sizes without performance loss 2.​ Describe how unsorted arrays are stored in memory. How are individual elements of an array accessed, inserted, and deleted in an unsorted array (assuming no empty elements in the middle  Comp 250 Exam 3 Questions of the data)? How would we search for an individual element in an unsorted array. What is the Big O for each operation? a.​ Storage of unsorted arrays in memory i.​ stored in contiguous memory blocks in no certain order ii.​ stored in a single block of memory where each element is the same data type and size b.​ Accessing an element i.​ use the index to find the memory address and the element in the matching cell ii.​ O(1) c.​ Inserting an element i.​ insert at the end: directly add the new element at the first open cell ii.​ insert at a specific position: shift all elements after the desired position to the right. Then place the new element in the chosen spot iii.​ at the end: O(1) iv.​ at a position: O(n) d.​ Deleting an element i.​ locate element based on index. shift all following elements to the left ii.​ O(n) e.​ Searching for an individual element in an unsorted array i.​ perform a linear search. 1.​ Start at the first element of the array. 2.​ Compare each element to the target value. 3.​ If the target value is found, return its index. 4.​ If the end of the array is reached without finding the value, return a "not found" indication. ii.​ O(n)  Comp 250 Exam 3 Questions 3.​ What is a linked list? Explain the difference between a singly linked list and a doubly linked list. Describe how each is stored in memory. How would we implement a singly linked list? How are individual nodes of a linked list accessed, inserted, and deleted? What is the Big O for each operation? a.​ Linked list i.​ A linear data structure where each node has an element and a pointer that points to the next node (or the previous node) ii.​ first node is called head iii.​ last node is called tail and is null iv.​ Components of a Node: 1.​ Data: Stores the value of the node. 2.​ Pointer: Stores the memory address of the next node (or both previous and next nodes in a doubly linked list). b.​ Differences between a singly linked and a doubly linked list i.​ c.​ Memory storage of each i.​ stored in non contiguous memory and can be located anywhere in memory as long as the pointers are correctly implemented ii.​ Singly Linked List: Each node occupies a separate block in memory, and the pointer connects nodes. Only one pointer per node points to the next node. iii.​ Doubly Linked List: Each node occupies a separate block with two pointers, one pointing to the next node and another to the previous node. d.​ How would we implement a singly linked list i.​ ADD MORE HERE  Comp 250 Exam 3 Questions e.​ Big O for each operation i.​ f.​ How are individual nodes accessed, inserted, and deleted i.​ access: start from the head and traverse until the desired node is found O(n) ii.​ Insertion 1.​ at the head: Update the new nodes pointer to point to the previous front node, and then update the head to point to the new node. O(1) 2.​ at the tail: traverse to the last node and update the new element to point to the tail, and have the old end point to the new node. O(1). IS THIS RIGHT? 3.​ middle: go to desired position. Make new node point to next node. Have previous node point to new node. O(1). iii.​ Deletion 1.​ at the head: reassign head to point to the next node. O(1) 2.​ Middle/End: Traverse to the previous node, update its pointer to skip the node being deleted iv.​ MAKE SURE ALL OF THE BIG O ARE RIGHT 4.​ What is recursion? In what circumstances might we use recursion? How would we implement recursion? What is the Big O complexity of a recursive algorithm? a.​ What is recursion? i.​ a programming technique where a function calls itself ii.​ defining a function in terms of itself iii.​ It solves complex problems by breaking them into smaller and smaller subproblems  Comp 250 Exam 3 Questions b.​ Circumstances to use recursion i.​ binary search, calculating factorials, navigating tree structures c.​ How to implement a recursion i.​ Set a base case which defines when the recursion will stop ii.​ Make the recursive case which reduces the problem sizes and repeats the pattern making the recursive call until the base case is reached d.​ Big O notation of a recursive algorithm??? i.​ O(n) because that is how many times the recursion has to run 5.​ Explain the difference between a stack and a queue and give examples of when we would use each one. How might we implement a stack data structure? How would we insert and remove elements of a stack data structure? What is the Big O of each operation? a.​ Stack i.​ A linear data structure that follows the LIFO (Last In, First Out) principle. ii.​ Elements are added and removed only from the top of the stack. iii.​ Examples of Use: 1.​ Undo/redo functionality in text editors. b.​ Queue i.​ A linear data structure that follows the FIFO (First In, First Out) principle. ii.​ Elements are added at the rear and removed from the front. iii.​ Examples of use 1.​ an online line for gettings tickets 2.​ Managing requests in web servers. c.​ IMPLEMENTING A STACK STRUCTURE?? i.​ use a singly linked list so then the head is the newest element d.​ Inserting and Removing Elements in a Stack  Comp 250 Exam 3 Questions i.​ insertion 1.​ Add the new element to the top of the stack. 2.​ O(1) ii.​ Removal 1.​ Remove and return the topmost element of the stack. 2.​ O(1) 6.​ Explain the difference between a stack and a queue and give examples of when we would use each one. How might we implement a queue data structure using an array? How would we insert and remove elements of a queue data structure? What is the Big O of each operation? a.​ Stack i.​ A linear data structure that follows the LIFO (Last In, First Out) principle. ii.​ Elements are added and removed only from the top of the stack. iii.​ Examples of Use: 1.​ Undo/redo functionality in text editors. b.​ Queue i.​ A linear data structure that follows the FIFO (First In, First Out) principle. ii.​ Elements are added at the rear and removed from the front. iii.​ Examples of use 1.​ an online line for gettings tickets 2.​ Managing requests in web servers c.​ IMPLEMENTING a queue d.​ Inserting and removing elements in a queue i.​ insertion 1.​ Add the new element to the rear of the queue 2.​ Adjust the rear pointer using modulo arithmetic for circular queue behavior  Comp 250 Exam 3 Questions 3.​ O(1) ii.​ Removal (dequeue) 1.​ remove and return the front of the queue 2.​ Adjust the front pointer using modulo arithmetic. 3.​ O(1) 7.​ Describe how sorted arrays are stored in memory. Give two methods for sorting an array and explain how they are implemented. What is the Big O of each sorting method. How would we search for an individual element of a sorted array? What is the Big O analysis for the sorting and searching operations? a.​ How are sorted arrays stored in memory i.​ Contiguous Memory Blocks: Like any array, sorted arrays are stored in contiguous memory locations, with each element directly following the previous one. ii.​ Order: Elements are stored in ascending or descending order based on a sorting criterion. b.​ Methods for sorting an array and how they are implemented i.​ Bubble sort 1.​ Compare adjacent elements in an array 2.​ swap them if they are in the wrong order 3.​ Repeat the process for all elements until the array is sorted 4.​ O(n^2) ii.​ Insertion sort 1.​ starts with an array 2.​ compare the values starting from the first value and moving to the next index if it is greater than the other 3.​ insert values into correct location as you receive them 4.​ traverse the list linearly 5.​ O(n^2) but slightly better than a bubble sort  Comp 250 Exam 3 Questions c.​ Searching for an element in a sorted array i.​ Binary Search 1.​ Compare the target element with the middle element of the array. 2.​ If they match, return the index. 3.​ If the target is smaller, search the left half; if larger, search the right half. 4.​ Repeat until the target is found or the array is exhausted. 5.​ O(logn) 8.​ What is a growable array list (expanding array) and why might we use it? What method do we use to expand an array once it has reached its capacity? What are the two strategies we may use when determining how much to expand our array? What is the Big O complexity of expanding our array? a.​ An expanding array is an array that can be adapted to increase in size to account for new data that pushes past the fixed capacity of the array. i.​ Expansion method 1.​ Allocate a new array B with larger capacity 2.​ Set B[k] = A[k], for k= 0,...,n−1, where n denotes the current number of items. 3.​ Set A= B, that is, we henceforth use the new array to support the list. 4.​ Insert the new element in the new array. ii.​ 2 strategies for determining how much 1.​ Geometric Increase in Capacity a.​ Often doubled 2.​ Arithmetic progression a.​ adding a fixed number iii.​ O(n) from the individual push operations  Comp 250 Exam 3 Questions 9.​ What is a priority queue and why might we use it? Give two methods for implementing a priority queue using an array. Explain the Big O complexity of insertion and removal for each method. a.​ Priority Queue - This is a collection of prioritized elements that allows arbitrary element insertion, and allows the removal of the element that has first priority i.​ WHY b.​ Implementation Methods i.​ array based Unsorted List 1.​ Entries are stored in no particular order, allowing for O(1) time complexity for insertions since elements are appended to the end of the array. However, operations like min or removeMin require scanning the entire array to find the smallest key, resulting in O(n) time complexity. ii.​ Binary Heap 1.​ 10.​What is a binary heap and what might we use it for? Is it sorted vertically or horizontally? How would we implement a binary heap using an array? Explain the insert and removal process of a binary heap. What is the Big O complexity of each operation? a.​ Binary Heap - i.​ A binary heap is a complete binary tree used to implement priority queues, satisfying two key properties: the heap property (parent nodes are greater/lesser than their children in max-heaps or min-heaps) and the shape property (tree is filled level by level, left to right). It is used in priority queues, heap sort, and graph algorithms. The structure ensures logarithmic time complexity for insertion and deletion while maintaining the heap order. b.​ Sorting i.​ Vertically, it maintains parent-child relationships according to the heap property, while horizontally, elements at the same level are not ordered. The focus is on efficiently finding the min/max at the root, rather than achieving a fully sorted structure. c.​ Implementation with Array i.​ A binary heap is implemented using an array, where the root node is stored at index 0, and the child nodes for a node at index i are at 2i+1 (left) and 2i+2  Comp 250 Exam 3 Questions (right), with the parent at (i−1)/2. This array representation ensures efficient storage without pointers while preserving the complete tree structure. The array's indexing makes traversal and updates straightforward, supporting logarithmic insertion and deletion times. d.​ Insertion/Removal i.​ To insert, add the new element at the end of the array and "bubble up" by comparing it with its parent and swapping if needed, ensuring the heap property. To remove the root, replace it with the last element, then "bubble down" by swapping it with the smaller/larger child (in min/max heaps) until the heap property is restored. Both operations take O(logn), as the height of the tree is at most log(n). 11.​What is a hash table? What data structure might we use to store a hash table? What are the two stages of hashing? Describe two methods of handling a collision. Describe the insertion and deletion operations of a hash table. What is the Big O complexity of each operation? a.​ Hash Table - Hash code takes the key field, and converts it to a numerical value i.​ Then use compression function to map it to an element of the array b.​ Collision Handling i.​ Separate Chaining ii.​ Linear Probing c.​ Insertion/Deletion i.​ Insertion ii.​ Deletion 12.​What is a skip list? Describe the methods of inserting into and searching a skip list. What is the Big O complexity of each? a.​ Skip List i.​ A skip list is a probabilistic data structure that extends a sorted linked list by adding multiple levels to create "towers" of nodes. Each node in the base level points to its next neighbor, while higher levels (towers) act as express lanes to skip over multiple nodes, enabling faster traversal. This hierarchical structure  Comp 250 Exam 3 Questions allows skip lists to efficiently perform search, insertion, and deletion operations, often used as an alternative to balanced trees. b.​ Insertion/Search Methods i.​ To insert, locate the position in the bottom layer where the new element belongs, then probabilistically promote the element to higher levels by flipping a coin until failure or the maximum level is reached. For searching, start at the topmost layer and traverse forward or drop down to lower levels as needed, narrowing the search to find the element. Both processes rely on skip lanes to minimize traversal, ensuring efficiency. c.​ Big O Complexity i.​ In a skip list, search, insertion, and deletion all have an average time complexity of O(logn) due to the logarithmic number of layers and probabilistic balancing. 13.​What is a binary search tree? Is it sorted vertically or horizontally? How are binary search trees implemented? Describe the process of inserting a new node into a binary search tree. What process do we follow if a binary search tree becomes unbalanced? Describe the method for searching for an individual node within a binary search tree. What is the Big O complexity of each operation (insertion and searching)? a.​ Binary Search Tree i.​ A binary search tree (BST) is a hierarchical data structure in which each node has at most two children, called the left and right child. The BST property ensures that for any node, all values in the left subtree are smaller, and all values in the right subtree are larger. b.​ Sorting i.​ Horizontally c.​ Implementation i.​ Array Based using left child 2i +1 and right child is 2i + 2 d.​ Perform rotations to balance out the tree i.​ If you have an unbalanced tree with nodes in a straight line on the right 1.​ perform a left rotation to put back into the tree ii.​ forms a right left zig zag  Comp 250 Exam 3 Questions 1.​ perform right rotation to put in straight line a.​ then perform left to put them back into a tree 2.​ A B C => C becomes root, A left, B Right Singly linked list best or array, but fixed size - STACK