American Computer Science League Contests

You may want to look at previous problems from old ACSL contests while you are learning the topics below. I find it helpful to test my understanding by trying an old problem while I'm learning something new!

Boolean Algebra

Boolean Algebra Tutorial Video

General Boolean Algebra Tutorial

Order of Operations

Boolean Algebra Identities

Symbols Used:

  1. $ A + B = B + A $
  2. $ A * B = B * A $
  3. $ A + (B + C) = (A + B) + C $
  4. $ A * (B * C) = (A * B) * C $
  5. $ A * (B + C) = A * B + A * C $
  6. $ \overline{A+B} =\overline{A}*\overline{B} $
  7. $ \overline{A*B} =\overline{A}+\overline{B} $
  8. $ A + 0 = A $
  9. $ A * 0 = 0 $
  10. $ A + 1 = 1 $
  11. $ A * 1 = A $
  12. $ A + \overline{A} = 1 $
  13. $ A * \overline{A} = 0 $
  14. $ A + A = A $
  15. $ A * A = A $
  16. $ \overline{\overline{A}} = A $
  17. $ A + \overline{A} * B = A + B $
  18. $ (A + B) * (C + D) = A * C + A * D + B * C + B * D $
  19. $ (A + B) * (A + C) = A + B * C $
  20. $ A * (A + B) = A $
  21. $ A \oplus B = A * \overline{B} + \overline{A} * B $
  22. $ \overline{A \oplus B} = \overline{A} \oplus B = A \oplus \overline{B} $

ACSL Overview

You might find it helpful to read the overview of boolean algebra from the ACSL.

Data Structures

Data Structures Tutorial Videos

Construct a Binary Search Tree

Internal Path Length of Binary Search Tree

Stacks and Queues

Key Things to Remember

ACSL Overview

You might find it helpful to read the overview of data structures from the ACSL.

Regular Expressions

Can be used to find patterns. We can convert between an algebraic expression of the regular expression, or a FSA (Finite State Automaton) representation.

Regular Expression Tutorial Video

Convert Regular Expression to Finite-State Automaton

Quick Examples

Given the regular expression 10*1, we can represent it as the following FSA:

This matches any expression that begins with a 1, has any number of 0's (including none), then ends with a 1. Some examples of this include:

Given the regular expression 11*01(101)*101*, we can represent it as the following FSA:

This matches any expression that:

A few examples of expressions that would match this include:

ACSL Overview

You might find it helpful to read the overview of regular expressions from the ACSL.