ACSL Category Descriptions - User contributions [en]

Assembly Language Programming

2020-08-29T17:27:30Z

Raj Joshi: /* Video Resources */

Programs written in high-level languages are traditionally converted by compilers into assembly language, which is turned into machine language programs – sequences of 1’s and 0’s – by an assembler. Even today, with very good quality compilers available, there is the need for programmers to understand assembly language. First, it provides programmers with a better understanding of the compiler and its constraints. Second, on occasion, programmers find themselves needing to program directly in assembly language in order to meet constraints in execution speed or space.

ACSL chose to define its own assembly language rather than use a “real” one in order to eliminate the many sticky details associated with real languages. The basic concepts of our ACSL topic description are common to all assembly languages.

== Reference Manual ==

Execution starts at the first line of the program and continues sequentially, except for branch instructions (BG, BE, BL, BU), until the end instruction (END) is encountered. The result of each operation is stored in a special word of memory, called the “accumulator” (ACC). The initial value of the ACC is 0. Each line of an assembly language program has the following fields:

LABEL OPCODE LOC

The LABEL field, if present, is an alphanumeric character string beginning in the first column. A label must begin with an alphabetic character(A through Z, or a through z), and labels are case-sensitive. Valid OPCODEs are listed in the chart below; they are also case-sensitive and uppercase. Opcodes are reserved words of the language and (the uppercase version) many not be used a label. The LOC field is either a reference to a label or ''immediate data''. For example, “LOAD A” would put the contents referenced by the label “A” into the ACC; “LOAD =123” would store the value 123 in the ACC. Only those instructions that do not modify the LOC field can use the “immediate data” format. In the following chart, they are indicated by an asterisk in the first column.

{| class="wikitable" style="text-align: left"|
|-
!OP CODE
!DESCRIPTION

|-
!*LOAD
|The contents of LOC are placed in the ACC. LOC is unchanged.

|-
!STORE
|The contents of the ACC are placed in the LOC. ACC is unchanged.

|-
!*ADD
|The contents of LOC are added to the contents of the ACC. The sum is stored in the ACC. LOC is unchanged. Addition is modulo 1,000,000.

|-
!*SUB
|The contents of LOC are subtracted from the contents of the ACC. The difference is stored in the ACC. LOC is unchanged. Subtraction is modulo 1,000,000.

|-
!*MULT
|The contents of LOC are multiplied by the contents of the ACC. The product is stored in the ACC. LOC is unchanged. Multiplication is modulo 1,000,000.

|-
!*DIV
|The contents of LOC are divided into the contents of the ACC. The signed integer part of the quotient is stored in the ACC. LOC is unchanged.
.
|-
!BG
|
Branch to the instruction labeled with LOC if ACC>0.

|-
!BE
|
Branch to the instruction labeled with LOC if ACC=0.

|-
!BL
|
Branch to the instruction labeled with LOC if ACC<0.

|-
!BU
|Branch to the instruction labeled with LOC.

|-
!READ
|
Read a signed integer (modulo 1,000,000) into LOC.

|-
!PRINT
|
Print the contents of LOC.

|-
!DC
|
The value of the memory word defined by the LABEL field is defined to contain the specified constant. The LABEL field is mandatory for this opcode. The ACC is not modified.

|-
!END
|
Program terminates. LOC field is ignored and must be empty.
|}

== Sample Problems ==

=== Problem 1 ===

After the following program is executed,
what value is in location TEMP?

{|class="wikitable" style="text-align: left"
|TEMP || DC || 0
|-
|A||DC||8
|-
|B||DC||-2
|-
|C||DC||3
|-
| ||LOAD||B
|-
| ||MULT||C
|-
| ||ADD||A
|-
| ||DIV||B
|-
| ||SUB||A
|-
| ||STORE||TEMP
|-
| ||END||
|}

'''Solution:''' The ACC takes on values -2, -6, 2, -1, and -9 in that order. The last value, -9, is stored in location TEMP.

=== Problem 2 ===

If the following program has an input value
of N, what is the final value of X which is
computed? Express X as an algebraic
expression in terms of N.

{|class="wikitable" style="text-align: left"
| || READ || X
|-
| || LOAD || X
|-
|TOP || SUB || =1
|-
| || BE || DONE
|-
| || STORE || A
|-
| || MULT || X
|-
| || STORE || X
|-
| || LOAD || A
|-
| || BU || TOP
|-
|DONE || END ||
|}

'''Solution:''' This program loops between labels TOP and
DONE for A times. A has an initial value of X and subsequent terms of N,
then values of A-1, A-2, …, 1. Each time through the loop,
X is multiplied by the the current value of A.
Thus, X = A * (A-1) * (A-2) * … * 1 or X=A! or A factorial.
For example, 5! = 5 * 4 * 3 * 2 * 1 = 120. Since the
initial value of A is the number input (i.e. N),
the algebraic expression is X = N!.

== Video Resources ==

The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

{|
|-
| <youtube width="300" height="180">https://youtu.be/jn2TJ-sHVzY</youtube>
| [https://youtu.be/jn2TJ-sHVzY ACSL Math: Assembly Language Programming (Quick Coding Bytes)]

This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.

|-
| <youtube width="300" height="180">https://youtu.be/RUm3iHsbO3I</youtube>
| [https://youtu.be/RUm3iHsbO3I ''Intro to Assembly Language'' ('''CalculusNguyenify''')]

A general introduction into assembly language. In particular, it covers how it fits into the source code to an executable image pipeline.

|-
| <youtube width="300" height="180">https://youtu.be/i_JYT398O64</youtube>
| [https://youtu.be/i_JYT398O64 ''Syntax of ACSL Assembly Language'' ('''CalculusNguyenify''')]

A very nice introduction to this ACSL category.

|-
| <youtube width="300" height="180">https://youtu.be/NEQASUsZ0g4</youtube>
| [https://youtu.be/NEQASUsZ0g4 ''Examples'' ('''CalculusNguyenify''')]

Walks through a couple of ACSL Assembly language programs that have been used in previous contests.

|}



x

Graph Theory

2020-08-09T16:42:15Z

Raj Joshi: /* ACSL Videos */

Many problems are naturally formulated in terms of points and connections between them. For example, a computer network has PCs connected by cables, an airline map has cities connected by routes, and a school has rooms connected by hallways. A graph is a mathematical object which models such situations.

== Overview ==

A ''graph'' is a collection of vertices and edges. An ''edge'' is a connection between two ''vertices'' (sometimes referred to as ''nodes''). One can draw a graph by marking points for the vertices and drawing lines connecting them for the edges, but the graph is defined independently of the visual representation. For example, the following two drawings represent the same graph:

::[[File:Graph fig1a.svg|150px]] [[File:Graph fig1b.svg|150px]]

The precise way to represent this graph is to identify its set of vertices {A, B, C, D, E, F, G}, and its set of edges between these vertices {AB, AD, BD, CF, FG, GH, GE, HE}.

To be precise, the graph above is an ''undirected graph''; the edge from x to y is the same as from y to x.

== Terminology ==

A ''path'' from vertex x to y in a graph is a list of vertices, in which successive vertices are connected by edges in the graph. For example, FGHE is path from F to E in the graph above. A ''simple path'' is a path with no vertex repeated. For example, FGHEG is not a simple path.

A graph is ''connected'' if there is a path from every vertex to every other vertex in the graph. Intuitively, if the vertices were physical objects and the edges were strings connecting them, a connected graph would stay in one piece if picked up by any vertex. A graph which is not connected is made up of ''connected components''. For example, the graph above has two connected components: {A, B, D} and {C, E, F, G, H}.

A ''cycle'' is a path, which is simple except that the first and last vertex are the same (a path from a point back to itself). For example, the path HEGH is a cycle in our example. Vertices must be listed in the order that they are traveled to make the path; any of the vertices may be listed first. Thus, HEGH and EHGE are different ways to identify the same cycle. For clarity, we list the start / end vertex twice: once at the start of the cycle and once at the end.

We’ll denote the number of vertices in a given graph by V and the number of edges by E. Note that E can range anywhere from V to V2 (or V(V-1)/2 in an undirected graph). Graphs with all edges present are called ''complete graphs''; graphs with relatively few edges present (say less than V log(V)) are called ''sparse''; graphs with relatively few edges missing are called ''dense.''

== Trees ==

A graph with no cycles is called a ''tree''. There is only one path between any two nodes in a tree. A tree on N vertices contains exactly N-1 edges. A ''spanning tree'' of a graph is a subgraph that contains all the vertices and forms a tree. Minimal spanning trees can be found for weighted graphs (i.e. each edge has a cost or distance associated with it) in order to minimize the cost or distance across an entire network. A group of disconnected trees is called a ''forest.''

== Directed Graphs ==

''Directed graphs'' are graphs which have a direction associated with each edge. An edge xy in a directed graph can be used in a path that goes from x to y but not necessarily from y to x. For example, a directed graph similar to our example graph is drawn below:

[[File:Graph fig1a directed.svg|150px]]

This graph is defined as the set of vertices V = {A,B,C,D,E,F,G,H} and the set of edges {AB,AD,DA,DB,EG,GE,HG,HE,GF,CF,FC}. There is one directed path from G to C (namely, GFC); however, there are no directed paths from C to G. Note that a few of the edges have arrows on both ends, such as the edge between A and D. These dual arrows indicate that there is an edge in each direction, which essentially makes an undirected edge. An ''undirected graph'' can be thought of as a directed graph with all edges occurring in pairs in this way. A directed graph with no cycles is called a ''dag'' (directed acyclic graph).

== Adjacency Matrices ==

It is frequently convenient to represent a graph by a matrix, as shown in the second sample problem below. If we consider vertex A as 1, B as 2, etc., then a “one” in M at row ''i'' and column ''j'' indicates that there is an edge from vertex ''i'' to ''j''., whereas a "zero" indicates there is not an edge. If we raise M to the ''pth'' power, the resulting matrix indicates which paths of length ''p'' exist in the graph. The value in $M^p(i,j)$ is the number of paths from vertex ''i'' to vertex ''j''.

== Sample Problems ==

=== Problem 1 ===

Find the number of different cycles contained in the directed graph with vertices {A, B, C, D, E} and edges {AB, BA, BC, CD, DC, DB, DE}.

'''Solution:'''
The graph is as follows:

::[[File:graph sample1.svg|196px]]

By inspection, the cycles are: ABA, BCDB, and CDC. Thus, there are 3 cycles in the graph.


=== Problem 2===

In the following directed graph, find the total number of different paths from vertex A to vertex C of length 2 or 4.

::[[File:graph sample3.svg|128px]]

'''Solution:'''

Let matrix $M$ represent the graph. Recall that the number of paths from vertex $i$ to vertex $j$ of length $p$ equals $M^p[i,j]$. The values of $M$, $M^2$ and $M^4$ are:

[[File:matrix_s3.png]]

There is 1 path of length 2 from A to C (cell [1,3] in $M^2$)
and 3 paths of length 4 (cell [1,3] in $M^4$).

=== Problem 3 ===

Given the adjacency matrix, draw the directed graph.

[[File:matrix_s4.png]]

'''Solution:'''

There must be exactly 4 vertices: V = {A, B, C, D}. There must be be exactly 7 edges: E = {AB, AD, BA, BD, CA, DB, DC}. Here are two valid drawings of the graph:

: [[File:Graph sample4soln-a.svg|128px]] [[File:Graph sample4soln-d.svg|128px]]

== Video Resources ==

===ACSL Videos===

The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

{|
|-
| <youtube width="300" height="180">https://youtu.be/pWCuRRqBGvw</youtube>
| [https://youtu.be/pWCuRRqBGvw ''ACSL Math: Graph Theory'' ('''Raj Joshi''')]

This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.

|-
| <youtube width="300" height="180">https://youtu.be/H96Lo2q_FSk</youtube>
| [https://youtu.be/H96Lo2q_FSk ''ACSL - Graph Theory Worksheet 1'' ('''misterminich''')]

Shows the solution to the ACSL problem: '''Draw the directed graph with vertices A, B, C, D, E and the directed edges AB, BC, AD, BC, DC, ED, and EA.''
|-
| <youtube width="300" height="180">https://youtu.be/y1fdIb_oNG0</youtube>
| [https://youtu.be/y1fdIb_oNG0 ''ACSL Graph Theory Worksheet 3'' ('''misterminich''')]

Shows the solution to an ACSL problem asking to find how many paths of a specific length there are in a specific directed graph.
|-
| <youtube width="300" height="180">https://youtu.be/vtTCRMGB0K8</youtube>
| [https://youtu.be/vtTCRMGB0K8 ''Graph Theory ACSL Example Problem'' ('''Tangerine Code''')]

Shows the solution to an ACSL problem asking to find how many different cycles there are from a specific vertex in a specific directed graph.
|}

{|
|-
| <youtube width="300" height="180">https://youtu.be/ivhOH6crQ1w</youtube>
| [https://youtu.be/ivhOH6crQ1w ''ACSL Test Prep - Graph Theory'' ('''Mrs. Goopta''')]

A talked-over presentation discussing graph theory as needed for the American Computer Science League and its tests.
|}

===Other Videos===

There are dozens of YouTube videos that provide an introduction to graph theory. The following are a couple that we found particularly well done. Be aware that the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

{|
|-
| <youtube width="300" height="180">https://youtu.be/44sQJK4BycY</youtube>
| [https://youtu.be/44sQJK4BycY ''CS 106B Lecture: Graphs: basic concepts'']

This lecture from Stanford University is s wonderful introduction to graph theory. The lecture starts out with many examples of real world problems that are modeled by graphs, and then moves on to review basic terminology relating to graph theory.
|-
| <youtube width="300" height="180"> https://youtu.be/gXgEDyodOJU</youtube>
| [https://youtu.be/gXgEDyodOJU ''Data structures: Introduction to Graphs'' '''(mycodeschool)''']

A nice introduction to the fundamental concepts of graphs.

|}

What Does This Program Do?

2020-08-08T18:34:56Z

Raj Joshi:

Frequently, one must use or modify sections of another programmer’s code. Since the original author is often unavailable to explain his/her code, and documentation is, unfortunately,
not always available or sufficient, it is essential to be able to read and understand an arbitrary program.

This category presents a program and asks the student to determine that the program does. The programs are written using a pseudocode that
should be readily understandable by all programmers familiar with a high-level programming language, such as Python, Java, or C.

= Description of the ACSL Pseudo-code =

We will use the following constructs in writing this code for this topic in ACSL:

{| class="wikitable" style="text-align: left"
|-
!'''Construct'''
!'''Code Segment'''
|-
|Operators
|! (not) , ^ or ↑(exponent), *, / (real division), % (modulus), +, -, >, <, >=, <=, !=, ==, && (and), <math>||</math> (or) in that order of precedence
|-
|Functions
|abs(x) - absolute value, sqrt(x) - square root, int(x) - greatest integer <= x
|-
|Variables
|Start with a letter, only letters and digits
|-
|Sequential statements
|
{| class="wikitable" style="text-align: left"
|-
|INPUT variable
|-
|variable = expression (assignment)
|-
|OUTPUT variable
|}
|-
|Decision statements
|
{| class="wikitable" style="text-align: left"
|-
|IF boolean expression THEN
|-
|Statement(s)
|-
|ELSE (optional)
|-
|Statement(s)
|-
|END IF
|}
|-
|Indefinite Loop statements
|
{| class="wikitable" style="text-align: left"
|-
|WHILE Boolean expression
|-
| Statement(s)
|-
|END WHILE
|}
|-
|Definite Loop statements
|
{| class="wikitable" style="text-align: left"
|-
|FOR variable = start TO end STEP increment
|-
| Statement(s)
|-
|NEXT
|}
|-
|Arrays:
|1 dimensional arrays use a single subscript such as A(5). 2 dimensional arrays use (row, col) order such as A(2,3). Arrays can start at location 0 for 1 dimensional arrays and location (0,0) for 2 dimensional arrays. Most ACSL past problems start with either A(1) or A(1,1). The size of the array will usually be specified in the problem statement.
|-
|Strings:
|Strings can contain 0 or more characters and the indexed position starts with 0 at the first character. An empty string has a length of 0. Errors occur if accessing a character that is in a negative position or equal to the length of the string or larger. The len(A) function will find the length of the string which is the total number of characters. Strings are identified with surrounding double quotes. Use [ ] for identifying the characters in a substring of a given string as follows:
S = “ACSL WDTPD” (S has a length of 10 and D is at location 9)

S[:3] = “ACS” (take the first 3 characters starting on the left)

S[5:] = “WDTPD” (take the last 5 characters starting on the right)

S[2:6] = “SL WD” (take the characters starting at location 2 and ending at location 6)

S[0] = “A” (position 0 only).

String concatenation is accomplished using the + symbol
|}

The questions in this topic will cover any of the above constructs in the Intermediate and Senior Division. In the Junior Division, loops will not be included in contest 1; loops will be used in contest 2; strings will be used in contest 3; and arrays will be included in contest 4.

= Sample Problems =

== Problem 1 ==

After this program is executed, what is the value of B that is printed if the input values are 50 and 10?
<syntaxhighlight lang="text">
input H, R
B = 0
if H>48 then
B = B + (H - 48) * 2 * R
H = 48
end if
if H>40 then
B = B + (H - 40) * (3/2) * R
H = 40
end if
B = B + H * R
output B
</syntaxhighlight>
'''Solution:'''

This program computes an employee’s weekly salary, given the hourly rate (R) and the number of hours worked in the week (H). The employee is paid an hourly rate for the number of hours worked, up to 40, time and a half for the overtime hours, up to 48 hours, and double for all hours over 48. The table monitors variables B and H:
{| class="wikitable"
|-
! | B || H
|-
| | 0 || 50
|-
| | 40 || 48
|-
| | 160 || 40
|-
| | 560 || 40
|}

Therefore, the final value of B is 2*2*10 + 8*3/2*10 + 40*10 = 40 + 120 + 400 = 560.

== Problem 2 ==

After the following program is executed, what is the final value of NUM?
<syntaxhighlight lang="text">
A = “BANANAS”
NUM = 0: T = “”
for J = len(A) - 1 to 0 step –1
T = T + A[j]
next
for J = 0 to len(A) - 1
if A[J] == T[J] then NUM = NUM + 1
next
</syntaxhighlight>

'''Solution:'''

The program first stores the reverse of variable A into variable T and then counts the number of letters that are in the same position in both strings.
Variable NUM is incremented each time a character at position x of A is the same as the character in position x of string T. There are 5 such positions: 1, 2, 3, 4, and 5.

== Problem 3 ==

After the following program is executed, what is the final value of C[4]?
<syntaxhighlight lang="text">
A(0) = 12: A(1) = 41: A(2) = 52
A(3) = 57: A(4) = 77: A(5) = -100
B(0) = 17: B(1) = 34: B(20 = 81
J = 0: K = 0: N = 0
while A(J) > 0
while B(K) <= A(J)
C(N) = B(K)
N = N + 1
k = k + 1
end while
C(N) = A(J): N = N + 1: J = J + 1
end while
C(N) = B(K)
</syntaxhighlight>

'''Solution:'''

The following table traces the variables through the execution of the program.

{| class="wikitable"
|-
!J
!K
!N
!A(J)
!B(K)
!C(N)
|-
|0 || 0 || 0 || 12 || 17 || 12
|-
|1 || 0 || 1 || 41 || 17 || 17
|-
|1 || 1 || 2 || 41 || 34 || 34
|-
|1 || 2 || 3 || 41 || 81 || 41
|-
|2 || 2 || 4 || 52 || 81 || 52
|-
|3 || 2 || 5 || 57 || 81 || 57
|-
|4 || 2 || 6 || 77 || 81 || 77
|-
|5 || 2 || 7 || -100 || 81 || 81
|}

Thus, the value of C(4) is 52. Note that this program merges two arrays in increasing order into one array until a negative number is input.

= Video Resources =

The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

{|
|-
| <youtube width="300" height="180">https://youtu.be/IBlXLEWeHjc</youtube>
| [https://youtu.be/IBlXLEWeHjc ''ACSL Math: What Does This Program Do?'' ('''Raj Joshi''')]

This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.
|}

Bit-String Flicking

2020-07-21T13:25:20Z

Raj Joshi: /* Video Resources */

Bit strings (strings of binary digits) are frequently manipulated bit-by-bit using the logical operators '''not''', '''and''', '''or''', and '''xor'''. Bits strings are manipulated as a unit using '''shift''' and '''circulate''' operators. The bits on the left are called the ''most significant bits'' and those on the right are the ''least significant bits''.

Most high-level languages (e.g., Python, Java, C++), support bit-string operations. Programmers typically use bit strings to maintain a set of flags. Suppose that a program supports 8 options, each of which can be either “on” or “off”. One could maintain this information using an array of size 8, or one could use a single variable (if it is internally stored using at least 8 bits or 1 byte, which is usually the case) and represent each option with a single bit. In addition to saving space, the program is often cleaner if a single variable is involved rather than an array. Bits strings are often used to maintain a set where values are either in the set or not. Shifting of bits is also used to multiply or divide by powers of 2.

Mastering this topic is essential for systems programming, programming in assembly language, optimizing code, and hardware design.

== Operators==

=== Bitwise Operators ===

The logical operators are '''not''' (~ or $\neg$), '''and''' (&), '''or''' (|), and '''xor''' ($\oplus$). These operators should be familiar to ACSL students from the [[Boolean Algebra]] and [[Digital Electronics]] categories.

* '''not''' is a unary operator that performs logical negation on each bit. Bits that are 0 become 1, and those that are 1 become 0. For example: ~101110 has a value of 010001.

* '''and''' is a binary operator that performs the logical '''and''' of each bit in each of its operands. The '''and''' of two values is 1 only if both values are 1. For example, '''1011011 and 011001''' has a value of '''001001'''. The '''and''' function is often used to isolate the value of a bit in a bit-string or to clear the value of a bit in a bit-string.

* '''or''' is a binary operator that performs the logical '''or''' of each bit in each of its operands. The '''or''' of two values is 1 only if one or both values are 1. For example, '''1011011 or 011001''' has a value of '''111011'''. The '''or''' function is often use to force the value of a bit in a bit-string to be 1, if it isn't already.

* '''xor''' is a binary operator that performs the logical '''xor''' of each bit in each of its operands. The '''xor''' of two values is 1 if the values are different and 0 if they are the same. For example, 1011011 xor 011001 = 110010. The '''xor''' function is often used to change the value of a particular bit.

All binary operators (and, or, or xor) must operate on bit-strings that are of
the same length. If the operands are not the same
length, the shorter one is padded with 0's on the left as needed. For
example, '''11010 and 1110''' would have value of '''11010 and 01110 = 01010'''.

The following table summarizes the operators:

::{| class="wikitable" style="text-align: center"
|-
!<math>x</math>
!<math>y</math>
! '''not''' <math>x</math>
!<math>x</math> '''and''' <math>y</math>
!<math>x</math> '''or''' <math>y</math>
!<math>x</math> '''xor''' <math>y</math>
|-
!0
!0
| 1
| 0
| 0
| 0
|-
!0
!1
| 1
| 0
| 1
| 1
|-
!1
!0
| 0
| 0
| 1
| 1
|-
!1
!1
| 0
| 1
| 1
| 0
|}

=== Shift Operators ===

Logical shifts (LSHIFT-x and RSHIFT-x) “ripple” the bit-string x positions in the indicated direction, either to the left or to the right. Bits shifted out are lost; zeros are shifted in at the other end.

Circulates (RCIRC-x and LCIRC-x) “ripple” the bit string x positions in the indicated direction. As each bit is shifted out one end, it is shifted in at the other end. The effect of this is that the bits remain in the same order on the other side of the string.

The size of a bit-string does not change with shifts, or circulates. If any bit strings are initially of different lengths, all shorter ones are padded with zeros in the left bits until all strings are of the same length.

The following table gives some examples of these operations:

::{| class="wikitable" style="text-align: right"
|-
!x
!(LSHIFT-2 x)
!(RSHIFT-3 x)
!(LCIRC-3 x)
!(RCIRC-1 x)
|-
!01101
| 10100
| 00001
| 01011
| 10110
|-
!10
| 00
| 00
| 01
| 01
|-
!1110
| 1000
| 0001
| 0111
| 0111
|-
!1011011
| 1101100
| 0001011
| 1011101
| 1101101
|}

=== Order of Precedence ===

The order of precedence (from highest to lowest) is: NOT; SHIFT and CIRC; AND; XOR; and finally, OR. In other words, all unary operators are performed on a single operator first. Operators with equal precedence are evaluated left to right; all unary operators bind from right to left.

== Sample Problems ==

=== Problem 1 ===

Evaluate the following expression:
:(0101110 AND NOT 110110 OR (LSHIFT-3 101010))

'''Solution:'''
The expression evaluates as follows:
:(0101110 AND '''001001''' OR (LSHIFT-3 101010))
:('''001000''' OR (LSHIFT-3 101010))
:(001000 OR '''010000''')
:'''011000'''

=== Problem 2 ===

Evaluate the following expression:
:(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))

'''Solution:'''
The expression evaluates as follows, starting at the innermost parentheses:
:(RCIRC-2 01101) => 01011
:(LCIRC-4 01011) => 10101
:(RSHIFT-1 10101) = 01010

=== Problem 3 ===

List all possible values of x (5 bits long) that solve the following equation.
:(LSHIFT-1 (10110 XOR (RCIRC-3 x) AND 11011)) = 01100

'''Solution:'''
Since x is a string 5 bits long, represent it by abcde. (RCIRC-3 x) is cdeab which, when ANDed with 11011 gives cd0ab. This is XORed to 10110 to yield Cd1Ab (the capital letter is the NOT of its lower case).
Now, (LSHIFT-1 Cd1Ab) = d1Ab0 which has a value of 01100, we must have d=0, A=1 (hence a=0), b=0. Thus, the solution must be in the form 00*0*, where * is an “I-don’t-care”. The four possible values of x are: 00000, 00001, 00100 and 00101.

=== Problem 4 ===

Evaluate the following expression:
: ((RCIRC-14 (LCIRC-23 01101)) | (LSHIFT-1 10011) & (RSHIFT-2 10111))

'''Solution:'''
The problem can be rewritten as
: A | B & C
The AND has higher precedence than the OR.

The evaluation of expression A can be done in a straightforward way: (LCIRC-23 01101) is the same as (LCIRC-3 01101) which has a value of 01011, and (RCIRC-14 01011) is the same as (RCIRC-4 01011) which has a value of 10110. Another strategy is to offset the left and right circulates. So, ((RCIRC-14 (LCIRC-23 01101)) has the same value as (LCIRC-9 01101), which has the same value as (LCIRC-4 01101) which is also 11010.

Expressions B and C are pretty easy to evaluate:
:B = (LSHIFT-1 10011) = 00110
:C = (RSHIFT-2 10111) = 00101

The expression becomes
: A | B & C = 10110 | 00110 & 00101 = 10110 | 00100 = 10110

== Video Resources ==

The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

{|
|-
| <youtube width="300" height="180">https://youtu.be/0U6ogoQ5Hkk</youtube>
| [https://youtu.be/0U6ogoQ5Hkk "ACSL Math: Bit String Flicking" (Quick Coding Bytes)]

This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.

|-
| <youtube width="300" height="180">https://youtu.be/IeMsD3harrE</youtube>
| [https://youtu.be/IeMsD3harrE ''Bit String Flicking (Intro)'' ('''CalculusNguyenify''')]

A great two-part tutorial on this ACSL category. Part 1 covers bitwise operations AND, OR, NOT, and XOR.

|-
| <youtube width="300" height="180">https://youtu.be/jbKw8oYJPs4</youtube>
| [https://youtu.be/jbKw8oYJPs4 ''Bit String Flicking Shifts and Circs'' ('''CalculusNguyenify''')]

Part 2 covers logical shifts and circulate operations.

|-
| <youtube width="300" height="180">https://youtu.be/XNBcO25mgCw</youtube>
| [https://youtu.be/XNBcO25mgCw ''Bit String Flicking'' ('''Tangerine Code''')]

Shows the solution to the problem: (RSHIFT-3 (LCIRC-2 (NOT 10110)))

|-
| <youtube width="300" height="180">https://youtu.be/8J9AdxU5CW8</youtube>
| [https://youtu.be/8J9AdxU5CW8 ''Bit String Flicking by Ravi Yeluru'' ('''hemsra''')]

Walks through two problems from the Junior Division.

|-
| <youtube width="300" height="180">https://youtu.be/aa_lQ8gft60</youtube>
| [https://youtu.be/aa_lQ8gft60 ''ACSL BitString Flicking Contest 2 Worksheet 1'' ('''misterminich''')]

Solves a handful of problems given in previous years at the Intermediate Division level.

|}

Recursive Functions

2020-07-21T13:23:06Z

Raj Joshi: /* ACSL */

A definition that defines an object in terms of itself is said to be ''recursive''. In computer science, recursion refers to a function or subroutine that calls itself, and it is
a fundamental paradigm in programming. A recursive program is used for solving problems that can be broken down into sub-problems of the same type, doing so until
the problem is easy enough to solve directly.

== Examples ==

=== Fibonacci Numbers ===

A common recursive function that you’ve probably encountered is the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, and so on. That is, you get the next Fibonacci number by adding together the previous two. Mathematically, this is written as

$$f(N)=f(N-1)+f(N-2)$$

Try finding f(10). No doubt, you have the correct answer, because you intuitively stopped when you reach $f(1)$ and $f(0)$.
To be formal about this, we need to define when the recursion stops, called the ''base cases''.
The base cases for the Fibonacci function is $f(0)=0$, and $f(1)=1$. The typical way to write this function is as follows:
$$f(N)=\cases{N & if $N \le 1$\cr
f(N-1)+f(N-2) & if $N > 1$}$$

Here is a Python implementation of the Fibonacci function:

::<syntaxhighlight lang="python">
def Fibonacci(x):
if (x <= 1) return x
return Fibonacci(x-1) + Fibonacci(x-2)
</syntaxhighlight>

(As a challenge to the reader: How could you implement the Fibonacci function without using recursion?)

=== Factorial Function ===

Consider the factorial function, $n! = n * (n-1) * ... * 1$, with 0! defined as having a value of 1. We can define this recursively as follows:

$$f(x)=\cases
{1 & if $x=0$\cr
x*f(x-1) & if $x\gt 0$\cr
}$$

With this definition, the factorial of every non-negative integer can be found.

Here is a Python implementation of the factorial function:
::<syntaxhighlight lang="python">def Factorial(x):
if (x == 0) return 1
return x * Factorial(x-1)
</syntaxhighlight>

=== Some Definitions ===

A few definitions: ''Indirection recursion'' is when a function calls another function which eventually calls the original function. For example, A calls B, and then, before function B exits, function A is called (either by B or by a function that B calls). ''Single recursion'' is recursion with a single reference to itself, such as the factorial example above. ''Multiple recursion'', illustrated by the Fibonacci number function, is when a function has multiple self references. ''Infinite recursion'' is a recursive function that never returns because it keeps calling itself. The program will eventually crash with an ''out of memory'' error message of some sort.

This ACSL category focuses on mathematical recursive functions rather than programming algorithms. While many mathematical functions can be done iteratively more efficiently than they can be done recursively, many algorithms in computer science must be written recursively. The Tower of Hanoi which is referred to in one of the videos is a good example of this. Another example is given in the sample problems below.

== Sample Problems==

This ACSL category focuses on mathematical recursive functions rather than programming procedures; but you’ll see some of the latter.
You will typically be asked to evaluate a recursive function for some specific value.
It's important that you are careful and neat. Work your way down the recursive calls until there are no more calls, and then work your way back up.

=== Sample Problem 1 ===

'''Problem:''' Find $g(11)$ given the following
$$g(x)=\cases
{g(x-3)+1 & if $x>0$\cr
3x & otherwise\cr
}$$

'''Solution:'''

The evaluation proceeds top-down as follows:

$$\begin{align}
g(11)&=g(8)+1\cr
g(8)&=g(5)+1\cr
g(5)&=g(2)+1\cr
g(2)&=g(-1)+1\cr
g(-1)&=-3\cr
\end{align}$$

We now use what we know about $g(-1)$ to learn more values, working our way back "up" the recursion:
:We now know the value of $g(2): g(2)=-3+1=-2$
:We now know the value of $g(5): g(5)= -2+1=-1$
:We now know the value of $g(8): g(8) = -1+1=0$
:And finally, we now have the value of $g(11): g(11)=0+1=1$

=== Sample Problem 2 ===

'''Problem:''' Find the value of $h(13)$ given the following definition of $h$:

$$h(x)=\cases
{h(x-7)+1 & when $x>5$\cr
x & when $0 \le x \le 5$\cr
h(x+3) & when $x \lt 0$}$$

'''Solution:'''

$$\begin{align}
h(13) &= h(6)+1 & \text{top rule, since $x>5$}\cr
h(6) &= h(-1)+1 & \text{top rule, since $x>5$}\cr
h(-1)&= h(-1+3) =h(2)& \text{bottom rule, since $x<0$}\cr
h(2)&=2&\text{middle rule, since $0 \le x \le 5$}\cr
\end{align}$$

We now work our way back up the recursion, filling in values that have been computed.

:$h(-1) = h(2) = 2$
:$h(6)=h(-1)+1 = 2+1=3$
:$h(13)=h(6)+1= 3+1=4$

=== Sample Problem 3 ===

'''Problem:''' Find the value of $f(12,6)$ given the following definition of $f$:

$$f(x,y)=\cases
{f(x-y,y-1)+2 & when $x>y$\cr
x+y & otherwise}$$

'''Solution:'''

$$\begin{align}
f(12,6) &= f(6,5)+2 & \text{top rule, since $x>y$}\cr
f(6,5) &= f(1,4)+2 & \text{top rule, since $x>y$}\cr
f(1,4) &= 1+4 = 5& \text{bottom rule, since $x \le y$}\cr
\end{align}$$

We now work our way back up the recursion, filling in values that have been computed.

:$f(12,6) = f(6,5) + 2 = f(1,4) + 2 + 2 = 5 + 2 + 2 = 9$

=== Sample Problem 4 ===

'''Problem:''' Consider the following recursive algorithm for painting a square:

1. Given a square.
2. If the length of a side is less than 2 feet, then stop.
3. Divide the square into 4 equal size squares (i.e., draw a “plus” sign inside the square).
4. Paint one of these 4 small squares.
5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares.

If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted?

'''Solution:'''

In the first pass, we get four squares of side 8.
One is painted, three are unpainted.
Next, we have 3*4 squares of side 4.
Three are painted (area=3*42), nine are not.
Next, we have 9*4 squares of side 2.
Nine are painted (area = 9*22), 27 are not.
Finally, we have 27*4 squares of side 1.
Twenty-seven are painted.
Therefore, the total painted is 1*82 + 3*42 + 9*22 + 27*12 = 175.

== Online Resources ==

===ACSL===

The following videos show the solution to problems that have appeared in previous ACSL contests.

{|
|-
| <youtube width="300" height="180">https://youtu.be/YinptBVZNFM</youtube>
| [https://youtu.be/YinptBVZNFM "ACSL Math: Recursive Functions" (Quick Coding Bytes)]

This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.

|-
| <youtube width="300" height="180">https://youtu.be/OjZSIXStSr8</youtube>
| [https://youtu.be/OjZSIXStSr8 ''Recursion Example 1'' ('''CalculusNguyenify''')]

The video walks through the solution to a straight-forward single-variable recursive function, that is, $f(x)=\cases{....}$
The problem
appeared in ACSL Senior Division Contest #1, 2014-2015.

|-
| <youtube width="300" height="180">https://youtu.be/MWdGTVCLI8g</youtube>
| [https://youtu.be/MWdGTVCLI8g ''Recursion Example 2'' ('''CalculusNguyenify''')]

The video walks through the solution to a 2-variable recursive function, that is, $f(x,y)=\cases{....}$ . The problem
appeared in ACSL Senior Division Contest #1, 2014-2015.

|-
| <youtube width="300" height="180">https://youtu.be/5P5iK-5heEc</youtube>
| [https://youtu.be/5P5iK-5heEc ''Recursive Functions ACSL Example Problem'' ('''Tangerine Code''')]

The video walks through the solution to a 2-variable recursive function, that is, $f(x,y)=\cases{....}$ .

|-
| <youtube width="300" height="180">https://youtu.be/BGCGlpm7Cow</youtube>
| [https://youtu.be/BGCGlpm7Cow ''ACSL Recursive Functions Part -1 by Ravi Yeluru'' ('''mesra''')]

The first of 4 videos capturing Ravi Yeluru solving a handful of ACSL Recursive Function problems. Other videos are [[https://youtu.be/n5otUyH1j6A Part 2]], [[https://youtu.be/xHaHwNHlMj4 Part 3]], and [[https://youtu.be/vj2pvAL8tQQ Part 4]].
|}

===Other Videos===

Because recursion is such a fundamental concept in computer science, there is no end to the number of YouTube videos that cover the topic. There are dozens of walk-throughs of the factorial and Fibonacci functions, and of other classic algorithms such as Towers of Hanoi and Binary Trees.
Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

{|

|-
| <youtube width="300" height="180">https://youtu.be/LdNdfPhwCP4</youtube>
| [https://youtu.be/LdNdfPhwCP4 ''Recursion lecture 1'' ('''anim aland''')]

Prof. Alan Dorin from Monash University presents an wonderful introduction to recursion. The last part of the video uses factorial as an example. Taken note how his base case guards against infinite recursion.

|-
| <youtube width="300" height="180">https://youtu.be/dxyYP3BSdcQ</youtube>
| [https://youtu.be/dxyYP3BSdcQ ''Fibonacci Sequence - Anatomy of recursion and space complexity analysis'' ('''mycodeschool''')]

The video is hand-simulation on the whiteboard of the recursive code for computing a Fibonnaci number. The code uses a base case of <syntaxhighlight lang="python" inline>if n<=1 return n</syntaxhighlight> to prevent infinite recursion where the function called with a negative parameter.

|-
| <youtube width="300" height="180">https://youtu.be/rVPuzFYlfYE</youtube>
| [https://youtu.be/rVPuzFYlfYE ''Towers of Hanoi'' ('''Arnaldo Pedro Figueira Figueira''')]

A nice explanation of the Towers of Hanoi from MIT edX Course: [https://www.edx.org/course/subject/computer-science MITx: 6.00x Introduction to Computer Science and Programming].

|}

Prefix/Infix/Postfix Notation

2020-07-21T11:10:14Z

Raj Joshi: /* Video Resources */

The expression $5+\large{8\over{3-1}}$ clearly has a value of 9. It is written in ''infix'' notation as $5+8/(3-1)$. The value of an ''infix'' version is well-defined because there is a well-established order of precedence in mathematics: We first evaluate the parentheses (3-1=2); then, because division has higher precedence that subtraction, we next do 8/2=4. And finally, 5+4=9. The order of precedence is often given the mnemonic of '''Please excuse my dear Aunt Sue''', or '''PEMDAS''': '''p'''arentheses, '''e'''xponentiation, '''m'''ultiplication/'''d'''ivision, and '''a'''ddition/''''s'''ubtraction. Multiplication and division have the same level of precedence; addition and subtraction also have the same level of precedence. Terms with equals precedence are evaluated from left-to-right [https://en.wikipedia.org/wiki/Order_of_operations wikipedia].

The algorithm to evaluate an ''infix'' expression is complex, as it must address the order of precedence. Two alternative notations have been developed which lend themselves to simple computer algorithms for evaluating expressions. In ''prefix'' notation, each operator is placed before its operands . The expression above would be <syntaxhighlight lang="python" inline>+ 5 / 8 - 3 1</syntaxhighlight>. In ''postfix'' notation, each operator is placed after its operand. The expression above is <syntaxhighlight lang="python" inline>5 8 3 1 - / +</syntaxhighlight>. In ''prefix'' and ''postfix'' notations, there is no notion of order of precedence, nor are there any parentheses. The evaluation is the same regardless of the operators.

Problems in this category ask to convert between prefix, infix, and postfix, or to evaluate an expression in prefix or postfix.

== Converting Expressions ==

An algorithm for converting from infix to prefix (postfix) is as follows:
* Fully parenthesize the infix expression. It should now consist solely of “terms”: a binary operator sandwiched between two operands.
* Write down the operands in the same order that they appear in the infix expression.
* Look at each term in the infix expression in the order that one would evaluate them, i.e., inner-most parenthesis to outer-most and left to right among terms of the same depth.
* For each term, write down the operand before (after) the operators.

One way to convert from prefix (postfix) to infix is to make repeated scans through the expression.
Each scan, find an operator with two adjacent operators and replace it with a parenthesized infix expression.
This is not the most efficient algorithm, but works well for a human.

A quick check for determining whether a conversion is correct is to convert the result back into the original format.

== Context ==

''Prefix'' and ''postfix'' notation is also known as [https://en.wikipedia.org/wiki/Polish_notation ''Polish'' and ''Reverse Polish'' notation], respectively.

== Examples ==

=== Infix to Prefix ===

The following sequence of steps illustrates converting $X=\left(AB-{C\over{D}}\right)^E$ from infix to prefix:
::{| class="wikitable" style="text-align: center"
|-
!(X = (((A * B) - (C / D)) ↑ E))
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" |X A B C D E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>* A B</syntaxhighlight> C D E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>* A B</syntaxhighlight> <syntaxhighlight lang="python" inline>/ C D</syntaxhighlight> E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>- * A B / C D</syntaxhighlight> E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>↑- * A B / C D E</syntaxhighlight>
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | <syntaxhighlight lang="python" inline>= X ↑ - * A B / C D E</syntaxhighlight>
|}

=== Infix to Postfix ===

The following sequence of steps illustrates converting $X=\left(AB-{C\over{D}}\right)^E$ from infix to postfix:
::{| class="wikitable" style="text-align: center"
|-
!(X = (((A * B) - (C / D)) ↑ E))
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" |X A B C D E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>A B *</syntaxhighlight> C D E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>A B *</syntaxhighlight> <syntaxhighlight lang="python" inline>C D /</syntaxhighlight> E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>A B * C D / -</syntaxhighlight> E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>A B * C D / - E ↑</syntaxhighlight>
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | <syntaxhighlight lang="python" inline> X A B * C D / - E ↑ =</syntaxhighlight>
|}

=== Prefix to Infix ===

The following sequence of steps illustrates converting $(3*4+{8\over{2}})^{(7-5)}$ from its prefix representation to infix:
::{| class="wikitable" style="text-align: left"
|-
! ↑ + * 3 4 / 8 2 – 7 5
|-
| style="background-color: #ffffff" | ↑ + <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> / 8 2 – 7 5
|-
| style="background-color: #ffffff" |↑ + <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> <syntaxhighlight lang="python" inline>(8/2)</syntaxhighlight> – 7 5
|-
| style="background-color: #ffffff" |↑ <syntaxhighlight lang="python" inline>(3*4)+(8/2)</syntaxhighlight> - 7 5
|-
| style="background-color: #ffffff" |↑ <syntaxhighlight lang="python" inline>((3*4)+(8/2))</syntaxhighlight> <syntaxhighlight lang="python" inline>(7-5)</syntaxhighlight>
|-
| style="background-color: #ffffff" |<syntaxhighlight lang="python" inline>(((3*4)+(8/2))↑(7-5))</syntaxhighlight>
|}

=== Postfix to Infix ===

The following sequence of steps illustrates converting $(3*4+{8\over{2}})^{(7-5)}$ from its postfix representation to infix:
::{| class="wikitable" style="text-align: left"
|-
!3 4 * 8 2 / + 7 5 -↑
|-
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> 8 2 / + 7 5 - ↑
|-
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> <syntaxhighlight lang="python" inline>(8/2)</syntaxhighlight> + 7 5 - ↑
|-
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>((3*4)+(8/2))</syntaxhighlight> 7 5 -↑
|-
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>((3*4)+(8/2))</syntaxhighlight> <syntaxhighlight lang="python" inline>(7-5)</syntaxhighlight> ↑
|-
| style="background-color: #ffffff" |<syntaxhighlight lang="python" inline>(((3*4)+(8/2))↑(7-5))</syntaxhighlight>
|}

== Video Resources ==

The following YouTube videos show ACSL students and advisors working out some previous problems.

{|
|-
| <youtube width="300" height="180">https://youtu.be/9UO5aDyHZ84</youtube>
| [https://youtu.be/9UO5aDyHZ84 "ACSL Math: Prefix/Infix/Postfix Notation" (Quick Coding Bytes)]

This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.

|-
| <youtube width="300" height="180">https://youtu.be/Lj91oRv3EIY</youtube>
| [https://youtu.be/Lj91oRv3EIY ''ACSL Prep - Mrs. Gupta - Prefix Infix Postfix'' ('''MegaChristian5555''')]

This video starts with a nice introduction to the category, and then solves a handful of practice problems.

|-
| <youtube width="300" height="180">https://youtu.be/lDm08rP_lms</youtube>
| [https://youtu.be/lDm08rP_lms ''ACSL Prefix Postfix Infix Contest 2 Worksheet 1'' ('''misterminich''')]

Mr. Minich is an ACSL advisor. This video was created to help prepare his students for the ACSL Prefix/Infix/Postfix category. It shows solutions to 5 different problems that have
appeared in recent years.

|-
| <youtube width="300" height="180">https://youtu.be/4YZdsw2UOpo</youtube>
| [https://youtu.be/4YZdsw2UOpo ''Prefix Notation'' ('''Tangerine Code''')]

To quote the video description: ''A general tutorial on prefix notation that can be used for American Computer Science League.''

|-
| <youtube width="300" height="180">https://youtu.be/R-t9-rbJDw8</youtube>
| [https://youtu.be/R-t9-rbJDw8 ''Postfix Notation'' ('''Tangerine Code''')]

To quote the video description: ''A general tutorial on postfix notation that can be used for American Computer Science League.''

|-
| <youtube width="300" height="180">https://youtu.be/dcc-nXY2L6c</youtube>
| [https://youtu.be/dcc-nXY2L6c ''2015 16 Contest 2 Prefix Infix Postfix Problem#1'' ('''Ravi Yeluru''')]

Ravi Yeluru walks through the solution to an ACSL Prefix/Infix/Postfix program that appeared in the 2015-16 year, Contest #2.

|-
| <youtube width="300" height="180">https://youtu.be/lEIPvUqstEY</youtube>
| [https://youtu.be/lEIPvUqstEY ''2015 16 Contest 2 Prefix Infix Postfix Problem#2'' ('''Ravi Yeluru''')]

Ravi Yeluru walks through the solution to an ACSL Prefix/Infix/Postfix program that appeared in the 2015-16 year, Contest #2.

|}

=== Other Videos ===

The following YouTube videos cover various aspects of this topic; they were created by authors who are not involved (or aware) of ACSL, to the best of our knowledge. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

{|
|-
| <youtube width="300" height="180">https://youtu.be/t7YWDiz8LMY</youtube>
| [https://youtu.be/t7YWDiz8LMY ''Infix Postfix and Prefix Notation'' ('''Carleton Moore''')]

A very gentle overview of infix, prefix, and postfix.

|-
| <youtube width="300" height="180">https://youtu.be/z3VsmufB_QI</youtube>
| [https://youtu.be/z3VsmufB_Q I''Infix Prefix and Postfix'' ('''University Academy''')]

Another very gentle overview of infix, prefix, and postfix.

|-
| <youtube width="300" height="180">https://youtu.be/jos1Flt21is</youtube>
| [https://youtu.be/jos1Flt21is ''Infix Postfix and Prefix Notation'' ('''mycodeschool''')]

Another overview of infix, prefix, and postfix notations.

|-
| <youtube width="300" height="180">https://youtu.be/MeRb_1bddWg</youtube>
| [https://youtu.be/MeRb_1bddWg ''Evaluation of Prefix and Postfix expressions using stack'' ('''mycodeschool''')]

Describes the standard algorithm to evaluate prefix and postfix expressions.

|-
| <youtube width="300" height="180">https://youtu.be/vq-nUF0G4fI</youtube>
| [https://youtu.be/vq-nUF0G4fI ''Infix to Postfix using stack'' ('''mycodeschool''')]

Describes the standard algorithm to convert from infix to postfix.
|}