Welcome!
This is the seventh week of this semester. We learnt algorithm, pseudocode and flowchart this week. Even though we have learnt these in last academic year, there are still new stuff and something we have forgotten. We tried to solve more difficult problem in less steps during the classes in this week. We also did a lot of interesting activities. It is an exciting week.
Define Algorithm
We first reviewed knowledge associated with algorithm. Algorithm is a set of step-by-step clear instructions to solve a problem. Algorithms can perform calculation, data processing and automated reasoning tasks. Even though is seems that algorithms only involves in science, actually it is everywhere in people’s daily life.
Properties and Expressions of Algorithm
Algorithms have several properties which are finiteness, definiteness, input, out and effectiveness. To be finiteness means that an algorithm can be expressed within a finite number of steps and it could terminate after particular number of steps. Algorithm is definiteness because an algorithm should be written in well-defined formal language which does not lead to misunderstanding of the steps. Algorithm must have inputs which means that quantities must be entered before the algorithm begins. Out means that an algorithm should have an output associated with inputs when an algorithm ends. To be an effective method, all instructions in an algorithm should be exactly be done by processor in principle and it could be accomplished in a finite amount of time and space.
There are several expressions of algorithm: natural language, flowchart, pseudocode, and programming language. Natural language is simple English which is somehow verbose and ambiguous. We all know that language might cause misunderstandings in daily life.
Flow chart is a type of diagram as a representative of algorithm which illustrates a solution model of a given problem. It shows the steps in various types of boxes which are connected with arrows. Pseudocode and flowchart can be transformed from each other. Pseudocode, informal language, is generic artificial language intended for human to read rather than computers. Programming language is a formal language intended for computers to understand and process it which comprises a set of instructions used to produce various kinds of output, like Python, Java and C++.
Decision Making Process
There is a process for decision making in algorithms. It could be concluded in four steps which are identification, development, selection, and implementation. Identification means to identify what problem is, to understand the problem, and to formulate the problem. Development means to discover different alternatives (methods) to solve the problem. Selection is to choose the best alternative in order to solve the problem. The last step, implementation, is executing the selected solution to find that whether the selected solution could actually solve the problem. If there is any problem, it should go back to redo the previous step. If there is no solution for the problem, people should go back to the first step, identification, to identify the problem again. If the most effective way could not be found which means that there might be some mistakes in development, development should be done again. If program does not work by utilizing the selected solution, selection should be done again.
Proper Pseudocode Notations and Conventions
Pseudocode involves a series of English-like statement. Pseudocode is like a planning tool. It is often written before designing the flow of a program. There are some common pseudocode notations. “Input” refers that users will enter something. It might be numbers, letters, or even sentences. “Output” means that an output will appear by operating the algorithm. The output could be printed or shown on the screen. “While” is used when there is a loop in algorithms which means that several instructions would be repeated for several times until it satisfies the condition. “While” is often written with the condition of the loop. “For” means a counting loop. “If-then-else” is used when there is a choice needed to make. “Repeat-Until” infers a loop with a condition at the end of the loop.
Division (quotient) vs. Modulus (remainder )
| Dividend | Divisor | Quotient | Remainder | |
| 16 Div 3 == 5 | 16 | 3 | 5 | 1 |
| 16 Mod 3 == 1 | 16 | 3 | 5 | 1 |
Example of “For”
Let N=0
For each person in room
Set N=N+1
There are also conventions for pseudocode. Variables name should all be capitals, for example a user inputs a number, the variable could be “NUM A”. A significant rule is how “=” is used. “A = 7” means assigning 7 to A. “A == 7” indicates A equals to 7. We also learnt how to write numbers in sequence which is much more convenient when dealing with a sequence of numbers.NS=[3,5,2,36,14] (Array) NS[0] = 3; NS[3]= 36 ; NS[2]= 2. It should be written in “dot notation” (Java, C++ and so on). Pseudocode keywords should be written in lower case, for instance “loop”, “while”. Method name is mixed, like “getRecord”. Output could mean that data is printed by a printer or is shown on the screen. If “//” appears, behind “//” is the explanation or comment for the pseudocode written before “//”.
We have done some activities to practice pseudocode. These are activities we have done. We strictly followed the decision making process: identification, development, selection, and implementation.
We also tried to translate assembly language to pseudocode. Last week, we had an assignment which is to use LMC to do multiplication. This week we used the assembly language we wrote in LMC and translated to pseudocode. Here is the picture of the activities.
Steps of Creating a Trace Table
Trace table is the new stuff we learnt in this semester. Trace table is a tactic to test algorithms to make sure there is no logical errors. It can also be used to record outcomes of an algorithm. I used the following pseudocode as an example to show how to create a trace table.
First, write down all variables in the first line.
| COUNT | N | SUM | N div 2 | N mod COUNT == 0 | SUM = N | Output |
Second, filling the initial value provided in the question in the second line of the chart
| COUNT | N | SUM | N div 2 | N mod COUNT == 0 | SUM = N | Output |
| 6 | 0 | 3 |
Third, input all loop values (in this case, it is variable — COUNT) vertically in the “COUNT” column.
| COUNT | N | SUM | N div 2 | N mod COUNT == 0 | SUM = N | Output |
| 6 | 0 | 3 | ||||
| 1 | ||||||
| 2 | ||||||
| 3 |
Fourth, follow the each pseudocode statement and fill the respective results in the cell for every change.
| COUNT | N | SUM | N div 2 | N mod COUNT == 0 | SUM = N | Output |
| 6 | 0 | 3 | ||||
| 1 | 1 | T | ||||
| 2 | 3 | T | ||||
| 3 | 6 | T | ||||
| T |
Finally, write down the final output.
| COUNT | N | SUM | N div 2 | N mod COUNT == 0 | SUM = N | Output |
| 6 | 0 | 3 | ||||
| 1 | 1 | T | ||||
| 2 | 3 | T | ||||
| 3 | 6 | T | ||||
| T | Perfect |
As shown above, it is a step-by-step example of how to establish a trace table. Trace table is truly imperative for checking whether there are logical errors or not, but also it could help people to find the result of a pseudocode.
First, we followed ,our teacher, Mr. Pete’s steps to make the trace table of his pseudocode for example 6. Here is the picture of Mr. Pete’s pseudocode for example 6 and my trace table. We also practiced how to make a trace table during the class. We checked each other’s pseudocode’s logic by utilizing trace table which is extremely useful. Here is the picture of our on-class activities.
Battleships game activity
Battleships game activity is a really interesting activity. There are 26 ships on the paper and each ship represents a different alphabet letter and a code. We did these activities in pairs. One student held a sheet of 1A, while another student held a sheet of 1B. First, every student circle a ship on the their own paper. Each student should try to locate their group mate’s ship. StudentA says the guessing letter of studentB’s ship. If it is right, the studentB should tell studentA that it is right. If it is wrong, studentB should tell the code of the letter studentA is guessing. StudentA writes down the code. We did two activities to discover the algorithms of searching an array of numbers. Afraid of not understanding the rule of the game, I copied a more clear instruction written by Mr. Pete.
In first activity, we are given a paper of ships with random codes. In the second activity, we are given a paper of ships with codes from smallest to the largest. The rule changes a little. After circling the letter, each student should tell the partner the code of the circling letter. If the letter is wrong, the partner could tell the student the code of guessing letter. So students are more easier to find the right answer because they have a relative small range of the letter. In the last activity of battleship game, students did not tell the code of circling letter to each other, but they will say whether the code is larger or smaller.
This activity highlights the algorithms of searching an array of numbers. With letters arranged according to numbers, it is much easier for students to guess and it saves time. In the last activity, student could most use five times to guess the right letter. However, in the first activity, it depends on fate. Mark and I were a pair. But I did not win even one game when playing with random numbers. Even once, I did not find the right letter, until I guessed 26 times (so sad). BUT it is an extremely fun activity we have done during last week.
In the first activity, it applies linear search algorithm. As you can see, the linear search algorithm is nothing else then looping though all element of the array and compare the element with the number we are looking for. If we find the number we set before and then we break out of the loop. In the second activity, it applies binary search algorithm. It finds the position of a target value within a sorted array. Binary search compares the target value to the middle number of the array. If they are not equal, the half in which the target cannot lie is eliminated, and then the binary search is repeated on the remaining half. The process does not stop until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. Compared with linear search algorithm, binary search algorithm is more convenient in most of the time.
Activities
Besides those activities described above, we also did some other activities in LMC. We made LMC code for the following questions in the video.
Due to limited time, we did flowchart practice after class. It is known to us all that flowchart and pseudocode could be convert from each other. So we wrote flowcharts for example 3-7, according to the pseudocode.
Conclusion
In conclusion, we learnt a lot and did a lot and did many activities. It was a fulfilling week. We reviewed algorithms, pseudocode and flowchart. We created more difficult pseudocode this semester. We also learnt how to create trace table to check for logical errors. By playing battleship game activity, we learnt the significance of linear search algorithm and binary search algorithm. I am looking forward to the computer science class in the next week!
站点标题 