Skip to content

Algorithms

CSE · Midterm · Fall 22

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

Read the questions as text

Read off the PDF by AI, so it may have mistakes. The PDF is the original.

Daffodil International University Department of Computer Science and Engineering Faculty of Science & Information Technology Midterm Examination, Fall 2022 Course Code: CSE214 Course Title: Algorithm Level: 2 Term: 1 Batch: 58, 59, Old Syllabus Time: 1.5 Hrs Marks: 25 Answer ALL Questions [The figures in the right margin indicate the full marks and corresponding course outcomes. All portions of each question must be answered sequentially.] 1. a) Analyze the Big-Oh(O) complexity of the following two code snippets: i) for( i = 1 ; i < n ; i++ ) { for( j = 1 ; j <= i ; j++ ) { printf("Algorithm is fun"); } printf("\n"); } [2] ii) for( i = 1 ; i <= n ; i++ ) for ( j = 1 ; j <= n ; j++ ) for ( k = 1 ; k <= j ; k++ ) printf("I am a genius!\n"); for( i = 1 ; i <= n ; i++ ) printf("I am again a genius!\n"); [2] b) Consider the following algorithm (on the next page) and the given array. Now run the algorithm on the array and demonstrate how the array will be updated at each iteration. Show every single step. A[5] = {4, 7, 2, 6, 8} and n=5 [3] for( i=0; i<n/2; i++) { for( j=1; j<=i; j++) { k=A[i]; A[i]=A[n-i-1]; A[n-i-1]=k; } } 2. Identify which searching algorithm you will be using in each of the following scenarios? Explain your choice (in no more than 3 lines per scenario) i. You have an array of 10 million floating point numbers sorted in descending order. You want to find a number from this array – let's call this operation a query. There is only a single query in this scenario. ii. Now, you have the same array of same size but this time they are in ascending order. Again, there will only be a single query. iii. For the third scenario, the numbers are unsorted. Again, there will be a single query only. iv. For the fourth scenario, the numbers are unsorted and you have to make 1 million different queries. [6] 3. Both merge sort and quick sort algorithms follow divide and conquer approach and their run time complexity in average case is O(n log n). Considering the following list, compare the performance of merge sort and quick sort algorithm for sorting the following list. [ 7 6 5 4 3 2 1 ] [5] 4. Suppose you have a file containing the following characters with the corresponding frequency. A | B | C | D | E | F 45 | 13 | 12 | 16 | 9 | 5 If you encode the file with the following codewords identify the size of your file in terms of required bits? A | B | C | D | E | F 0000 | 0001 | 0010 | 0011 | 0100 | 0101 Now it is possible to encode the file with fewer number of bits. Build the solution. Develop the solution step by step and finally construct the new code words for each character. [7]