Difference between revisions of "What Does This Program Do?"

From ACSL Category Descriptions
Jump to navigation Jump to search
 
(31 intermediate revisions by 5 users not shown)
Line 1: Line 1:
Frequently, one must use or modify sections of another programmer’s code. Since the original author is often unavailable to explain his/her code, it is essential to be able to read and understand an arbitrary program.  This category has been rewritten using pseudocode similar to the design of the AP CS Principles course.  Pseudo-code is English-like, language independent algorithmic code and should be able to be traced by students regardless of whether they are familiar with BASIC, C++, Java, Python, or any other high level language.
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.   


= Description of Pseudo-code =
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:
We will use the following constructs in writing this code for this topic in ACSL:
Line 11: Line 15:
|-
|-
|Operators
|Operators
|! (not) , ^ (exponent), *, / (real division), % (modulus), +, -, >, <, >=, <=, !=, ==, && (and), || (or) in that order of precedence
|! (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
|Variables
Line 17: Line 24:
|-
|-
|Sequential statements
|Sequential statements
|
{| class="wikitable" style="text-align: left"
|-
|INPUT variable
|INPUT variable
variable = expression (assignment)
|-
OUTPUT variable
|variable = expression (assignment)
|-
|OUTPUT variable
|}
|-
|-
|Decision statements
|Decision statements
|IF boolean expression
|
    Statement(s)
{| class="wikitable" style="text-align: left"
ELSE  (optional)
|-
    Statement(s)
|IF boolean expression THEN
END IF
|-
|Statement(s)
|-
|ELSE  (optional)
|-
|Statement(s)
|-
|END IF
|}
|-
|-
|Indefinite Loop statements
|Indefinite Loop statements
|
{| class="wikitable" style="text-align: left"
|-
|WHILE Boolean expression
|WHILE Boolean expression
    Statement(s)
|-
END WHILE
|    Statement(s)
|-
|END WHILE
|}
|-
|-
|Definite Loop statements
|Definite Loop statements
|
{| class="wikitable" style="text-align: left"
|-
|FOR variable = start TO end STEP increment
|FOR variable = start TO end STEP increment
    Statement(s)
|-
NEXT
|    Statement(s)
|-
|NEXT
|}
|-
|-
|Arrays:
|Arrays:
|1D arrays use a single subscript such as A[5].
|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.
  2D arrays use row major order starting with [0,0] in the upper left corner.
  Use [] for identifying the subscript(s) so that A[5] is the 6th item in a list
  and A[2,3] is row 2 (third row) and column 3 (4th column).
  The size of the array will be specified in the problem statement.
|-
|-
|Strings:
|Strings:
|They can contain 0 or more characters and the indexed position starts with 0 as
|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:
the first character.  An empty string has a length of 0.  Errors occur if accessing
S = “ACSL WDTPD” (S has a length of 10 and D is at location 9)
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
S[:3] = “ACS” (take the first 3 characters starting on the left)  
total characters.  Strings are identified with surrounding double quotes.
 
Use [] for identifying the characters in a substring of a given string as follows:
S[4:] = “DTPD” (take the last 4 characters starting on the right)  
    If S = “ACSL WDTPD”, then
 
    S[:3] = “ACSL”      (positions 0 to 3)
S[2:6] = “SL WD” (take the characters starting at location 2 and ending at location 6)
    S[5:] = “WDTPD”      (positions 5 to 9)
 
    S[2:6] = “SL WD”     (positions 2 to 6)
S[0] = “A” (position 0 only).
    S[0] = “A”           (position 0 only)
 
The value of len(A) is 10.
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.  Line numbers will be included for the purpose of explaining the solution.
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 =
= Sample Problems =


== Sample Problem 1 ==
== Problem 1 ==


After this program is executed, what is the value of B that is printed if the input values are 50 and 10?
After this program is executed, what is the value of B that is printed if the input values are 50 and 10?
::10 input H, R
<syntaxhighlight lang="text">
::20 B = 0
input H, R
::30 if H>48 then
B = 0
::40      B = B + (H - 48) * 2 * R
if H>48 then
::50      H = 48
    B = B + (H - 48) * 2 * R
::60 end if
    H = 48
::70 if H>40 then
end if
::80      B = B + (H - 40) * (3/2) * R
if H>40 then
::90      H = 40
  B = B + (H - 40) * (3/2) * R
::100 end if
  H = 40
::110 B = B + H * R
end if
::120 output B
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
|}


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:
:LINE      B      H
:  20      0      50
:  50    40      48
:  90    160      40
: 110    560      40
Therefore, the final value of B is 2*2*10 + 8*3/2*10 + 40*10 = 40 + 120 + 400 = 560.
Therefore, the final value of B is 2*2*10 + 8*3/2*10 + 40*10 = 40 + 120 + 400 = 560.


== Sample Problem 2 ==
== Problem 2 ==


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


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.
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.
A B A N A N A S
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.
T S A N A N A B
* * * * *
Those positions marked with an asterisk contribute one to the value of NUM. There are 5 such positions.  


== Sample Problem 3 ==
== Problem 3 ==


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


Solution: The following table traces the variables through the execution of the program.
'''Solution:'''


{|
The following table traces the variables through the execution of the program.
      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


{| 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.


= Videos =
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.
|}

Latest revision as of 15:12, 22 October 2020

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:

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
INPUT variable
variable = expression (assignment)
OUTPUT variable
Decision statements
IF boolean expression THEN
Statement(s)
ELSE (optional)
Statement(s)
END IF
Indefinite Loop statements
WHILE Boolean expression
Statement(s)
END WHILE
Definite Loop statements
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[4:] = “DTPD” (take the last 4 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?

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

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:

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?

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

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]?

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)

Solution:

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

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.

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.