CS13002 Programming and Data Structures

Spring semester

Exercise set I

Note: Students are encouraged to solve as many problems from this set as possible. Some of these will be solved during the lectures, if time permits. We have made attempts to classify the problems based on the difficulty level of solving them. An unmarked exercise is of low to moderate difficulty. Harder problems are marked by H, H2 and H3 meaning "just hard", "quite hard" and "very hard" respectively. Exercises marked by M have mathematical flavor (as opposed to computational). One requires elementary knowledge of number theory or algebra or geometry or combinatorics in order to solve these mathematical exercises.

  1. Assume that the CPU of a particular computer has three general-purpose registers A,B,C. Assume also that m,n,t are integer values stored in the machine's memory. Write assembly instructions for performing the following assignments. Use an assembly language similar to that discussed in the examples given in the notes. Assume that all operations are integer operations.
    1. m = m + n - 1;
    2. t = (m+5)*(n+5);
    3. n = (m+5)/(n+5)+(n+5)/(m+5);

  2. [M] Let n be a non-negative integer less than 2t. Let (at-1at-2...a1a0)2 be the t-bit binary expansion of n obtained by the repeated divide-by-2 procedure described in the notes. Prove that: 
       n = at-12t-1 + at-22t-2 + ... + a121 + a0.

  3. Write the 8-bit 2's complement representations of the following integers:
    1. 123
    2. -123
    3. -7
    4. 63

  4. Find the 32-bit floating point representation of the following real numbers (under the IEEE 754 format):
    1. 123
    2. -123
    3. 0.1
    4. 0.2
    5. 0.25
    6. -543.21

  5. [H2M] Let x be a proper fraction, i.e., a real number in the range 0<=x<1. Prove that x has a terminating binary expansion if and only if it is of the form a/2k for some integers a,k with 0<=a<2k.

  6. Let x,y,z be unsigned integers. Find the values of x,y,z after the following statements are executed. 
       x = 5;
   z = 12;
   x *= x;
   x += z * z;
   y = x << 1;
   z = y % z;

  7. Assume that m and n are (signed) integer variables and that x and y are floating point variables. Write logical conditions that evaluate to "true" if and only if:
    1. x+y is an integer.
    2. m lies strictly between x and y.
    3. m equals the integer part of x.
    4. x is positive with integer part at least 3 and with fractional part less than 0.3.
    5. m and n have the same parity (i.e., are both odd or both even).
    6. m is a perfect square.

  8. Write a program to solve the following problems:
    1. Show that -29 and 31 are roots of the polynomial x3 + x2 - 905x - 2697. What is its third root?
    2. Show that -2931 is a root of the polynomial x3 + 2871x2 - 174961x + 2634969.
    3. The three roots of the polynomial x3 + x2 - 74034x + 5294016 are integers. Find them.
    4. The three roots of the polynomial x3 + x2 - 28033x - 1815937 are again integers. Find them.

  9. Read five positive real numbers a, b, c, d and e from the user and compute their arithmetic mean, geometric mean, harmonic mean and standard deviation.

  10. Input four integers a, b, c and d with b and d positive.
    1. Output the rational numbers (not their float equivalents) (a/b)+(c/d), (a/b)-(c/d) and (a/b)*(c/d).
    2. Output the rational numbers (a/b)+(c/d), (a/b)-(c/d) and (a/b)*(c/d) in lowest terms, that is, in the form m/n with n>0 and gcd(m,n)=1.

  11. Input four integers a, b, c and d with a or b (or both) non-zero and with c or d (or both) non-zero.
    1. Output the complex numbers (a+ib)/(c+id) and (c+id)/(a+ib) in the form (r/s)+i(u/v) with r,s,u,v integers and s,v>0.
    2. Output the complex numbers (a+ib)/(c+id) and (c+id)/(a+ib) in the form (r/s)+i(u/v) with r/s and u/v in lowest terms, that is, with s,v>0 and with gcd(r,s)=gcd(u,v)=1.

  12. Let m and n be 32-bit unsigned integers. Use bit operations to assign to m the following functions of n:
    1. 1 if n is odd, 0 if n is even.
    2. 1 if n is divisible by 4, 0 otherwise.
    3. 2n (Assume that n<=31).
    4. n rotated by k positions to the left for some integer k>=0.
    5. n rotated by k positions to the right for some integer k>=0.

  13. Write a program that does the following: Scan six real numbers a,b,c,d,e,f and compute the point of intersection of the straight lines: 
       ax + by = c
   dx + ey = f

    Your program should specifically handle the case that the two given lines are parallel.

  14. Write a program to determine the roots of a quadratic equation. Figure out a way to handle the case when the the roots are not real.

  15. Write a program that scans a string and checks if it represents a valid date in the format DD-MM-YYYY. (Example: 29-02-2005 is not a valid date, but 29-02-2004 is valid.)

  16. An ant is sitting at the left end of a rope of length 10 cm. At t=0 the ant starts moving along the rope to reach the other end of the rope. The ant has a speed of 1 cm per second. After every second the rope stretches instantaneously and uniformly (along its length) by 10 cm with the left end fixed at the point from where the ant started its journey. Suppose that the ant's legs provide it sufficient friction in order to withstand the stretching of the rope. Write a program to demonstrate that the ant will be able to reach the right end of the rope. Your program should also calculate how many seconds the ant would take to achieve this goal. You may assume that the length of the ant is negligible (i.e., zero).

    Note: The ant would reach the right end of the rope, even if its initial length and stretching per second were 1 km (or even a billion kilometers) instead of 10 cm. But for these dimensions the ant would take such an unbelievably large time that your program will not give you the confirmation in your life-time. Moreover, you will require more precision than what double can provide. Try to solve this puzzle mathematically.

  17. Randomly generate a sequence of integers between -5 and +99 and output the maximum and minimum values generated so far. Exit, if a negative integer is generated. You must not store the sequence generated (say using an array), but update the maximum and minimum values on the fly, as soon as a new entry is generated. A sample run is given below: 
       Iteration   1: new entry =  84, max =  84, min =  84
   Iteration   2: new entry =  87, max =  87, min =  84
   Iteration   3: new entry =  72, max =  87, min =  72
   Iteration   4: new entry =  53, max =  87, min =  53
   Iteration   5: new entry =  93, max =  93, min =  53
   ...

  18. It is known that the harmonic number Hn converges to k + ln n as n tends to infinity. Here ln is the natural logarithm and k is a constant known as Euler's constant. In this exercise you are asked to compute an approximate value for Euler's constant. Generate the values of Hn and ln n successively for n=1,2,3,..., and compute the difference kn = Hn - ln n. Stop when kn-kn-1 is less than a specific error bound (like 10-8).

    Note: It is not known whether Euler's constant is rational or not. It has, however, been shown that if Euler's constant is rational, its denominator must have more than 10,000 decimal digits.

  19. Write a program that, given a positive integer n, determines the integer t with the property that 2t-1<=n<2t. This integer t is called the bit-length of n.

  20. A Pythagorean triple is a triple (a,b,c) of positive integers with the property that a2+b2=c2. Write a program that scans a positive integer value k and outputs all Pythagorean triples (a,b,c) with 0<a<=b<c<=k.

  21. Consider the function 
       f(a,b) = (a2+b2)/(ab-1)

    of two positive integers a,b with ab>1.

    1. Write a program that scans a positive integer k and prints the three values a,b,f(a,b) if and only if 0<a<=b<=k and f(a,b) is an integer.
    2. [H3M] Do you see a surprising fact about these f(a,b) values? Can you prove your hunch?

  22. Given a number in decimal write a program to print the reverse of the number. For example, the reverse of 3481 is 1843.

  23. Write a program that does the following: Read a decimal integer and print the ternary (base 3) representation of the integer.

  24. Write a program that does the following: Read a string of 0's and 1's and print the decimal equivalent of the string treated as an integer in the binary representation.

  25. [H] Write a program that does the following: Read a string of 0's, 1's and 2's and print the decimal equivalent of the string treated as an integer in the ternary representation.

  26. Write a program that, given a positive number x (not necessarily integral) and an integer k, computes the kth root of x using the bisection method. Supply an accuracy for your answer.

  27. Generate a random sequence of birthdays and store the birthdays in an array. As soon as a match is found, report that. Also report how many birthdays were generated to get the match.

    Note: It is surprising to see that you usually require a very small number of people (around 25) in order to have a match in their birthdays. However counter-intuitive it might sound, it is a mathematical truth, commonly known as the birthday paradox. In short it says that if you draw (with replacement) about sqrt(n) samples from a pool of n objects, there is about 50/50 chance that you get a repetition. If you draw 2 sqrt(n) samples, you can be almost certain that there will be at least one repetition.

  28. Write a program that, given an array A[] of integers, finds out the largest and second largest elements of the array.

  29. Write a program that, given an array A[] of signed integers, finds out a subsequence i,i+1,...,j such that the sum 
       A[i] + A[i+1] + ... + A[j]
    is maximum over all such subsequences. Note that the problem is trivial if all numbers are positive -- your algorithm should work when the numbers may have different signs.

  30. [H2] Can you write a program that solves the problem of the last exercise using roughly n operations?

  31. Read an English sentence from the terminal. Count and print the number of occurrences of the alphabetic letters (a through z) in it. Also print the total number of distinct alphabetic letters in the sentence. Make no distinction between upper and lower case letters, i.e., 'a' is treated the same as 'A', 'b' the same as 'B' and so on. Neglect non-alphabetic characters (digits, spaces, punctuation symbols etc.).

  32. Input two strings a and b from the user and check if b is a substring of a. If b is a substring of a, then your program should also print the leftmost position of the leftmost match of b in a.

  33. Write a program that scans a positive integer and checks if the integer is a perfect number (i.e., a number which is equal to the sum of all its proper integral divisors, e.g., 6 = 1+2+3).

  34. Write a program that reads a positive integer n and lists all primes between 1 and n. Use the sieve of Eratosthenes described below:

    Use an array of n cells indexed 1 through n. Since C starts indexing from 0, one may, for the ease of referencing, use an array of n+1 cells (rather than n). Initially all the array cells are unmarked. During the process one marks the cells with composite indices. An unmarked cell holds the value 0, a marked cell holds 1. Henceforth, let us abbreviate "marking the cell at index i" as "marking i".

    Any positive integral multiple of a positive integer k, other than k itself, is called a proper multiple of k. Starting with k=2, mark all proper multiples of 2 between 1 and n. Then look at the smallest integer >2 that has not been marked. This is k=3 and must be a prime. Mark all the proper multiples of 3 and then look at the next unmarked integer -- this is k=5. Then mark the proper multiples of 5 and so on. The process need continue as long as k<=sqrt(n), since every composite integer m, 1<m<=n, must have a prime divisor <=sqrt(n).

    After the loop described in the last paragraph terminates, report the indices of the unmarked cells in your array. These are precisely all the primes in the range 1,2,...,n.

    Now adjust the bound n in order to detect the millionth prime.

  35. [HH] Repeat the above problem where a cell is marked at most once. In the previous description, cell 6 will will get marked when we consider 2 as well as 3 etc.

  36. [HM] Write a program that, given two integers a,b with 0<a<b, finds integers n1,n2,...,nk with the properties that: 
       n1 < n2 < ... < nk and
   a/b = 1/n1 + 1/n2 + ... + 1/nk.

    (Hint: You may use the following idea. If a/b is already of the form 1/n, we are done. Otherwise, find the integer n such that 1/n<a/b<1/(n-1). Print n, replace a/b by (a/b)-(1/n) and repeat. Prove that this gives a strictly increasing sequence of printed values (n) and that the process terminates after finitely many steps.)

  37. Write a program that, given a set of n points in the plane (specified by their x and y coordinates), determines the smallest circle that encloses all these points. (Hint: The smallest circle must either pass through three given points or have two given points at the opposite ends of a diameter.)

  38. In this exercise you are asked to compute approximate values of pi.
    1. Write the infinite series for 1/(1+x2).
    2. Integrate (between 0 and x) both 1/(1+x2) and the infinite series for it, put the value x = 1/sqrt(3) and write pi as an infinite series.
    3. Truncate the series after n terms and evaluate the truncated series to get an approximate value of pi. Use the values n=10i for i=1,2,...,6.

    4. Write the infinite series for 1/sqrt(1-x2).
    5. Integrate (between 0 and x) both 1/sqrt(1-x2) and the infinite series for it, put the value x = 1/2 and write pi as an infinite series.
    6. Truncate the series after n terms and evaluate the truncated series to get an approximate value of pi. Use the values n=10i for i=1,2,...,6.

  39. [H] Write a program to determine the smallest positive integer n with the following property. Let 
       n = akak-1...a1a0

    be the decimal representation of n with ak>0. Look at the integer: 

       n' = a0akak-1...a2a1

    (the cyclic right shift of n). The desired property of n is that n' must be a proper integral multiple of n.

  40. [H] Write a program to find the smallest positive integer n with the property that the decimal expansion of 2n starts with the four digits 2005, i.e., 2n = 2005... (Hint: Take log.)

Course home