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:

BALANCED:
(a+3)*(b+2)
{a[1], b[2], c[3]}
void alloc() { x = new ArrayList<>(b[3]); }
<<<< ((( [[ { x } ]] ))) >>>>

NOT BALANCED:
A[1) = 34;
(((( b )))
:) (:

Hint: Use a stack data structure.

CS1 Deadline: 12/6/2013
Use: handin cs1113 extra6 BalancedBrackets.java

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 SumBitIndices.java

See also: http://graphics.stanford.edu/~seander/bithacks.html

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 NumbersToLetters.java

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:

65530143041677706302967142525228354930666445327554797323840124289201432437575885

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 SquaresInCircle.java


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).

Sum Of Primes.

Difficulty: (2/5)

Write a program that will take an integer as a command line argument and print the sum of all primes less than that number. For example:

% java SumPrimes 10

would sum the primes below 10:

2 + 3 + 5 + 7 = 17

To test your program, calculate the sum of all primes below a million:

Hints: Use the Sieve of Eratosthenes. Also, realize that the sum of all primes below a million is too big to fit in an int.

CS1 Deadline: 11/8/2013
Use: handin cs1113 extra2 SumPrimes.java

Area of a Triangle.

Difficulty: (2/5)

Write a program that will take the coordinates of the vertices of a triangle in 3D as command line arguments and print out the area of the triangle. For example, given the input:

% java TriangleArea 0 0 0  1 0 0  0 1 0

The program should calculate the area of the triangle with vertices (0,0,0), (1,0,0), and (0,1,0), which happens to be 0.5. Hint: Use Heron's formula, or the cross product.

To test your program, calculate the area of the triangle with vertices

(1, 2, 3)  (7, 8, 9)  (4, -5, 10)

CS1 Deadline: 11/1/2013
Use: handin cs1113 extra1 TriangleArea.java

A place for programming puzzles. I will try to publish about one per week. If you know what you are doing, you should be able to write a program that solves the program in a couple of hours or less. The hope is to introduce different topics related to programming techniques, useful math, etc.