Saturday, November 23, 2013

Balanced Brackets and Parentheses.

Difficulty (2/5).

Many languages enclose expressions using brackets or parentheses of various kinds. For example, in Java, you might see expressions like the following:
s = new ArrayList<>();
A[(i*2)+1] = ((x+2)*(y-2));
public int getValue() { return val; }
Notice how in all of these cases there is a "balancing principle" that gives the brackets a hierarchical structure. The rules for this balancing are as follows:
  1. Each open bracket must have a corresponding close bracket of the same kind to the right. Thus getValue() is balanced, but getValue(} is not.
  2. A closing bracket must be the same kind as the nearest unclosed open bracket to the left. Thus, A[(i*2)+1] is balanced, but A[(i*2]) is not.
Write a program that will prompt the user for an input line and determine if it's brackets of various kinds are balanced. Support the following bracket types:
(), [], {}, <>
Test your program on the following expressions:
{a[1], b[2], c[3]}
void alloc() { x = new ArrayList<>(b[3]); }
<<<< ((( [[ { x } ]] ))) >>>>

A[1) = 34;
(((( b )))
:) (:
Hint: Use a stack data structure.

CS1 Deadline: 12/6/2013
Use: handin cs1113 extra6

Saturday, November 16, 2013

Sum of Bit Indices.

Difficulty (1/5).

In some programming languages, such as C and Java, an integer is stored as a 32 bit quantity. For example, the integer 267 is represented by the following bits:
0000 0000 0000 0000 0000 0001 0000 1011
The bits of the integer are numbered from 0 to 31, with rightmost bit being considered bit 0, often called the "low order bit". The leftmost bit is considered to be bit 31, often called the "high order bit", or "sign bit". In the example above, bits 0, 1, 3, and 8 are 1 bits.

Write a program that will take an integer on the command line and print the sum of the bit indices that have a 1 bit in them. For example, given the input:
% java SumBitIndices 267
your program should calculate and print the value 12 (0+1+3+8).

To test your program, calculate the sum of the bit indices of the number 1265.

CS1 Deadline: 12/6/2013
Use: handin cs1113 extra5

See also:

Saturday, November 9, 2013

Numbers to Letters.

Difficulty: (1/5).

By numbering the letters of the alphabet from a=1 to z=26, and letting space=0, we can encode a multi-word message M of length k using the equation:
encode(M) = M[0]*27^(k-1) + M[1]*27^(k-2) + ... + M[k-2]*27^1 + M[k-1]*27^0
where M[i] is the value of character i of the message, and ^ means exponentiation.
For example, the code number for "ab cd" is
encode("ab cd") = 1*27^4 + 2*27^3 + 0*27^2 + 3*27^1 + 4*27^0 = 570892
Write a program that will take a number on the command line and decode it into a string in the manner just described. For example, given the input:
% java NumbersToLetters 570892
the program should print out the string "ab cd". Hints: use modular arithmetic. Use a long to store the number, since an int will only hold a message 6 characters long.

To test your program, decode the number 42120723190451.

CS1 Deadline: 11/29/2013
Use: handin cs1113 extra4

Optional: If you store the code number as an int, your program will only be able to handle messages of 5 letters or less. Using a long increases the maximum message size to 11, but this is still pretty short. Extend your program to larger messages by using BigInteger or another multiprecision library to store the code number. Test your enhanced program by decoding the number:

Saturday, November 2, 2013

Squares in a Circle.

Difficulty: (2/5)

Let us define the Unit Grid as the set of 1x1 squares on the plane with corners that have integer coordinates. For example, the square with corners (1,1), (2,1), (1,2) and (2,2) is part of the unit grid.

Let C be a circle with center (x,y) and radius r.

Write a program that will take the center and radius of a circle (x, y and r) as as command line arguments and print out how many squares from the unit grid are completely covered by the circle. For example, given the input:
% java GridSquares 0.5 0.5 1.0
the program should calculate the number of grid squares completely covered by the circle with center (0.5, 0.5) and radius 1.0, which happens to be 1.

To test your program, calculate the number of grid squares in a circle with center (0.25, 0.4) and radius 200.

CS1 Deadline: 11/15/2013
Use: handin cs1113 extra3

Optional: Extend your program to deal with very large circles. Test your enhanced program on the circle with center (0.1, 0.1) and radius 200000. (Hint: You won't have time to count the squares one by one).