Skip to content

Algorithms

CSE · Midterm · Fall 24

Batch 65

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 Faculty of Science & Information Technology Department of Computer Science and Engineering Midterm Examination, Fall 2024 Course Code: CSE213, Course Title: Algorithms Level: 2 Term: 1 Batch: 65 Time: 01:30 Hours 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) Discuss the complexity of the following code snippet: int main() { int i, j; scanf("%d", &N); int count = 0; for (int i = N; i > 0; i /= 2) for (int j = 0; j < i; j++) count++; } [2.5] [CO1] b) Write an algorithm to swap two given numbers without using a temporary variable. Explain the time complexity of your generated algorithm. [2.5] 2. Describe the below inquiries in case of the binary search algorithm: I. Outline the main steps involved in performing the binary search algorithm. II. What is the time complexity of binary search in the worst-case scenario? III. Describe how the 'divide and conquer' approach applies to binary search. IV. If you have an ordered list containing 128 elements, what is the maximum number of steps needed to find a specific element using binary search? V. Can binary search be applied to an unordered list? Justify your answer. [5] [CO1] 3. Alex is organizing a gaming tournament and needs to sort the scores of the participants to execute the final rankings. The scores are currently in random order: [150, 92, 185, 120, 160] Alex decides to use the quicksort algorithm to sort these scores in ascending order. He chooses the first element as the pivot for simplicity and needs to sort the list step by step. How can you help Alex to sort the scores? [5] [CO2] 4. Harun and Biplob are good friends. They usually chat with each other regularly. Once Harun sent a greeting 'Hi Friend' to Biplob. Someone tried to snip that message but it was encrypted. However, Huffman coding was used for the encryption. Demonstrate the encrypted code for the transmitted message. [5] [CO2] 5. Sarah is a treasure hunter, and she has discovered an ancient vault filled with precious gems. However, her backpack has a weight limit of 30 kg, and she must choose wisely from the following gems, each with a specific weight and estimated market value: Gem | Weight (kg) | Value ($) Ruby | 10 | 60,000 Sapphire | 15 | 90,000 Emerald | 5 | 50,000 Diamond | 12 | 100,000 Sarah can take whole gems or fractions of them, as the gems can be cut without losing value. How can she organize her backpack to maximize the total value of the gems she can carry without exceeding the 30 kg weight limit? [5] [CO3]