Data structures and algorithms Exam Questions with Answers

Data structures and algorithms Exam Questions with Answers Why do we need a high level language? - Correct Answers: High-level languages encourage you to think more about the problem domain and less about the execution platform. There is less ceremony, so you can spend more time on stuff that actually brings you value. Money. Cheaper developers, faster development speeds, and less bugs equal more money. A high level language is easier to code in and therefore less error prone. Program - Correct Answers: A set of instructions for the computer to perform a task. It can be stored in memory or downloaded from the internet. when do you use float instead of double? - Correct Answers: Though both Java float and Double can represent floating-point numbers, we can consider a couple of things to choose between Java float and double. Though both Java float vs Double is approximate types, use double if you need more precise and accurate results. Use float if you have memory constraint because it takes almost half as much space as double. If your numbers cannot fit in the range offered by float, then use double. Though be careful with floating-point calculation and representation, don't use double or float for monetary calculation, instead use Big Decimal. What is selection? - Correct Answers: Making the program behave differently each time it runs. the switch statement - Correct Answers: In computer programming languages, a switch statement is a type of selection control mechanism used to allow the value of a variable or expression to change the control flow of program execution via search and map. Designing algorithms - Correct Answers: A strategy to solve a problem in terms of 1. the actions to be executed 2. the order in which the actions are to be executed when do we use a for loop? - Correct Answers: generally used when the number of repetitions or iterations is known in advance. For example, you know there are 10 students in a class and you want to calculate the average mark for them all. What to do when the number of loops is not fixed? - Correct Answers: Use a while loop What is the difference between a while loop and a for loop? - Correct Answers: A while loop causes the code inside it to be repeated until some condition is satisfied. A for loop is repeated for a fixed number of iterations. Asymptotic Notation - Correct Answers: Asymptotic notations are the mathematical notations used to describe the running time of an algorithm when the input tends towards a particular value or a limiting value. For example: In bubble sort, when the input array is already sorted, the time taken by the algorithm is linear i.e. the best case. But, when the input array is in reverse condition, the algorithm takes the maximum time (quadratic) to sort the elements i.e. the worst case. When the input array is neither sorted nor in reverse order, then it takes average time. These durations are denoted using asymptotic notations. There are mainly three asymptotic notations: Big-O notation Omega notation Theta notation What types of trees do you know? - Correct Answers: Free trees Binary Positional trees Rooted trees Ordered trees Define a free tree - Correct Answers: In a free tree there's no designated root vertex. You can make a free tree into a rooted one by choosing any of its vertices to be the root. Define rooted tree - Correct Answers: In graph theory, the basic definition of a tree is that it is a connected graph without cycles. This definition does not use any specific node as a root for the tree. A rooted tree introduces a parent — child relationship between the nodes and the notion of depth in the tree. Roughly and visually, adding a root to a tree just corresponds to grabbing one of the nodes of the tree and hanging the tree with this node. Once the tree is hanged, each node has a depth related to its height, a parent to which it is suspended and several children which hang from this node. what is a binary and positional tree - Correct Answers: a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A tree is either empty or consists of a node containing a label value and an indexed sequence of zero or more children, each a positional tree. If every node has two positions, we have a binary tree and the children are its left and right subtrees. Again, nodes are the parents of their non-empty children. How can you distinguish between binary trees and ordered trees - Correct Answers: An ordered tree is an oriented tree in which the children of a node are somehow "ordered." What sorting algorithms do you know? - Correct Answers: Quicksort Heapsort merge sort insertion sort Insertion Sort - Correct Answers: Each item is take in turn, compared to the items in a sorted list and placed in the correct position. A simple sorting algorithm that builds the final sorted array (or list) one item at time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Insertion sort sorts in place and therefore uses less memory space. Though its asymptotic running time is O(n^2), its code is very tight so the constant factor in the running time is very small. Insertion sort is, therefore, an efficient algorithm for a small input size. Merge Sort Algorithm - Correct Answers: Sorts an array by cutting the array in half, recursively sorting each half, and then merging the sorted halves Insertion Sort Algorithm - Correct Answers: Insertion Sort Worst Case - Correct Answers: O(n^2) Heapsort algorithm - Correct Answers: a sorting algorithm that inserts the values to be sorted into a heap Heapsort Worst Case - Correct Answers: n log n Quick Sort Worst Case - Correct Answers: O(n^2) Quick Sort - Correct Answers: Unstable, O(n log n) for a good pivot,O(n^2) for a bad pivot Ω(n log n) : Uses partitioning O(n), Pick a median of 1st, middle, and last element for pivot. Random selection is also good, but expensive. Algorithm can be slow because of many function calls. Sorts in place - Correct Answers: in-place sort (algorithm) Definition: A sort algorithm in which the sorted items occupy the same storage as the original ones. These algorithms may use o(n) additional memory for bookkeeping, but at most a constant number of items are kept in auxiliary memory at any time. Also known as sort in place. Generalization (I am a kind of ...)sort. Specialization (... is a kind of me.)American flag sort, quicksort, insertion sort, selection sort, Shell sort, diminishing increment sort, J sort, gnome sort. Heap Data Structure - Correct Answers: The (binary) heap data structure is an array object that we can view as a nearly complete binary tree Nearly complete binary tree - Correct Answers: An almost complete binary tree is a special kind of binary tree where insertion takes place level by level and from left to right order at each level and the last level is not filled fully always. It also contains nodes at each level except the last level. How many types of binary heaps are there? - Correct Answers: max-heaps min-heaps What is the heap property of a max-heap? - Correct Answers: A[PARENT(i)] >= A[i]. The largest element in a max-heap is stored at the root., and the subtree rooted at the node contains values no larger than that contained at the node itself. The min-heap property - Correct Answers: The smallest element in a min-heap is at the root. for every node i other than the root, A[PARENT(i)] <= A[i] Complete Binary Tree - Correct Answers: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. Priority Queue data structure - Correct Answers: Max-Heapify - Correct Answers: Runs in O(lg n) time is key to maintaining the max heap property Build-Max-Heap - Correct Answers: Runs in linear time O. Produces a max-heap from an unordered input array Heapsort - Correct Answers: Runs in O(nlogn). Sorts an array in place combines the better attributes of the insertion sort and merge sort. Like merge sort, the running time heapsort is O(nlgn). Like insertion sort, it sorts in place so uses less memory. Heapsort involves a very useful data structure - heap, which also has other uses such as an efficient priority queue. The heapsort process involves building a heap then extracting the root element, followed by maintaining the heap property each time. MAX-HEAP-INSERT - Correct Answers: runs in O(lgn), allows the heap data structure to implement a priority queue Binary Heap - Correct Answers: an almost complete binary tree representation of (part of) an array, the size of the heap may be smaller than the size of the array. What are the minimum and maximum numbers of elements in a heap of height h? - Correct Answers: 2h, 2h+1-1 Is an array that is in increasing sorted order a min-heap? - Correct Answers: Yes Is the sequence < 23, 17, 14, 6, 13, 10, 1, 5, 7, 12> a max heap? - Correct Answers: No On the heap shown below, how many elements have heights 0, 1, 2, and 3? - Correct Answers: 5, 3, 1, 1 sorting algorithms - Correct Answers: such as BubbleSort and QuickSort, arrange items in a list in a particular order. Quicksort - Correct Answers: uses the partitioning and comparison operations to arrange the elements of a list in the correct order. Its expecting running time is Ө(nlgn), but it generally out-performs heapsort in practice because like insertion sort, it has tight code so the hidden constant factor in its running time is small. Quicksort is unique because its speed depends on the pivot you chose. uses a divide and conquer approach. A partition procedure divides the original problem into subproblems (that are solved recursively) and sorts the pivot element in place. The expected running time for quicksort is Ө(nlgn), but it generally outperforms heapsort in practice because like insertion sort, it has tight code so the hidden constant factor in its running time is small. If you're implementing quicksort, choose a random element as the pivot. The average runtime of quicksort is O(n log n)! The constant in Big O notation can matter sometimes. That's why quicksort is faster than merge sort. Quicksort Worst Case - Correct Answers: Ө(n^2) on an input array if n numbers. InsertionSort asymptotic running time - Correct Answers: O(n^2) How does InsertionSort work? - Correct Answers: Express InsertionSort in pseudocode - Correct Answers: Analyse the performance of InsertionSort algorithm - Correct Answers: What is a sorting problem - Correct Answers: Input: A sequence of n numbers $(a1, a2, ..., an)$. Output: A permutation (reordering) $(a'1, a'2, ..., a'n)$ of the input sequence such that $a'1 ≤ a'2 ≤ ... ≤ a'n$ . The input sequence is usally an $n$ - element erray, although it may be represented in some other fashion, such as a linked list. Why is sorting considered the most fundamental problem in the study of algorithms - Correct Answers: Sometimes, an application inherently needs to sort infomration. Eg, producing bank statements. Algorithms often use sorting as a key subroutine. For example, a program that renders grpahical objects which are layered on top of each other might have to sort the objects according to an above relation so that it can draw these objects from bottom to top. We can prove a nontrivial lower bound for sorting (as we shall do in Ch8). Our best upper bounds match the lower bound asymptotically, and so we know that our sorting algorithms are asymptotically optimal. Moreover, we can use the lower bound for sorting to prove lower bounds for certain other problems. Many engineering issues come to the fore when implementing sorting algorithms. The fastest sorting program for a particular situation may depend on many factors, such as prior knowledge about the keys and satellite data, the memory hierarchy (caches and virtual memory) of the host computer, and the software environment. Many of these issues are best dealt with at the algorithm level, rather than by tweaking the code. Sorting in place - Correct Answers: Comparison sorts - Correct Answers: Determine the sorted order of an input array by comparing elements. Insertionsort Mergesort Heapsort Quicksort sorting algorithm - Correct Answers: Describes the method by which we determine the sorted order, regardless of whether we are sorting individual numbers or large records containing many bytes of satellite data. Thus, when focusing on the problem of sorting, we typically assume that the input consists only of numbers. Insertionsort - Correct Answers: A fas in-place sorting algorithm for small input sizes. O(n^2) a sorting algorithm sorts in place if - Correct Answers: only a constant number of elements of the input arrays are ever sorted outside the array. Algorithm - Correct Answers: A step-by-step procedure for solving a problem. A set of instructions for accomplishing a task. Binary Search Algorithm - Correct Answers: An algorithm that searches for a target value in a sorted list by checking at the midpoint and then repeatedly cutting the search section in half. Because we are cutting the list in half, we use log base 2 to count the number of steps binary search needs to search for something. Binary Search Worst Case - Correct Answers: logn Binary search needs log n operations to check a list of size n. In Big O notation this is O(logn) When you search for an element using simple search, in the worst case you might have to look at every single element. So, for a list of 8 numbers, you would have to check 8 numbers at most. For binary search you will have to check $logn$ elements in the worst case. Suppose n = 100 how many steps will it take to search this list? log100 (read log base 2) = 6.7 2^6.7 = 100 The exponent that we need to elevate 2 to reach 100 is 6.7. So, searching this list will, at worst take 6.7 steps. Linear time algorithm - Correct Answers: An algorithm that executes in O(n) time. The maximum number of guesses is the same as the size of the list. For example, simple search executes in O(n). logarithmic time - Correct Answers: In Big O notation where the time taken to run an algorithm increases or decreases in line with a logarithm. Time increases logarithmically. Big O Notation - Correct Answers: Big O notation is a special notation that tells you how fast an algorithm is. It counts the number of operations and it established a worst-case running time. ️ It does not tell you the speed in seconds. Instead, Big O lets you compare the number of operations. It tells you how fast the algorithm grows. A notation that expresses computing time (complexity) as the term in a function that increases most rapidly relative to the size of a problem. A way of expressing the worst-case run-time of an algorithm, useful for comparing the speed of two algorithms. A notation system used to classify algorithms (see algorithm analysis). The primary notation levels are: O(1), O(log N), O(N), O(N log N), and O(N^2) running time - Correct Answers: Measures how fast an algorithm is. Algorithm running times grow at different rates. The run time of two algorithms can grow at different rates. Algorithm speed isn't measured in seconds but in the growth of the number of operations. Instead, we talk about how quickly the run time of an algorithm increases as the size of the input increases. Run time of algorithms is expressed in Big O notation O(log n) is faster than O(n) is faster than O(n), but it gets a lot faster as the list of items you are searching grows. Some common Big O run times - Correct Answers: O(log n), also known as log time. Example: Binary search. O(n), also known as linear time. Example: Simple search. O(n * log n). Example: A fast sorting algorithm, such as quicksort O(n^2). Example: A slow sorting algorithm, like selection sort O(n!). Example: A really slow algorithm, like the travelling salesperson How do we measure algorithm speed? - Correct Answers: Algorithm times are measured in terms of growth of an algorithm., not seconds. Algorithm times are written in Big O notation. How do you compare floats and Double? - Correct Answers: You should use a logical operator, e.g. > or < to compare both Java float and Double variables, instead of = and ! = because they are not precise. Real numbers in Java - Correct Answers: Both Java float vs Double is used to represent real numbers in Java, i.e. numbers with fractions or decimal points. It's also best practice to choose a data type that takes less storage if it's sufficient for data you are storing, so choose float over double if you are happy with precision and range; double is more accurate then float, though. Double and float are not used to represent values that require very high precision. So, for instance, to store currency values, it is not a good idea to use double or float; instead, Java has a class, "Big Decimal", that specifies the exact number of digits following the decimal, including rounding up or down. What is the difference between arrays and linked lists? - Correct Answers: Arrays are data types arranged as a sequence, stored at one address. In a linked list, each item knows the address of the next item, so this data structure stores memory addresses linked together. Suppose you want to read the last item in a linked list. You cannot just read it, because you do not know what address it is at. Linked lists are great if you are going to read all the items one at a time. But if you are going to keep jumping around, linked lists are terrible. Arrays are different. You know the address for every item in your array. array - Correct Answers: An array is a series of memory locations - or 'boxes' - each of which holds a single item of data, but with each box sharing the same name. All data in an array must be of the same data type. The elements in an array are numbered. is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.[1][2][3] The simplest type of data structure is a linear array, also called one-dimensional array. Arrays are useful mostly because the element indices can be computed at run time. Among other things, this feature allows a single iterative statement to process arbitrarily many elements of an array. For that reason, the elements of an array data structure are required to have the same size and should use the same data representation. The set of valid index tuples and the addresses of the elements (and hence the element addressing formula) are usually,[3][5] but not always,[2] fixed while the array is in use. The term array is often used to mean array data type, a kind of data type provided by most high-level programming languages that consists of a collection of values or variables that can be selected by one or more indices computed at run-time. Array types are often implemented by array structures; however, in some languages they may be implemented by hash tables, linked lists, search trees, or other data structures. Linked lists - Correct Answers: an ordered set of data elements, each containing a link to its successor (and sometimes its predecessor). linked lists are collection of the nodes that contain information part and next pointer a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. can be used to implement other data structures a collection of nodes arranged so that each node contains a link to the next node in the sequence. Suppose you want to read the last item in a linked list. You cannot just read it, because you do not know what address it is at. Linked lists are great if you are going to read all the items one at a time. But if you are going to keep jumping around, linked lists are terrible. They can only do sequential access Why does it take O(n) time to insert an element into an array? - Correct Answers: Becasue, depending on where you wnat to inser it, you might have to try every single elemt in the lsit to find the right position. An n-element heap has a height: - Correct Answers: ⌊