UIL CS: Collections & Algorithms

This is part of the UIL CS study series. See also:

Main topic list: https://www.uiltexas.org/files/academics/UILCS-JavaTopicList2526.pdf

7. Regex Patterns (most common + how used)

In Java:

  • s.matches(regex) must match entire string
  • Use Pattern and Matcher for searching
String s = "insert regex pattern here";
String t = "match me to a regex";
Pattern pattern = Pattern.compile(s);
Matcher matcher = pattern.matcher(t);

Common patterns

PatternMeaning
.any char
\ddigit
\Dnot digit
\wword char [A-Za-z0-9_]
\Wnot word
\swhitespace
\Snot whitespace
\bword boundary (position between \w and \W)
|alternation (matches before and after, like a logical OR)
(?:...)non-capturing group
(?=...)positive lookahead
(?!...)negative lookahead
(?<=...)positive lookbehind
(?<!...)negative lookbehind

Note: ? after a quantifier (*, +, ?) is non-greedy/lazy.

Examples

"12345".matches("\\d+");       // true
"12a45".matches("\\d+");       // false

"abc".matches("[a-z]{3}");     // true
"ABC".matches("[a-z]{3}");     // false

"hello@gmail.com".matches("\\w+@\\w+\\.com"); // true-ish (simplified)

"   ".matches("\\s+");         // true

14. Collections & Common Methods

List / ArrayList

  • Add/insert: add(E) / add(index, E).
  • Access: get(index).
  • Remove: remove(index) or remove(Object).
  • Size: size().
  • Example: Removing and adding values changes order.

Stack

  • Push: push(E) or add(E) on a Stack.
  • Pop: pop().
  • Peek: peek() returns top.
  • LIFO behavior.

Collections Utility Methods

  • Rotate lists: Collections.rotate(list, k).
  • Remove by condition: removeIf(predicate).

Maps and Sets

  • Basic behaviors: HashMap, TreeMap, HashSet, TreeSet.
  • Key methods: put(key, value), get(key), containsKey(key), contains(), size().

16. Trees & Graphs

Binary Search Trees: Insert order affects shape. Tree properties: internal nodes vs leaves, diameter. Complexity: worst-case search in unbalanced BST is O(n)O(n).

17. Postfix notation (Reverse Polish) with example

Polish notation reference: https://www.uilexas.org/files/academics/UILCS-PolishNotation-Examples.pdf

Definition

Postfix places operators after operands.

  • Infix: 3+43 + 4
  • Postfix: 3 4 +3\ 4\ +

Evaluate using a stack:

  • push numbers
  • when operator appears: pop two operands, apply, push result

Example

Evaluate postfix: 5 2 3 ∗ + 4 −5\ 2\ 3\ *\ +\ 4\ -

Steps:

  • push 5→[5]5 \rightarrow [5]
  • push 2→[5,2]2 \rightarrow [5,2]
  • push 3→[5,2,3]3 \rightarrow [5,2,3]
  • ∗*: pop 33 and 2→2∗3=6→[5,6]2 \rightarrow 2*3=6 \rightarrow [5,6]
  • ++: pop 66 and 5→5+6=11→[11]5 \rightarrow 5+6=11 \rightarrow [11]
  • push 4→[11,4]4 \rightarrow [11,4]
  • −-: pop 44 and 11→11−4=7→[7]11 \rightarrow 11-4=7 \rightarrow [7]

Answer: 77

18. Algorithms/Complexity

  • Understand basic time complexity (e.g., BFS, simple loops).
  • Recognize inefficiencies (e.g., nested loops →O(n2)\rightarrow O(n^2)).
  • Recognize linear vs logarithmic vs polynomial behavior.

19. Miscellaneous

  • String methods: length(), substring(), split(), toLowerCase(), matches().
  • Math class: ceil, floor, pow, min, max.
  • Scanner: input parsing: nextInt(), nextLine().