UIL CS Contest Session 3

UIL Computer Science Contest Session 10:50 AM - 11:35 AM

Session 206: 10:50 AM - 11:35 AM

Basic Data Structures and Algorithms

You have to know your basic algorithms in sorting, searching and merging.

These are the data structures that you will be tested on - Stacks, Queues, Linked Lists, Binary Search Trees, Heaps, and Graphs. Here are resources on data structures to get you started:

Classes of Algorithms

There are four classes of algorithms that you must be familiar with

Brute Force — Try every possible solution one by one until you find the one that works, without trying to be clever about it. It's simple to write but often too slow for large inputs.
Greedy — Make the choice that looks best right now at each step, and never go back to reconsider it. This is fast and works well for some problems, but it can miss the overall best solution if an early "good" choice turns out to block a better one later.
Divide and Conquer — Break a problem into smaller pieces of the same problem, solve each piece (often recursively), and then combine the results. Merge sort and binary search are classic examples of this approach.
Dynamic Programming — Break a problem into overlapping subproblems, solve each subproblem once, and store ("memoize") the answers so you never redo the same work twice. It's useful when brute force would repeat the same calculations over and over.

Here is a brief discussion on these four classes of algorithms.

Recursion

Some of the more difficult problems in the UIL Written Test involves tracing recursive code. There are some problems on the programming contest that can only be solved through recursion. Here are some resources to get you started:

Tips for tracing recursive code by hand:

Find the base case first. Identify the condition that stops the recursion and returns a value directly, without calling the function again.
Draw a call stack. Write down each call on its own line, indenting a little further each time the function calls itself, so you can see how deep the recursion goes.
Track the parameters at each level. Write down the actual argument values passed into each call — don't just write the function name, since the values are what change from call to call.
Work from the bottom up. Once you reach the base case, start returning values back up the stack one level at a time, plugging each returned value into the call that is waiting for it.
Watch for multiple recursive calls. If a function calls itself more than once (like in a tree or Fibonacci-style recursion), trace one full branch at a time instead of trying to juggle every branch at once.
Keep a small table. For problems with several variables, a table with one row per call and one column per variable can keep you from losing track of state.

Special Topics

There are two special topics that you might see on the written test.

Regular Expressions (Regex): A regular expression is a pattern made of characters and symbols that describes a set of strings, used to search, match, or validate text. For example, the pattern [0-9]+ matches one or more digits in a row, so it would match "42" or "2026" but not "abc".

Lambda Expressions: A lambda expression is a short, unnamed function that you can write inline and pass around like a value, instead of writing a full method with a name. For example, in Java, (a, b) -> a + b is a lambda that takes two parameters and returns their sum, and it's often used as a quick way to define behavior for things like sorting or filtering a list.