Remove last element

Given a singly LinkedList, suppose you have a reference to the head of the list, but no tail and no size. Implement a method which removes the last element of the list.

• What is the running time of your solution?
• Can you do this with a single loop?
• Bigger challenge: given the head and an integer \(n\), can you remove the \(n\)-th element from the end of the list?

Reverse a Singly Linked List

Given a singly LinkedList, how might you implement a reverse method? Moreover, how might you do this in-place: that is, without using a secondary list or additional storage?

Middle Element

Given a singly LinkedList, how might you find the middle element in one loop?

Collate Iterators

• Read one item from an iterator, then switch iterators.
• If an iterator runs out, remove it.
• Cycle around when you get to the end.
• How?
• Can a data structure help?
• Replit.

Bracket Matching

The following strings of brackets are perfectly matched:

• {}([])
• [(()())]

The following are not:

• {(})
• (][)

(Replit)

Base Counting

Devise an algorithm which, given an input \(n\), outputs all numbers from 1 to \(n\) in binary. Example: if \(n = 6\), then we write 1, 10, 11, 100, 101, 110. (The format of the output doesn’t matter, they can all be on separate lines.)

Base Counting

Idea:

• Queue it up!
• Start with “1” on the queue (as a String)
• Dequeue a “number” (as a String)
  • Output the number.
  • Append a 0 to the number, enqueue it back.
  • Append a 1 to the number, enqueue it back.
• When do you stop?

General Base Counting

Given a file with a number b (from 2 - 8) and another number n (written in base 10), output all numbers from 1 to n in base b.

Postfix calculator

Regular (“infix”) arithmetic expressions require precedence rules and/or brackets to know how to evaluate them: \(3 + 4 * 5 = 23\). Postfix expressions do not require precedence rules. Postfix means the operator goes after the operands:

• \(3+4 * 5\) is “3 4 5 * +” in postfix
• \((3+4)*5\) is “3 4 + 5 *” in postfix
• What is: “12 7 − 13 4 − 5 * +”?

Reading from a text file

// assumes "data.txt" is in src folder
InputStream is = MyClass.class.getResourceAsStream("data.txt");
Scanner sc = new Scanner(is);
// for the PostfixCalculator:
while (sc.hasNextLine()) {
  String line = sc.nextLine();
  Scanner lineScanner = new Scanner(line); // this works!
   // now we can read the data from the Scanner the same way we read input
   // we can use lineScanner.nextInt(),
   // or lineScanner.hasNextInt(), for example
}

base_test.txt

For the “General Base counting” exercise, it’s somewhat easier. Just need to read two ints:

InputStream is = MyClass.class.getResourceAsStream("base_test.txt");
Scanner sc = new Scanner(is);
int base = sc.nextInt();
int number = sc.nextInt();

postfix_test.txt

For the PostfixCalculator, need to parse several lines:

InputStream is = MyClass.class.getResourceAsStream("postfix_test.txt");
Scanner sc = new Scanner(is);
while (sc.hasNextLine()) {
  String line = sc.nextLine();
  Scanner lineScanner = new Scanner(line);
  while (lineScanner.hasNext()) {
    if (lineScanner.hasNextInt()) {
      int number = lineScanner.nextInt(); // do something with this number
    } else {
      String operator = lineScanner.next(); // do something with this operator
    }
  }
}

Submission

• Make a short presentation of this (take screenshots of your code to include in PPT, etc)
• Upload (PDF or PPT) to assignment space on BrightSpace.
• Sign up on this spreadsheet for a time to present.
• Presentations start next Thursday (9/21).

Rubric

5 points:

• (2 points) Algorithm: clear description of the algorithm.
• (2 points) Code: show and explain a working demo for this problem.
  • Working demo doesn’t need to be perfect (ie don’t worry about validating inputs, etc.)
  • You should explain how the code implements your algorithm
• (1 point) Running time: give a brief analysis of the running time for the problem

Circular Queue

Implementation considerations:

• Array or linked list?
• How do we recognize the “front” and “back” of the queue?
• What happens to the “front” and “back” if we insert into a full queue?
• How do we recognize if the queue is empty? Let’s try to implement this together.

Let’s implement this together.

Definitions

• arity: the maximum number of children a node in a tree has. (This might not be defined on an infinite tree). A tree of arity 2 is called a binary tree.
• leaf: a node which has no children.
• path: a path in a tree is a set of nodes \(n_1, n_2, \ldots, n_k\) such that each \(n_i\) is the parent of \(n_{i+1}\). This path has length \(k −1\), because there are \(k − 1\) steps to go from \(n_1\) to \(n_k\).
• height: the height of a tree is the length of the longest path starting at the root and ending at a leaf.

Picture

Search Trees

Idea: a binary search tree has the following property for any node:

• all data in left subtree is \(\leq\) the data in the node
• all data in the right subtree are \(\geq\) the data in the node.

Implementation

Check Replit for a quick BinaryTree implementation. Let’s test it out.

BinaryTree<Integer> tree = new BinaryTree<>();
tree.insert(5);
tree.insert(10);
tree.insert(-5);
tree.insert(0);
tree.insert(100);
tree.printTree();