[go: up one dir, main page]
Scribd
Upload
1 views3 pages

Chapter 2

Chapter 2 discusses various algorithms and their performance analyses, including bubble sort, array summation, and linear search, highlighting their time and space complexities. It also includes programming exercises for implementing algorithms such as swapping variables, checking for prime numbers, and solving the Towers of Hanoi problem. The document emphasizes the efficiency of certain algorithms for small to medium datasets while noting the limitations of others for larger datasets.

Uploaded by

cloudstudyjam2005
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
1 views3 pages

Chapter 2

Chapter 2 discusses various algorithms and their performance analyses, including bubble sort, array summation, and linear search, highlighting their time and space complexities. It also includes programming exercises for implementing algorithms such as swapping variables, checking for prime numbers, and solving the Towers of Hanoi problem. The document emphasizes the efficiency of certain algorithms for small to medium datasets while noting the limitations of others for larger datasets.

Uploaded by

cloudstudyjam2005
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Chapter 2 – Problem Solving and Algorithms

Numerical Problems
1 Perform analysis on bubble sort
Time Complexity: O ( n2 )
Space Complexity: O ( 1 )
Bubble Sort is generally not used in practice because it is very inefficient for large
datasets.
2 Perform analysis on the summation of an array
Time Complexity: O ( n )
Space Complexity: O ( 1 )
The performance of this algorithm is generally very good, especially for small to
medium-sized arrays.
3 Perform analysis of finding the maximum of an array
Time Complexity: O ( n )
Space Complexity: O ( 1 )
The performance of this algorithm is generally very good, especially for small to
medium-sized arrays.
4 Let t(n) = 7 n3 +6 n2+5 , prove that this is O(n3 )
t(n) = 7 n3 +6 n2+5 ≤ 7 n3 +6 n 3+5 n3=18 n3 ≈ O ( n3 )

5 Let t ( n )=7 n2 +6 n , what is Big-Omega notation?


t ( n )=7 n2 +6 n ≤ 7 n2 +6 n 2=12n 2 ≈ O ( n2 )

6 Perform asymptotic analysis of linear search


Time Complexity: O ( n )
Space Complexity: O ( 1 )
The performance of linear search is generally good for small to medium-sized arrays.
However, for very large arrays, the time required to perform the search may become
a bottleneck.

Programming Exercise
1 Write an algorithm for swapping two variables without an intermediate variable.
1. a = a + b
2. b = a - b
3. a = a - b

At step 2 and step 3, one could notice that the values in a and b are swapped without
intermediate variable.
2 Write an algorithm for finding a number prime or not.
Input: n, number
Output: True (If n is prime number) or False (If n is not prime number)
if n < 2:
return False
if n = 2 or 3:

COPYRIGHT © 2023 PEARSON INDIA EDUCATION SERVICES PVT. LTD


1
return True
if n % 2 == 0 or n%3 == 0:
return False
for i∈ [ 5 , √ n ] do:
if i % 2 != 0:
if n % i == 0:
return False

3 Read a set of employees and their year of birth. Write an algorithm to print the
employees who were born in odd years.
1. Read in the set of employees and their year of birth.
2. For each employee, check if their birth year is odd.
3. If the birth year is odd, print the employee's name and birth year.
4 Write an algorithm to check the number Armstrong number or not.
sum = 0
num_digits = len(str(n))
for digit in str(n):
sum += int(digit) ** num_digits
if sum == n:
return True
else:
return False
5 Write an algorithm to solve the towers of Hanoi problem.
1. If there is only one disk, move it from the source rod to the destination rod.
2. Otherwise, move n-1 disks from the source rod to the auxiliary rod, using the
destination rod as the auxiliary.
3. Move the remaining disk from the source rod to the destination rod.
4. Move the n-1 disks from the auxiliary rod to the destination rod, using the source
rod as the auxiliary.
6 Write a recursive algorithm to find the sum of an array.
def array_sum(arr, index):
if index < 0:
return 0
return arr[index] + array_sum(arr, index - 1)
7 Write an algorithm for solving a binary search problem.
def binary_search(arr, value, first, last):
if first > last:
return -1

middle = (first + last) // 2


if arr[middle] == value:
return middle
elif arr[middle] > value:
return binary_search(arr, value, first, middle - 1)
else:
return binary_search(arr, value, middle + 1, last)
8 Write an algorithm to solve a cashier problem. A cashier problem returns the
minimum number of coins for a given request.

COPYRIGHT © 2023 PEARSON INDIA EDUCATION SERVICES PVT. LTD


2
def minimum_coins(total_amount, denominations):
coin_counts = [0] * len(denominations)
denominations.sort(reverse=True)

for i in range(len(denominations)):
num_coins = total_amount // denominations[i]
coin_counts[i] = num_coins
total_amount -= denominations[i] * num_coins

if total_amount == 0:
return coin_counts

return “Not possible with the given values”


9 Write an algorithm for finding a perfect number.
sum = 0
for i in range(1, n // 2 + 1):
if n % i == 0:
sum += i
return sum == n
10 Solve the 3n + 1 problem to generate a sequence of numbers.
sequence = [n]
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n=3*n+1
sequence.append(n)
return sequence

COPYRIGHT © 2023 PEARSON INDIA EDUCATION SERVICES PVT. LTD


3

You might also like