Skip to content

Algorithms

CSE · Midterm · Summer 25

Paper 3 of 3Batch Batch-67 · MD. ABDUR RAFISwitch

Batch Batch-67

Paper 3 of 3

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 & Engineering Mid Examination, Summer 2025 Course Code: CSE 213, Course Title: Algorithms Level: 1 Term: 1 Batch: Batch-67 Time: 01:30 Hrs Marks: 25 Answer ALL Questions 1. a) Analyze the time complexity of this loop. (2.5) [CO1] void CheckFunction(int N) { for (int i = 1; i <= N; i++) { int j = 1; while (j < N) { printf("i = %d, j = %d\n", i, j); j = j * 2; }}} b) Analyze the time complexity of this loop. (2.5) for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { printf("i = %d, j = %d\n", i, j);}} 2. a) In the kingdom of Numeria, the ancient Guardian protects a treasure that only opens for a prime number-a number that cannot be divided evenly by any number other than 1 and itself. The Guardian grows old and asks you, the kingdom's young mathematician, to uncover the secret. Write pseudocode to determine whether a given number is prime. (3) [CO3] b) During semester exams, the university assigns seat numbers based on student IDs. These IDs are stored in a sorted list for efficient processing. The sorted list of student IDs is as follows: [1003, 1010, 1015, 1020, 1024, 1028, 1030, 1045] A student with ID 1024 arrives and wants to know his seat location. Now, simulate the best possible searching algorithm. How many total comparisons needed for your technique? Why sometimes linear search can be better for a small target index? (4) c) In the city of Dhaka, a famous activist gives a riddle to scholars: "There lies an array of N unique sacred stones. - If one sorts them using Merge Sort, the total number of comparisons is C1. - If sorted with Quick Sort using the last element as pivot, the expected number of comparisons is C2. - Given a certain arrangement, C2 becomes exactly 1.5x C1. Determine the maximum possible number of elements N for which this is true?" Your job is to analytically find the largest integer N such that: C2 = 1.5 x C1 (3) 3. a) Sumaiya, a second-year CSE student, visits the Ekushey Book Fair at Bangla Academy with a budget of 6taka. She wants to buy some books. Each book has a price and a rewards points. She wants to maximize the reward points within her 6-taka budget. Here are the available books: Book | Price-tk | Reward points A-Programming Tricks | 2 | 4 B-Bangla Poetry | 3 | 5 C-Short Story Book | 4 | 6 D-Data Structure | 2 | 3 E- Algorithms | 1 | 1 F-Discreate Maths | 3 | 5 Now your task is to help Sumaiya select the combination of books with maximum reward points without exceeding 6 taka budget. (5) [CO2] b) Once upon a time, there were two friends - Sender and Receiver. They lived far apart, and sending messages was very expensive because they had to pay 1 Taka for each character they sent. One day, they discovered the Huffman Coding Algorithm, which can reduce the message size by encoding frequently used characters with shorter codes. Now, Sender wants to send the following message: aaaaaaaaabbbbbccceefdddddddddd Your Task: 1. Encode the entire message using your generated Huffman codes. 2. Calculate the total cost if sending 1-bit costs 1 Taka? 3. Calculate the original cost without compression (considering 1 character = 8 bits). (3+1+1)