CmSc 155 Data Structures and Object-Oriented Programming

This course follows on from CmSc 150 and goes in depth into object-oriented programming, exploring encapsulation, overloading, polymorphism, interfaces, and inheritance. The core data structures are implemented and used, including arrays, array-lists, linked lists, stacks and queues. Algorithms for searching and sorting are developed, analyzed and compared. The class is taught in Java. Prerequisite: CmSc 150. Four credits. Offered every spring.

Here are some fun problems that are solved in this class.

(1) Given: An n-by-n array K such that K[i][j] = 1 if person i knows person j and K[i][j] = 0 otherwise.
A celebrity is a person who knows no-one (besides themselves) and is known by everyone. Write and test a method that determines if an array has any celebrities.
Examples:
1 0 1 0 1
0 1 1 1 1
0 0 1 0 0
0 0 1 1 1
1 1 1 0 1
Above array has a celebrity, person 3.

1 0 1 0
1 1 0 1
0 1 1 1
1 1 1 1
Above array has no celebrities.

(2) Create and test a method that takes any positive integer n and returns the following array:

The elements in the 1st row and column are all 1.
The elements in the 2nd row and column are all 2 (except for those in the 1st row and column).
The elements in the 3rd row and column are all 3 (except for those in the 2nd row and column).
And so on.
E.g. if n is 5 the result should be
1 1 1 1 1
1 2 2 2 2
1 2 3 3 3
1 2 3 4 4
1 2 3 4 5

(3) Create and test a method that automatically decodes a message encoded using a “Caesar” code, in which each
letter is shifted by the same amount.
Assumed the message consists of lower-case letters and punctuation. The punctuation symbols are not encrypted.

The method should try all 26 possible decodings, and use a dictionary to determine the most likely decoding.
E.g. “haahjr ha khdu!” decodes as “attack at dawn!”