PART A (Short Answer Questions)
1. Solving a jigsaw puzzle without reference using trial and error
To solve a jigsaw puzzle without a reference picture using trial and error:
Sort pieces by edge type (border vs interior)
Start by assembling the border using pieces with straight edges
Group remaining pieces by color or pattern similarities
Try fitting pieces together based on shape and color matches
If a piece doesn't fit, set it aside and try another
Continue this process systematically until all pieces are placed
2. Python code to check if input is numeric
input_str = "12345"
if input_str.isdigit():
print("The input is numeric")
else:
print("The input is not numeric")
3. Flowchart for Fibonacci sequence
[Textual representation since I can't draw]
START
│
▼
Input n (number of terms)
│
▼
Initialize a=0, b=1, count=0
│
▼
While count < n:
│
├─► Print a
│ │
│ ▼
│ next = a + b
│ │
│ ▼
│ a = b
│ │
│ ▼
│ b = next
│ │
│ ▼
│ count += 1
│
▼
END
4. Algorithm to check for palindrome
1. Start
2. Read input number
3. Initialize reverse = 0 and temp = input number
4. While temp > 0:
a. remainder = temp % 10
b. reverse = (reverse * 10) + remainder
c. temp = temp // 10
5. If input number equals reverse:
a. Print "Palindrome"
Else:
a. Print "Not Palindrome"
6. End
5. Code output prediction
(i) -10-12-14-16-18
(ii)
10
8
6
4
2
0
(iii) 162 (evaluated as 2*(3(22)) = 2*(3^4) = 2*81 = 162
6. Python program for sum of even numbers
numbers = list(map(int, input("Enter numbers separated by space: ").split()))
sum_even = sum(num for num in numbers if num % 2 == 0)
print("Sum of even numbers:", sum_even)
7. Motivation for randomized approach
Randomized approaches are motivated by:
Avoiding worst-case scenarios in deterministic algorithms
Providing average-case efficiency guarantees
Simplifying complex deterministic algorithms
Being effective for parallel and distributed computing
Useful when input distribution is unknown or complex
Often providing simpler and more elegant solutions
8. Algorithm for 4-digit password recovery
1. Start
2. Initialize attempt = 0000
3. While attempt <= 9999:
a. Try login with attempt
b. If successful:
i. Return attempt as password
ii. Exit
c. Increment attempt by 1
4. If no match found after 10000 attempts, return "Password not found"
5. End
PART B (Detailed Questions)
Module 1
9a. Backtracking for Sudoku
Backtracking for Sudoku works by:
Find an empty cell in the grid
Try digits 1-9 in the cell
For each digit, check if it's valid (no conflict in row, column, or 3x3 box)
If valid, place the digit and recursively attempt to solve the rest
If recursion leads to solution, return success
If no digit works, backtrack (undo placement) and try next possibility
Repeat until grid is filled or all possibilities exhausted
9b. Heuristics for restaurant selection
Using heuristics to find the best restaurant:
Proximity heuristic: Prioritize restaurants within a certain radius
Rating heuristic: Consider only restaurants with ratings above a threshold
Price heuristic: Filter by affordable price range
Cuisine preference: Prioritize preferred cuisine types
Wait time heuristic: Estimate or check current wait times
Popularity heuristic: Consider number of customers as a quality indicator
Combination heuristic: Weighted combination of above factors
10a. Means-Ends Analysis for campus software
Applying Means-Ends Analysis:
Define goals: Student management, course scheduling, attendance tracking, etc.
Current state assessment: Identify existing systems and pain points
Identify differences: Gap between current and desired system
Select operators:
Database design for student records
Scheduling algorithms for courses
Authentication system for security
Reporting modules for analytics
Apply operators: Implement solutions to reduce differences
Evaluate progress: Test each component against goals
Iterate: Refine based on feedback until all goals are met
10b. Python program for radius calculation
import math
def calculate_radius(area):
return math.sqrt(area / math.pi)
circle_area = float(input("Enter area of circle: "))
radius = calculate_radius(circle_area)
print(f"Radius of circle: {radius:.2f}")
Module 2
11a. Pseudocode for grading system with rounding
FUNCTION calculateGrade(marks):
IF marks >= 90:
base_grade = 'A'
ELSE IF marks >= 80:
base_grade = 'B'
ELSE IF marks >= 70:
base_grade = 'C'
ELSE IF marks >= 60:
base_grade = 'D'
ELSE IF marks >= 50:
base_grade = 'E'
ELSE:
RETURN 'F'
IF marks >= 50:
next_multiple = ((marks // 10) + 1) * 10
IF (next_multiple - marks) < 3:
RETURN next higher grade from base_grade
ELSE:
RETURN base_grade
ELSE:
RETURN 'F'
END FUNCTION
11b.Algorithm to Identify Optimal Delivery Times
Problem Statement:
Identify and print delivery times (in minutes) that are:
Divisible by 6 (optimal durations)
Not divisible by 4 (avoid complex scheduling)
Algorithm (Pseudocode):
FUNCTION findOptimalDeliveries(delivery_times):
optimal_times = EMPTY_LIST
FOR time IN delivery_times:
IF time % 6 == 0 AND time % 4 != 0:
ADD time TO optimal_times
RETURN optimal_times
END FUNCTION
12a. Pseudocode for min/max in list
FUNCTION findMinMax(numbers):
IF length of numbers == 0:
RETURN error
min_num = numbers[0]
max_num = numbers[0]
FOR i FROM 1 TO length(numbers)-1:
IF numbers[i] < min_num:
min_num = numbers[i]
IF numbers[i] > max_num:
max_num = numbers[i]
RETURN (min_num, max_num)
END FUNCTION
12b. Pseudocode for factorial using for loop
FUNCTION factorial(n):
IF n < 0:
RETURN error
result = 1
FOR i FROM 1 TO n:
result = result * i
RETURN result
END FUNCTION
Module 3
13a. Recursive Fibonacci generator
def fibonacci(n):
if n <= 0:
return []
elif n == 1:
return [0]
elif n == 2:
return [0, 1]
else:
seq = fibonacci(n-1)
seq.append(seq[-1] + seq[-2])
return seq
n = int(input("Enter number of terms: "))
print(f"First {n} Fibonacci numbers:", fibonacci(n))
13b. Right triangle checker
def is_right_triangle(a, b, c):
sides = sorted([a, b, c])
return abs(sides[0]**2 + sides[1]**2 - sides[2]**2) < 1e-6
a, b, c = map(float, input("Enter three sides: ").split())
if is_right_triangle(a, b, c):
print("These sides form a right triangle")
else:
print("These sides do not form a right triangle")
14a. Recursive LCM using GCD
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
def lcm(a, b):
return (a * b) // gcd(a, b)
a, b = map(int, input("Enter two numbers: ").split())
print(f"LCM of {a} and {b} is {lcm(a, b)}")
14b. Text reorganization program
def reorganize_text(sentence):
capitals = []
lowers = []
digits = []
specials = []
for char in sentence:
if char.isupper():
capitals.append(char)
elif char.islower():
lowers.append(char)
elif char.isdigit():
digits.append(char)
else:
specials.append(char)
return ''.join(capitals + lowers + digits + specials)
input_text = input("Enter a sentence: ")
print("Reorganized text:", reorganize_text(input_text))
Module 4
15a. Divide and Conquer for two lowest rates
Algorithm:
If array has only 2 elements, return their sum
If array has 3 elements, find the 2 smallest and return sum
Else:
a. Split array into two halves
b. Recursively find two smallest in left half (L1, L2)
c. Recursively find two smallest in right half (R1, R2)
d. Merge results by comparing the four values
e. Return sum of the two smallest from the merged set
Example:
Input: [15, 10, 8, 12, 20, 5]
Split: [15,10,8] and [12,20,5]
Left half: min1=8, min2=10
Right half: min1=5, min2=12
Compare all four: min1=5, min2=8
Return sum: 13
15b. Greedy vs Dynamic Programming
Greedy Approach:
Makes locally optimal choice at each step
Never reconsider choices
Generally faster but may not reach global optimum
Examples: Dijkstra's algorithm, Huffman coding
Dynamic Programming:
Breaks problem into overlapping subproblems
Stores solutions to subproblems (memoization)
Guarantees optimal solution
Examples: Fibonacci sequence, 0/1 knapsack
Comparison:
DP is exhaustive, Greedy is heuristic
DP has higher time/space complexity
Greedy is simpler to implement
DP works for more problem types
16a. Memoization vs Tabulation for Fibonacci
Memoization (Top-down):
Recursive approach
Stores computed values when first calculated
Only computes needed values
Example:
python
memo = {0:0, 1:1}
def fib_memo(n):
if n not in memo:
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
Tabulation (Bottom-up):
Iterative approach
Builds table from base cases up
Computes all values up to n
Example:
python
def fib_tab(n):
table = [0, 1]
for i in range(2, n+1):
table.append(table[i-1] + table[i-2])
return table[n]
16b. Greedy algorithm for maximum tasks
Algorithm:
Sort the tasks by increasing duration
Initialize count = 0 and total_time = 0
For each task in sorted order:
a. If total_time + task duration <= time_limit:
i. Add task duration to total_time
ii. Increment count
b. Else:
i. Break loop
Return count
Reasoning:
Sorting ensures we try shortest tasks first (greedy choice)
This maximizes number of tasks we can fit
Each step is locally optimal (shortest remaining task)
The solution is globally optimal for this problem
