Turn-in Checklist:
  1. Bring in to class a stapled turn-in containing your written answers to all the questions. If you worked with a partner, you and your partner should submit a single writeup with both of your names and UVA Email Ids on it. You must clearly indicate both names and UVA IDs in big block letters if you are working in a team.
  2. Use our automatic adjudication service to submit a single Python file (a modification of ps5.py) containing your Python code answers. You must define an author list. Each partner must separately submit a copy of your joint Python file.
  3. Use our automatic adjudication service to submit a single Java file (a PS5.java — it must be named exactly that, including using the uppercase letters) containing all Java code answers. You must define an author list. Each partner must separately submit a copy of your joint Java file.

Collaboration Policy - Read Very Carefully

You may work on this assignment alone or with one partner of your choice so long as it is not someone with whom you have partnered on two or more previous problem sets.

Regardless of whether you work alone or with a partner, you are encouraged to discuss this assignment with other students in the class and ask and provide help in useful ways.

Remember to follow the pledge you read and signed at the beginning of the semester. For this assignment, you may consult any outside resources, including books, papers, web sites and people, you wish except for materials from previous cs1120, cs150, and cs200 courses. You may consult an outside person (e.g., another friend who is a CS major but is not in this class) who is not a member of the course staff, but that person cannot type anything in for you and all work must remain your own. That is, you can ask general questions such as "can you explain recursion to me?" or "how do lists work in Python?", but outside sources should never give you specific answers to problem set questions. If you use resources other than the class materials, lectures and course staff, explain what you used in your turn-in.

You are strongly encouraged to take advantage of the scheduled help hours and office hours for this course.


Optinal Reading: Course book Chapter 9 or complete Udacity CS 101.
Download: Download ps5.zip to your machine and unzip it into your home directory J:\cs1120\ps5.

This file contains:

  • ps5.py — A template for your answers. You should do the problem set by editing this file.
  • database.py — Partial implementation of a database.
  • helper_functions.py — Some useful procedures for this PS.


Once upon a time, in a faraway fictional town known as Charlottansville, East Virginia, there was a highly regarded public university where funding cuts led to a budget crisis. The wise and noble University administration tried cutting "non-essential" services such as heat and cleaning for student housing, libraries, printing and professors and have attempted some more creative solutions including hosting rock concerts, building a fancy new basketball arena, increasing student tuition, adding extra digits to course numbers, briefly firing the president, and replacing an adequate student information system with a dysfunctional one, but somehow the budget is still not balanced and the University is expecting further extractions from the Commonbroke government.

Fortunately, the University was able to get "Chapter 11" status from the Commonwealth, which gives it more power to control its own destiny by raising tuition and selling off assets. The Board of Transients has decided the time for drastic measures has arrived, and they will conduct an auction to raise money. To avoid paying fees to a commercial auction service, they have decided to exploit free labor from cs1120 students to develop an auction service for them.


The auction service will be built using a database. A database is just a way of storing and manipulating structured data. For this problem set, you will implement a database and use it to implement an auction service. Our database is controlled using Python procedures that are similar to the SQL commands used to control nearly all commercial databases. In the final course project (Problem Set 9), you will build a dynamic web site that uses an actual SQL database.

Data in a database is stored in tables. The fields of a table describe the data and are not mutable. The entries of a table are the data, and can be changed.

We represent a table using a list of lists. The first element of the list is a list of the labels for the fields in the table (i.e. ["name","email"]). The rest of the elements of the list correspond to the entries in the table. All entries (including the list of lables) must all have the same number of elements.

Consider the following example table:

Course NumberTitleRoom
cs2330Digital Logic DesignRice Hall 240
cs3330Computer ArchitectureOlsson Hall 120
cs4102AlgorithmsRice Hall 130

In Python, we would represent this table with the following list of lists:
[["course_number","title","room"], \
    ["cs2330","Digital Logic Design","Rice Hall 240"], \
    ["cs3330","Computer Architecture","Olsson Hall 120"], \
    ["cs4102","Algorithms","Rice Hall 130"]] 

In order to work with these tables, the following definitions are provided in database.py:

# Make a table from a list of fields and a set of entries
def make_table(fieldlist,entries):
    return [fieldlist] + entries

# Make a table from just a list of fields
def make_new_table(fieldlist):
    return [fieldlist]

def table_fields(t):
    return t[0]
def table_entries(t):
    return t[1:]

In this problem set, we will be building an eBay-like auction service called Wahoo! Auctions.

For our Wahoo! Auctions service, we will need several different tables to keep track of the bidders, the items for sale, and the bids on those items. We use strings to describe the fields in a table. Those tables are defined in ps5.py:

bidders = make_new_table(["name","email"])
items = make_new_table(["item_name","description"])
bids = make_new_table(["bidder_name","item_name","amount"])
# bidders, items and bids are all tables in our database

Since new bids come in all the time, we will use mutation to update the state (i.e., the current information) stored in our database.

Inserting Entries

We want to define more abstract procedures for manipulating data tables.

The table_insert procedure inserts an entry into a table.

You shouldn't need to change the definition of table_insert, but you should be able to understand it (defined in database.py):

def table_insert(table,entry):
    # We first need to check that the new entry has as many
    # elements as the other entries.  If it doesn't, we
    # give up and raise an error.
    if len(entry) != len(table_fields(table)):
        raise StandardError("New table entry has " + str(len(entry)) + \
            " values, but " + str(len(table_fields)) + "were expected")

    # Add the new element. The "append" function here is
    # the mutation equivalent of: table = table + [entry]
The expression len(entry) != len(table_fields(table)) will be True if the entry we are adding to the table has the wrong number of elements — there must be one element in the entry corresponding to each field in the table. If this is the case, we will raise an error (just like the get_angle and get_offshoot_commands functions from Problem Set 3). Otherwise, we will simply append the entry to our table.

Our auction service will need procedures for adding bidders, posting items for sale and bidding on items. We have provided a definition of add_bidder in ps5.py:

def add_bidder(name, email):
    table_insert(bidders, [name,email])
It takes two parameters (name and email) and adds an entry in the bidders table. Understanding it should give you a good idea how to define some additional procedures. We have defined a table_display procedure in database.py for printing out a table. (You don't need to understand the details of how table_display works.)

You should obtain the following interactions:

>>> table_display(bidders)
name                       email                      
-------------------------  -------------------------  

>>> add_bidder("Tim Koogle", "tk@yahoo.com")
>>> add_bidder("Katie Couric", "katie@cbs.com")
>>> add_bidder("Dave Matthews", "dave@dmb.com")
>>> table_display(bidders)

name                       email                     
-------------------------  ------------------------- 
Tim Koogle                 tk@yahoo.com              
Katie Couric               katie@cbs.com
Dave Matthews              dave@dmb.com              

Question 1:

a. Define post_item as a procedure that takes two parameters (name, description) and adds an entry with the given name and description to the items table.

b. Define insert_bid as a procedure that takes three parameters (bidder, item, and amount) and adds a corresponding entry to the bids table.

Question 2: Describe the running time of your insert_bid procedure. Your answer should use Θ notation, clearly explain what all variables you use mean, and include a convincing explanation of why your answer is correct.

Develop tests for your post_item and insert_bid procedures similar to the add_bidder examples above, and make sure they also work correctly.

Selecting Entries

Inserting entries in tables is only useful if we can also get the entries we are interested in out of the table. The table_select procedure takes a table, a field and a procedure. It evaluates to a table that has the same fields as the input table, and has entries that are all entries in the table for which the procedure applied to the value of the field for that entry is true. (That is, the procedure is a predicate, like we saw in filter.)

For example,

>>> table_select(bids, item_name, lambda pitem : pitem == "CLAS")
should produce a table with the same fields as the bids table, ["bidder_name","item_name","amount"], but only containing those entries whose item_name field value matches the string "CLAS".

So, to define table_select, you will first need to find the index of the selected field (e.g., "item_name" in the example). We have provided (in helper_functions.py) the list_find_element procedure that may be helpful for this. It takes as input a list and a value, and returns a number that indicates what is the first element of the input list that matches the input value. As usual, elements are numbered starting from 0. If none of the elements match, the return value is -1.

# Why do we need a separate helper function? (Feel free to skip this
# explanation) In this case, we need an extra variable n to keep track of
# how many elements we have seen in the list so far. Alternatively, we
# could define the recursive step as 1 + list_find_element_helper(list[1:],
# value, n+1), but then when we return -1, the entire length of the list
# will be added on top, which is not what we want.

def list_find_element_helper(list, value, n):
    if len(list) == 0:
        return -1
    elif list[0] == value:
        return n
        return list_find_element_helper(list[1:],value,n+1)

# List_find_element looks for a specific value in a list and returns its
# index in the list.  If the element is not in the list, we return -1.
def list_find_element(list,value):
    return list_find_element_helper(list,value,0)
Using list_find_element, we have defined table_field_number, a procedure (in database.py) that takes a table and a field and outputs the index of that field in the table's field list:
def table_field_number(table,field):
    return list_find_element(table_fields(table),field)
The fields are indexed starting from 0; if the field is not in the table, table_field_number outputs -1.

Hence, you could start to define table_select as:

def table_select(table,field,predicate):
    fieldno = table_field_number(table,field)
    if fieldno == -1:
        raise StandardError("No matching field: " + str(field))
Another procedure you may find helpful in finishing the definition of table_select is the filter procedure in Python. This procedue takes in a function and a list, and will filter out all elements in the list that don't satisfy the function. For example:
>>> print filter(lambda x : len(x) == 2, ["hi", "hello", "by", "bye"])
["hi", "by"]

Question 3: Define the table_select procedure.

If your table_select is working correctly, you should see interactions similar to these:

Remember our University is completely fictional. The bid amounts should not be construed to have anything to do with the actual value of any aspects of any real Universities with which you might be familiar or with the generosity of actual University alumni who might have similar names.
>>> setup_tables()

>>> print table_select(bids,"item_name",lambda x: x=="CLAS")
[['bidder_name', 'item_name', 'amount'], ['Dave Matthews', 'CLAS', 2000000], \
         ['Katie Couric', 'CLAS', 37000000]]

>>> table_display(table_select(bids,"item_name",lambda x: x=="CLAS"))
bidder-name                item-name                  amount
-------------------------  -------------------------  -------------------------
Dave Matthews              CLAS                       2000000
Katie Couric               CLAS                       37000000

>>> print table_entries(table_select(bids,"item_name",lambda x: x=="SEAS"))
[['Tim Koogle', 'SEAS', 10000000]]

>>> print table_entries(table_select(bids,"item_name",lambda x: x=="The Rotunda"))

>>> print table_entries(table_select(bids,"amount",lambda x: x>10000000))
[['Tiki Barber', 'COMM', 79000000], ['Katie Couric', 'CLAS', 37000000]]

>>> print table_entries(
            table_select(bids,"amount",lambda x: x>10000000),
            "bidder_name",lambda x: x == "Katie Couric"))
[['Katie Couric', 'CLAS', 37000000]]
Selects can be nested since they produce tables as output. Here we use table_select(bids,"amount", lambda x : x > 10000000))) to produce the table of all bids over 10000000, and then use another table_select to select the bids from that table where the bidder name is "Katie Couric". To make sure you understand table_select, produce a different expression that will evaluate to the same table by selecting the name first and then the amount.

In ps5.py we define define the procedure get_bids procedure for making it easier to do table selects:

def get_bids(item):
    return table_entries(table_select(bids, "item_name", lambda x: x==item))
The get_bids procedure evaluates to a list of bid entries that are the entries in the bids table whose item_name field matches the parameter item.
Question 4: Describe the asymptotic running time of your table_select procedure using Θ notation. Be careful to specify carefully what any variables you use in your answer mean.

Highest Bids

In any auction, it is important to know who currently has the highest bid.
Question 5: Define a get_highest_bid procedure that takes an item name as a parameter and evaluates to the bid entry that is the highest bid on that item. If there is no bid, return the empty list []. You shouldn't assume that the last entry that is a bid on this item is the highest bid for that item. [Hint]

Your get-highest-bid procedure should work like this:

>>> setup_tables()
>>> print get_highest_bid("SEAS")
['Tim Koogle', 'SEAS', 10000000]
>>> print get_highest_bid("Rotunda")

Placing Bids

To conduct fair auctions, we can't just allow any bid to be inserted into the bids table. Instead, bids will be placed using a place_bid procedure. It should:

To report an error, you can raise an exception. The popular StandardError exception takes as input a string describing the error message. For example: raise StandardError(bidder + " is not a legitimate bidder"). The exact prose of your error message doesn't matter — only that it clearly indicates what the problem is. So be as creative as you like with your error messages.

Note that you may run into a problem if you try to include something that is not a string in your error message. If, for example, you use the code "You bid $" + amount, where amount is an integer, then Python will raise an error, as strings and integers cannot be added together. To fix this, simply call the str function to convert something that is not a string into a string, as in "You bid $" + str(amount).

Question 6: Define a place_bid procedure that satisfies the description above. Don't attempt to do everything at once! Start by satisfying one of the properties first and testing your procedure before trying to satisfy the other property.

Hint: place_bid may be of moderate length: 10 lines is reasonable. Don't worry if yours is longer or shorter, as long as you understand what is going on and you are getting the right answers.

You should get interactions similar to these:

>>> setup_tables()
>>> print place_bid("Tim Koogle","SEAS",20000000)
>>> print place_bid("Katie Couric","SEAS",18000000)
#Traceback ... 
#    StandardError: Bid amount does not exceed previous highest bid: 
#                                            ['Tim Koogle', 'SEAS', 20000000]

>>> print place_bid("Katie Couric","SEAS",22000000)
>>> print place_bid("Dave Matthews","The Rotunda",1000000)
#Traceback ... 
#    StandardError: The Rotunda is not for sale!

>>> print place_bid("Wes Weimer","SEAS",10000000000)
#Traceback ... 
#    StandardError: Wes Weimer is not a legitimate bidder
The astute reader may notice that "Tiki Barber" appears in teh bids table from setup_tables() but does not appear in the bidders table. That's exactly the sort of mischief that your place_bid procedure prevents!

Ending the Auction

When the auction is over, all items are sold to the highest bidders and the University collects the high bid amounts. If there are no bids for an item, it cannot be sold.

Question 7: Define a procedure end_auction that reports the final auction results by creating and returning a "winners" table.
winners = make_new_table(["item_name","bidder_name","winning_amount"])
You may assume that the auction has been conducted fairly (i.e., by using place_bid and not by randomly mutating the tables). For each entry in the items table, in other, your winners table should contain an entry indicating the winning bid and the winning bidder. If there were no bids on that item, do not include it in your winners table.
Here's an example:
>>> setup_tables()
>>> table_display(end_auction())
item_name   bidder_name    winning_amount
----------  -------------  ----------------
SEAS        Tim Koogle     10000000
CLAS        Katie Couric   37000000
COMM        Tiki Barber    79000000
SIS         Bono           1

# Note: there was no winning bid on item "CS1120", so it
# does not appear in the answer.

Try some sample auctions to demonstrate your program. See if you can make enough money to save the University, but be careful not to sell off too many important assets — we will revisit the University in Charlottansville in Problem Set 6.

Question 8: Describe the running time of your end_auction procedure. (You answer should use Θ notation, should clearly define the meaning of all variables you use in your answer, and should include a convincing explanation of why it is correct.)

Introduction to Java

Java: These next few problems introduce you to Java. Make sure that you have read the Java Lab Guide and any other Java-related materials we have provided.

The Java programming language is a popular choice for solving problems in modern computer science practice. Java is an object-oriented and statically-typed language: we will cover what those concepts mean in more detail in class.

For now, we will go through a series of simple exercises designed to make sure that we can all write simple Java programs and translate our knowledge of Python to our knowledge of Java. You'll find that the underlying algorithms and concepts remain the same, but that Java has different syntax.

Hello, world.

The first thing you’ll have to do is create a Java file using Eclipse (follow the Eclipse/Java tutorial video if you need help with this). Name your file "PS5.java". (Case matters: you must use uppercase "PS".) Eclipse will automatically generate a class that is the same name as the file you created. It should look like this:
public class PS5 {
  // class code goes here
This is helpful because all of your code needs to go inside a Class (i.e. between the curly braces after the class name). In Java, all of your code is organized into classes. You’ll learn more about classes a little later, but for now, just think of them as a way to organize your code by grouping functions and data that are meant to do similar things into one place.

In Java, comments start with //. (In Python, they start with #.)

Inside your PS5 class, you’ll need to make a main method. Because Java programs can be quite large, the special main method tells Java where to start running your program. Unlike Python, Java is very specific about what code it executes when you run your program. Java will only run the code you put inside a function named main, so it's up to you to make sure you call any other code you want to execute! Your main function should be defined like this, inside your PS5 class:

public class PS5 {

  public static void main( String[] args ) {
    // Put your code here

The words public static void main( String[] args ) are very important to Java and you must type them exactly as they are listed here. If you change any of them, your program will not be valid Java. We'll talk about what they mean later. For now, just accept them as something arbitrary you have to do to make Java happy.

Inside your main function, you need to call Java's print function. Java's print function is called System.out.println and looks like this:

Java Code Python Equivalent
public static void main( String[] args ) {
  System.out.println("String to be printed");   
print "String to be printed" 
We've included the declaration for main in the Java example to remind you that you always need a main function inside one of your classes in a Java program. Beyond that, however, the Java version is more verbose than the Python version: Java is very rigorously organized.

The line System.out.println("String to be printed"); is saying "I want to print a line, and the function to do so is in the System class's output section."

You now know enough to write your first Java program.

Question 9: Submit a PS5.java file containing a main method that prints out the string "Hello, world.". It should look like the example above, but the particular string will be different.

Java Arrays and Iteration

In Python, lists are very important. In Java, arrays are often used for similar purposes.

Java Code Python Equivalent
public static void main( String[] args ) {   
  int [] numbers = {8, 6, 7}; 
  System.out.println( numbers.length );
  System.out.println( numbers[0] ) ; 
numbers = [8, 6, 7] 
print len(numbers)
print numbers[0]

We're going to print the largest element in a Java array. We specify an array using the following syntax:

int [] myArray = {1, 2, 3};
This says we want to hold integers (and only integers) in an array [] named myArray. In addition, we want the initial value of myArray to be {1, 2, 3}.

Be careful when initializing a Java array: once you give it a size, you can't make it any bigger or smaller later! You can change the value of any element, you just can't add or subtract any elements from a Java array. (That's annoying, so we'll see how to work around that in the next problem.) You access elements of an array the same way you access elements of a Python list: container [ index ]

Using this information, we will make an "author list" array that holds the UVA ID strings of you and all of your partners (if any). We want it to be a public global variable that anyone (notably including our grading system!) can see. So we'll put it outside of main.

Java Code Python Equivalent
public static String [] authors = { "mst3k" } ; 

public static void main( String[] args ) {   
  // ...
authors = ["mst3k"] 

# ...

If you look closely, you'll see that we had to tell Java that the author list will hold Strings. Don't worry about the public static part for now.

Question 10: Add to your PS5.java a public static String [] authors variable that is initialized to contain the UVA IDs of you and all of your partners for this problem set.
Now we'll write a Java function called find_best that takes a non-empty array of ints and returns the largest int it contains. To do so, we'll need to learn more Java equivalents of Python syntax. Control structures, like if-else, translate fairly directly:

Java Code Python Equivalent
public static void main( String[] args ) {   
  if (5 > 3) {
    System.out.println("This is true."); 
  if (22 > 44) {
  } else { 
  // you must give the type of each new variable
  int x = 77; 
if 5 > 3:
        print "This is true." 
if 22 > 44:
        print "Alpha."
        print "Beta."
x = 77 
print x
This is true.

Note how Java uses { curly braces } instead of : and tabbing to indicate control structure grouping. We'll also need to be able to iterate over every element in an array. Both Python and Java use a for loop to do this, but the syntax is a little different:

Java Code Python Equivalent
public static void main( String[] args ) {   
  int [] myArray = { 8, 1, 6, 2, 7 } ; 
  int x = 3; 
  for (int i = 0; i < myArray.length ; i = i + 1) {
    if (myArray[i] > x) {
      System.out.println("... is greater than x!"); 
myArray = [8, 1, 6, 2, 7]
x = 3
for i in range(len(myArray)):
        print myArray[i]
        if myArray[i] > x:
                print "... is greater than x!"
... is greater than x!
... is greater than x!
... is greater than x!

Note that in Java you must put ( parentheses ) around the conditional for each if. Java for loops are often used as follows:

for( int i = 0; i < array_size; i=i+1 ) {
  // put loop body code here
Which you can think of as follows:
for( index initialization; loop condition; index modifier ) {
  // put loop body code here
A for loop starts by running your initialization code (setting the index i to 0 in the case above). Then, it checks to see whether or not the loop condition is true. If it is, it executes your loop code once and then runs your modifier code (increasing the value of index i by 1). After that, it repeatedly checks to see if the condition is true, runs your loop if it is, then executes your modifier code each time.

We now have enough information to write a Java procedure that finds the largest value in an array of ints.

Question 11: Add to your PS5.java a public static int find_best(int [] array) function that returns the largest element in its input array (which will always be non-empty).

You can test your find_best code by calling it from main. For example, you might get started with:

public class PS5 {
  // author list definition

  public static void main(String [] args) {
    // code to print out "Hello, world."
    int [] myArray = {8,6,7,3,9,0,5}; 
    System.out.println( find_best( myArray ) );

  public static int find_best(int [] array) {
    // ... code? ...
    for (int i=0; i < array.length; i=i+1) {
      // code involving array[i] 
    return 0 // replace with best element 
On such a test, your code should print 9 after Hello, world.

Hint: You might make a local int variable best that holds the best value you've seen so far. Since you know the input array is non-empty, you might start by assigning the value of the zero-th element of the array into best. Then, inside the for loop, check to see if each element is bigger than best. If it is, reassign best to hold the new value. Finally, return best.

Sorting an ArrayList

Simple Java arrays have a fixed size: you can change the values of array elements, but you cannot add news ones easily. So what happens if you want an array of variable size? One solution is to use a Java object called an ArrayList.

ArrayList allows us to make variable-sized collections of objects. But with this added flexibility comes a little extra work. First, we have to tell Java that we want to use ArrayList objects. We do that by adding the following line of code before and outside our class:

import java.util.ArrayList;

public class PS5 {
  // ...
After we import the ArrayList class definitions, we can initialize an ArrayList as follows:
import java.util.ArrayList;

public class PS5 {

  public static void main( String[] args ) {
    ArrayList<Integer> myArrayList = new ArrayList<Integer>();
The Integer inside the angled brackets is called a generic. All it does is tell Java what kind of values we’ll be storing in our array (notice that we used Integer instead of int — for now, that's just something arbitrary we need to keep Java happy). On the other side of the equals sign, we use Java’s new keyword to make a new, empty ArrayList. Then, we can append elements to an ArrayList by calling:
myArrayList.add(element);       // Python: lst = lst + [element] 
We can also add all of the elements of one ArrayList into another:
myArrayList.addAll(otherArrayList); // Python: lst = lst + other_list
And we access those elements using:
myArrayList.get(index);         // Python: lst[element] 
We can also mutate an array list by removing elements:
myArrayList.remove(index);  // removes the index-th element
... and get the number of elements remaining by calling:
myArrayList.size();  // Python: len(lst) 
Note that for arrays we used array.size, but for ArrayLists we use arrayList.size() — ah, the arbitrary glory of Java.

We now know enough Java to write a procedure that sorts ArrayLists of Integers. We've learned a few ways to sort numbers. Let's try the "selection sort" or "find best sort":

public static ArrayList<Integer> sort(ArrayList<Integer> lst) {

  // 1. if the lst.size() is 0, return lst

  // 2. Find the index corresponding to the highest number in lst.
  //      This will be like your find_best code above, but will work
  //      on ArrayLists. You'll probably use "for" and ".get()". 
  //      We might call this index "best_index".

  // 3. Note the value associated with best_index in lst.

  // 4. Make a new empty ArrayList and add the best value from Step 3 to
  // it.

  // 5. Remove the best_index-th element from lst.

  // 6. Make a recursive call to sort() on the new, smaller lst. 

  // 7. Add all of the elements from the result of the recursive call
  // to the list you made in step 4, and return it.
Question 12: Add to your PS5.java a public static ArrayList<Integer> sort(ArrayList<Integer> lst) function that returns the ArrayList in sorted descending order.

Note: You are not allowed to used the predefined Collections.sort() in your solution. You must write the code to sort from scratch!

You can test your sort code by calling it from main. For example, you might get started with:

public class PS5 {
  // author list definition

  public static void main(String [] args) {
    // code to print out "Hello, world."
    ArrayList<Integer> myArrayList = new ArrayList<Integer>();
    System.out.println( sort(myArrayList) );

  public static ArrayList<Integer> sort(ArrayList<Integer> toSort) {
    // ...
On such a test, your code should print [9, 8, 7, 6, 5, 3, 0] after Hello, world.

Counting Letters in a String

In addition to lists and recursive procedures, we often like to manipulate strings.
String s = "Hello";                     // s = "Hello"
System.out.println( s );                // print s 
System.out.println( s.length() );       // print len(s)
System.out.println( s.substring(1,3) ); // print s[1:3] 
System.out.println( s.equals("Hi") );   // print s == "Hi" 

Note that you should not use == to compare two strings. Instead, use string1.equals(string2).

Let's write a procedure that counts the number of times a target letter appears in a string.

public static int countLetter( String toCount, String targetLetter ) {
  // Your code here
Question 13: Add to your PS5.java a public static int countLetter(String myString, String targetLetter) function that returns the number of times the single letter targetLetter occurs in myString.

You can test your countLetter code by calling it from main. For example, you might get started with:

public class PS5 {
  // author list definition

  public static void main(String [] args) {
    // code to print out "Hello, world."
    System.out.println( countLetter("java junkies", "a") );
    System.out.println( countLetter("lorelai leigh gilmore", "l") );
    System.out.println( countLetter("", "w") );

  public static int countLetter(String myString, String targetLetter) {
    // ...
On such a test, your code should print 2 4 0 after Hello, world.

Welcome to Java!

Credits: This problem set was created for CS200 Spring 2003 by Katie Winstanley, Rachel Dada, Spencer Stockdale and David Evans, revised for CS200 Spring 2004 by Sarah Bergkuist and David Evans, revised for CS150 Fall 2005 by David Evans, and revised for CS150 Spring 2009 by Wes Weimer. It was adapted for Python and Java in 2012 by Jonathan Burket, Lenny Li, and Dru Knox.