Starting from:
$30
CSL101-Assignment 2
Write a program to calculate the value of nCr. nCr is the number of ways of selecting r items given n items. The recurrence for calculating nCr is given by:
nCr = n-1Cr + n-
1Cr-1
Assume that n = r in this question. The program should make use of nCr_helper ( ) function.
Q.2 Write a function that takes two positive integers n and k as input. Find the sum: nC0 + nC1 + nC2 + nC3 + . . . + nCk.
The program should consist of two user-defined functions. One function to calculate the sum of series which subsequently takes the help of fact_helper ( ) function. Do not use math.h library functions.
Q.3 Goldbach conjecture states that every even number greater than 2 can be expressed as a sum of two primes. Given a number ‘N’ as input, write a program to check whether the Goldbach conjecture holds for ‘N’, and print the corresponding two primes adding to N. Use prime_helper ( ) function taken in class.
Q.4 A Fibonacci prime series is a series made of those numbers in the Fibonacci series which are prime. In main ( ), take an integer ‘n’ as the input and print n terms of Fibonacci prime series. Use prime_helper ( ) function taken in class.
Q.5 A number is said to be perfect if it is the sum of all its factors (except itself). For example, 6 has factors 1, 2, 3 and 1 + 2 + 3 = 6, hence it is perfect. Also, 28 = 1 + 2 + 4 + 7 + 14 is perfect. Write a C function checkPerfect ( ) which returns 1 if n is perfect number and 0 if it is not.
Q.6 Given an integer n as input, print smallest number x such that x = n and x is a palindrome. You have done a question to find whether a number is a palindrome or not in the previous assignment. Using the same logic, write a function Palindrome_helper (int p) such that it returns whether a number p is a palindrome or not? Format: int Palindrome_helper (int p)
{
// write your logic here
} main ( )
{
/* Read n;
Call Palindrome_helper ( ) to check smallest number x such that smallest x = n and x is a palindrome */ }
Q.7 Consider the Peasants' Algorithm for multiplication of two positive integers. It works in the following manner:
• Write the two numbers in two columns. Keep updating according to the following procedure until the number in the first (i.e., left) column becomes 1.
• Halve the number in the first column (integer division), double the number in the second column.
• In the end, sum up all the numbers in the second column, for which, the corresponding number in the first column is odd.
Example of multiplication using Peasants’ algorithm: 13 x 8:
13 8 ← 6 16
3 32 ←
1 64 ←
Answer: 64 + 32 + 8 = 104
Write a function to calculate multiplication using the Peasants’ algorithm.
Q.8 Write a function to check if a given input number is a jumping number. A number is called jumping number if all adjacent digits in it differ by 1. All single digits are considered as jumping numbers. Some examples of jumping numbers are 0, 5, 10, 12, 78, 567, 101.
Q.9 Write a program to compute F (x, y) where F (x, y) = F (x-y, y) + 1 if y <= x and F (x, y) = 0 if x < y
Q.10 Write a recursive function printNum ( ) that prints any given number by putting spaces between successive characters to be printed. For example: printNum (12) prints 1 2 printNum (327) prints 3 2 7 printNum (-912) prints – 9 1 2
Q.11 Write a recursive function that returns a reverse of a number passed as a parameter.
Q.12 Write a recursive function that returns the status (as 0 or 1) after checking the primarily of a number.
Q.13 Given a positive integer n and a digit d, return the count of the occurrences of the digit d in the number n. For example, a count of 7 in 7177 yields 3. Use a recursive function.
Q.14 The Ackerman recursion can be described as below: A (0, n)
= n + 1
A (m + 1, 0) = A (m, 1)
A (m + 1, n + 1) = A (m, A (m + 1, n))
Given m and n as input, write a program to calculate A(m, n), using recursion.
Q.15 The Taylor’s series for cos(x) is given as:
∞ (−1)𝑛𝑥2𝑛 𝑥2 𝑥4 𝑥6
cos(x) = ∑ = 1 - + - +…
𝑛=0 (2𝑛)! 2! 4! 6!
The program to calculate cos(x) should use three recursive functions: float power
(float x, float n); float fact (float n); float cosine (float x, float n);
Q.16 Write a program to swap the second smallest and second largest element in the array.
Q.17 Given a sorted array of n numbers and another number x, determine whether or not there exist two elements in the input array whose sum is exactly x. Try to write an iterative and recursive solution both.
Q.18 Write a program that places kth element of an array at position 1, the (k + 1) th element in position 2, etc. The original 1st element is placed at (n – k + 1) and so on. The ‘k’ should be user input.
Q.19 Find all the peak elements in an array of integers. An element in an array is called a peak element if it is greater than its adjacent neighbours. Assume that the array contains multiple peak elements. The first and the last element of the array have only one adjacent neighbor. For example:
A [ ] = {50, 80, 70, 90, 100, 80,50,20}, then peak elements are 80, 100.
A [ ] = {100, 80, 70, 90, 60, 65}, then peak elements are 100, 90, and 65.
Q.20 Write a program that rearranges the elements of an array so that all those originally stored at odd indices are placed before those at even indices. Consider the array index starts from 1.
For example, the array
10 20 30 40 50 60 70 80
would be transformed to
10 30 50 70 20 40 60 80
Q.21 Given a 1-D array, write a program that counts the number of even-spaced inversions in the array. We call a pair (i, j) as an even-spaced inversion when both the following conditions satisfy:
1. (i, j) is an inversion, which means arr [i] arr [j] where i < j, and
2. the difference between i and j is even.
Q.22 Given an array A [ ] of size n integers, create an another array output [ ] such that output [i] is equal to the product of all elements of A except A [i]. For example, A [ ] = {1, 2, 3, 4, 5}, then output [ ] = {120, 60, 40, 30, 24}.
Q.23 Given a sorted array A of integers of size N and two integers viz., left and right. Write a recursive function to count the number of integers between left and right (inclusive of both) present in array A. For example, A [ ] = {10, 20, 25, 30, 45, 50, 60, 80, 100}, left = 30, and right = 70, then the output = 4.
Q.24 Consider a 1-D array of integers 0’sand 1’s only. Write a C function takes as input an array having n elements and then prints the length of the longest sequence of 1’s. For example, if array is A [ ] = {0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1}, the length of longest run of 1’s is 4 (underlined).
Q.25 Write a function that counts the number of unique numbers present in a 1-D array. For example, for an array A [ ] = {1, 2, 3, 4, 5, 4, 3, 2} as input, the output is 5.
Q.26 Write a function compact ( ) which takes as parameters an array of integers and its length. The function should modify the array so that all consecutive occurrences of the same integer are replaced by a single occurrence of that integer. The function should return the length of this new array.
Example: When called with the array {1, 1, 1, 2, 2, 1, 2, 3, 3, 1, 1}, your function should modify the array to {1, 2, 1, 2, 3, 1} and return 6.
Q.27 Given an unsorted array A of size n that may contain duplicates and a number k < n,
write a function that returns “1” if an array contains at least one duplicate pair within a distance of k, i.e. there exists i, j ϵ [0, n − 1] such that A [i] = A [j] and |i − j| < k.
Q.28 Write a function that accepts as argument an array A of integers together with its size n and a non-negative integer k. The function should create another array, which is obtained by cyclically shifting the input array A by k positions to the right. For example, if array A
= {2, 4, 6, 1, 3, 9, 5} of size n = 7 and k = 3, the function should create another array B
=
{3, 9, 5, 2, 4, 6, 1}.
Q.29 Given a matrix of N*N order. Write a program to interchange the diagonals of the matrix. For example, Input: { {1, 2, 3}, Output: { {3, 2, 1},
{4, 5, 6}, {4, 5, 6},
{7, 8, 9} } {9, 8, 7} }
Q.30 Write a function to reverse the order of the elements in an M*N array of integers, so that X [0][0] is now at X [M-1][N-1], X [0][1] is now at X [M-1][N-2], and so on. Input: { {0, 1, 2, 3, 4}, Output: { {19, 18, 17, 16,
15},
{5, 6, 7, 8, 9}, {14, 13, 12, 11, 10},
{10, 11, 12, 13, 14}, {9, 8, 7, 6, 5},
{15, 16, 17, 18, 19} } {4, 3, 2, 1, 0} }
Solve the same problem using loops and recursion both.
Q.31 Write a function that takes an input parameter a string, and returns the first nonrepeating character in it. For example, if the input string is “Malayalam”, then the output should be ‘y’ and if the input string is “Telugu”, then the output should be ‘T’.
Q.32 Write a function strend (s, t), which returns 1 if the string t occurs at the end of the string s, and zero otherwise.
Q.33 Write a program that encodes English-language word into pig-Latin. To translate an English word into a pig-Latin word, place the first letter of the word at the end of the word and add the letters “ay” at the end. For example: word “jump” becomes “umpjay”, word “the” becomes “hetay” and the word “computer” becomes “omputercay”. Do not use string.h library functions.
Q.34 Write a program that finds out the initials of the words in a string, where a single blank space separates two consecutive words in the string. For example, if the input string is “Sacred Games”, the output will be “S.G.”.
Q.35 Write a function squeeze (S1, S2) that deletes each character in the string S1 that matches any character in the string S2.
nCr = n-1Cr + n-
1Cr-1
Assume that n = r in this question. The program should make use of nCr_helper ( ) function.
Q.2 Write a function that takes two positive integers n and k as input. Find the sum: nC0 + nC1 + nC2 + nC3 + . . . + nCk.
The program should consist of two user-defined functions. One function to calculate the sum of series which subsequently takes the help of fact_helper ( ) function. Do not use math.h library functions.
Q.3 Goldbach conjecture states that every even number greater than 2 can be expressed as a sum of two primes. Given a number ‘N’ as input, write a program to check whether the Goldbach conjecture holds for ‘N’, and print the corresponding two primes adding to N. Use prime_helper ( ) function taken in class.
Q.4 A Fibonacci prime series is a series made of those numbers in the Fibonacci series which are prime. In main ( ), take an integer ‘n’ as the input and print n terms of Fibonacci prime series. Use prime_helper ( ) function taken in class.
Q.5 A number is said to be perfect if it is the sum of all its factors (except itself). For example, 6 has factors 1, 2, 3 and 1 + 2 + 3 = 6, hence it is perfect. Also, 28 = 1 + 2 + 4 + 7 + 14 is perfect. Write a C function checkPerfect ( ) which returns 1 if n is perfect number and 0 if it is not.
Q.6 Given an integer n as input, print smallest number x such that x = n and x is a palindrome. You have done a question to find whether a number is a palindrome or not in the previous assignment. Using the same logic, write a function Palindrome_helper (int p) such that it returns whether a number p is a palindrome or not? Format: int Palindrome_helper (int p)
{
// write your logic here
} main ( )
{
/* Read n;
Call Palindrome_helper ( ) to check smallest number x such that smallest x = n and x is a palindrome */ }
Q.7 Consider the Peasants' Algorithm for multiplication of two positive integers. It works in the following manner:
• Write the two numbers in two columns. Keep updating according to the following procedure until the number in the first (i.e., left) column becomes 1.
• Halve the number in the first column (integer division), double the number in the second column.
• In the end, sum up all the numbers in the second column, for which, the corresponding number in the first column is odd.
Example of multiplication using Peasants’ algorithm: 13 x 8:
13 8 ← 6 16
3 32 ←
1 64 ←
Answer: 64 + 32 + 8 = 104
Write a function to calculate multiplication using the Peasants’ algorithm.
Q.8 Write a function to check if a given input number is a jumping number. A number is called jumping number if all adjacent digits in it differ by 1. All single digits are considered as jumping numbers. Some examples of jumping numbers are 0, 5, 10, 12, 78, 567, 101.
Q.9 Write a program to compute F (x, y) where F (x, y) = F (x-y, y) + 1 if y <= x and F (x, y) = 0 if x < y
Q.10 Write a recursive function printNum ( ) that prints any given number by putting spaces between successive characters to be printed. For example: printNum (12) prints 1 2 printNum (327) prints 3 2 7 printNum (-912) prints – 9 1 2
Q.11 Write a recursive function that returns a reverse of a number passed as a parameter.
Q.12 Write a recursive function that returns the status (as 0 or 1) after checking the primarily of a number.
Q.13 Given a positive integer n and a digit d, return the count of the occurrences of the digit d in the number n. For example, a count of 7 in 7177 yields 3. Use a recursive function.
Q.14 The Ackerman recursion can be described as below: A (0, n)
= n + 1
A (m + 1, 0) = A (m, 1)
A (m + 1, n + 1) = A (m, A (m + 1, n))
Given m and n as input, write a program to calculate A(m, n), using recursion.
Q.15 The Taylor’s series for cos(x) is given as:
∞ (−1)𝑛𝑥2𝑛 𝑥2 𝑥4 𝑥6
cos(x) = ∑ = 1 - + - +…
𝑛=0 (2𝑛)! 2! 4! 6!
The program to calculate cos(x) should use three recursive functions: float power
(float x, float n); float fact (float n); float cosine (float x, float n);
Q.16 Write a program to swap the second smallest and second largest element in the array.
Q.17 Given a sorted array of n numbers and another number x, determine whether or not there exist two elements in the input array whose sum is exactly x. Try to write an iterative and recursive solution both.
Q.18 Write a program that places kth element of an array at position 1, the (k + 1) th element in position 2, etc. The original 1st element is placed at (n – k + 1) and so on. The ‘k’ should be user input.
Q.19 Find all the peak elements in an array of integers. An element in an array is called a peak element if it is greater than its adjacent neighbours. Assume that the array contains multiple peak elements. The first and the last element of the array have only one adjacent neighbor. For example:
A [ ] = {50, 80, 70, 90, 100, 80,50,20}, then peak elements are 80, 100.
A [ ] = {100, 80, 70, 90, 60, 65}, then peak elements are 100, 90, and 65.
Q.20 Write a program that rearranges the elements of an array so that all those originally stored at odd indices are placed before those at even indices. Consider the array index starts from 1.
For example, the array
10 20 30 40 50 60 70 80
would be transformed to
10 30 50 70 20 40 60 80
Q.21 Given a 1-D array, write a program that counts the number of even-spaced inversions in the array. We call a pair (i, j) as an even-spaced inversion when both the following conditions satisfy:
1. (i, j) is an inversion, which means arr [i] arr [j] where i < j, and
2. the difference between i and j is even.
Q.22 Given an array A [ ] of size n integers, create an another array output [ ] such that output [i] is equal to the product of all elements of A except A [i]. For example, A [ ] = {1, 2, 3, 4, 5}, then output [ ] = {120, 60, 40, 30, 24}.
Q.23 Given a sorted array A of integers of size N and two integers viz., left and right. Write a recursive function to count the number of integers between left and right (inclusive of both) present in array A. For example, A [ ] = {10, 20, 25, 30, 45, 50, 60, 80, 100}, left = 30, and right = 70, then the output = 4.
Q.24 Consider a 1-D array of integers 0’sand 1’s only. Write a C function takes as input an array having n elements and then prints the length of the longest sequence of 1’s. For example, if array is A [ ] = {0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1}, the length of longest run of 1’s is 4 (underlined).
Q.25 Write a function that counts the number of unique numbers present in a 1-D array. For example, for an array A [ ] = {1, 2, 3, 4, 5, 4, 3, 2} as input, the output is 5.
Q.26 Write a function compact ( ) which takes as parameters an array of integers and its length. The function should modify the array so that all consecutive occurrences of the same integer are replaced by a single occurrence of that integer. The function should return the length of this new array.
Example: When called with the array {1, 1, 1, 2, 2, 1, 2, 3, 3, 1, 1}, your function should modify the array to {1, 2, 1, 2, 3, 1} and return 6.
Q.27 Given an unsorted array A of size n that may contain duplicates and a number k < n,
write a function that returns “1” if an array contains at least one duplicate pair within a distance of k, i.e. there exists i, j ϵ [0, n − 1] such that A [i] = A [j] and |i − j| < k.
Q.28 Write a function that accepts as argument an array A of integers together with its size n and a non-negative integer k. The function should create another array, which is obtained by cyclically shifting the input array A by k positions to the right. For example, if array A
= {2, 4, 6, 1, 3, 9, 5} of size n = 7 and k = 3, the function should create another array B
=
{3, 9, 5, 2, 4, 6, 1}.
Q.29 Given a matrix of N*N order. Write a program to interchange the diagonals of the matrix. For example, Input: { {1, 2, 3}, Output: { {3, 2, 1},
{4, 5, 6}, {4, 5, 6},
{7, 8, 9} } {9, 8, 7} }
Q.30 Write a function to reverse the order of the elements in an M*N array of integers, so that X [0][0] is now at X [M-1][N-1], X [0][1] is now at X [M-1][N-2], and so on. Input: { {0, 1, 2, 3, 4}, Output: { {19, 18, 17, 16,
15},
{5, 6, 7, 8, 9}, {14, 13, 12, 11, 10},
{10, 11, 12, 13, 14}, {9, 8, 7, 6, 5},
{15, 16, 17, 18, 19} } {4, 3, 2, 1, 0} }
Solve the same problem using loops and recursion both.
Q.31 Write a function that takes an input parameter a string, and returns the first nonrepeating character in it. For example, if the input string is “Malayalam”, then the output should be ‘y’ and if the input string is “Telugu”, then the output should be ‘T’.
Q.32 Write a function strend (s, t), which returns 1 if the string t occurs at the end of the string s, and zero otherwise.
Q.33 Write a program that encodes English-language word into pig-Latin. To translate an English word into a pig-Latin word, place the first letter of the word at the end of the word and add the letters “ay” at the end. For example: word “jump” becomes “umpjay”, word “the” becomes “hetay” and the word “computer” becomes “omputercay”. Do not use string.h library functions.
Q.34 Write a program that finds out the initials of the words in a string, where a single blank space separates two consecutive words in the string. For example, if the input string is “Sacred Games”, the output will be “S.G.”.
Q.35 Write a function squeeze (S1, S2) that deletes each character in the string S1 that matches any character in the string S2.
1 file (22.8KB)
