ACSL Contest 2

ACSL Jan 15, 2020

In ACSL Contest 2, you would face the questions covering the following three topics.

Question TypeNumber of Questions
Pre/Post/Infix Notation2
Bit-String Flicking2
LISP Programming1

These topics would be covered in the following pages.

Next page: Pre/Post/Infix Notation

[latexpage]

Pre/Post/Infix Notation

For this type of question, you would have to convert between different notations of expression or evaluate the expression provided. We would provide a brief introduction to the notations and then we will present the methods to covert them.

Introduction to different notations

When the computer processes an expression, it could be expressed in three ways, which are called just as the top heading suggested. These different notations are connected with binary trees. In most cases, we are using the infix notation, in which the binary operators are placed between the two numbers. A basic example would be the following expression:

However, there are two other ways of presenting the notations. The first one is called prefix notation, in which the binary operators are placed in front of the two numbers. An example would be the following:

The other type would be postfix notation, in which the binary operators are placed at the end of the two numbers. An example would be this:

They seemed to be irrelevant at first glance, but, after I tell you about the conversion in the following sections, you would found that the above three examples are actually the same thing.

Conversions between the different notations

When converting different notations, we often use the infix notation as a bridge during conversion. The following sections would show you how to present the different conversions.

Conversions between prefix and infix notations

When converting from prefix to infix notations, a good way would be trying to convert the sections which strictly follows the ‘operator-number1-number2‘ pattern. Let’s look at the following prefix expression example:

In order to convert this to infix notation, we could try to use the method I mentioned above. Notice that in most cases in ACSL, the $\uparrow$ represents the power function, where the first number is the base and the second is the exponential. So now let’s just get started. We would transverse the entire list of symbols until we reach finally an infix notation.

The complete process of converting between prefix and infix notations

It might seem useful at first glance, but you would never be asked this type of question in the exam since its too easy. Instead, you would be asked to evaluate the prefix notation, which would be easier as you could use the result in every step instead. Let’s look at the following past paper question with its year indicated in the picture for Senior Contest.

To be honest, you could just follow the following steps to reach the results:

For the other way round, more questions occur as the infix notation could be quite complicated. Let’s look at the following example as a glance to how these type questions would be like:

At first glance, you might be scared by this question. But don’t panic. Just as the saying says, the best way to overcome the difficulty is to face it directly. Hence we could first try to remove the fraction lines and the square root symbols and convert them during the process. The following is the complete process during the expansion of the expression.

It is not ‘so’ difficult

That’s all for converting between prefix and infix notations.

Converting between postfix and infix notations

When converting between postfix and infix notations, you would need basically the same skills as above, except always remember to look for number1-number2-operator when you are converting and put the operator at the back when you are converting to the postfix notations.

Converting between prefix and postfix notations

For this type of question, you could just use the infix notation as a bridge to convert.

Next Page: Bit-String Flicking

Bit-String Flicking

There is basically a table of commands that you shall remember as the commands:

CommandExplainationExamples using 10001 and n=3
RCIRC-nBasically means ‘Right CIRCular’
Shift the entire string to the right and move the rest to the left
RCIRC-3 10001
=00110
LCIRC-nBasically means ‘Left CIRCular’
Shift the entire string to the left and move the rest to the right
LCIRC-3 10001
=01100
RSHIFT-nShift the entire string to the right and put 0 for empty spacesRSHIFT-3 10001
=00100
RSHIFT-nShift the entire string to the left and put 0 for empty spacesLSHIFT-3 10001
=00100
ANDand operation for every bit
ORor operation for every bit
NOTnot operation for every bit
XORxor operation for every bit
(same=0,different=1)

[latexpage]

LISP Programming

For this part, you would have to remember the following function:

DescriptionExplainationExample
ADD(n1,n2)$n1+n2$
SUB(n1,n2)$n1-n2$
MULT(n1,n2)$n1 * n2$
DIV(n1,n2)$n1/ n2$
EXP(n1,n2)$n1^{n2}$
SQUARE(n)$n^{2}$
SET identifier listassign the list value to the identifierSET X (1 (23) 4)
CAR(list)return the first element of the listCAR X=1
CDR(list)return the list without its fist elementCDR X=((23) 4)
REVERSE(list)reverse the listREVERSE X=(4 (23) 1)
CON(var1,var2)connect two variables to form a listCON(X,5)=(1 (23) 4 5)

I’m truely sorry for the uncomplete of this post for the lack of time. The rest two sections only contains the most essential information. I might update this post during the holiday later.

Daniel – author of this post

Daniel Zhao

The greatest pigeon in SCIE who would always gugugu whenever, wherever, and whatever.

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.