COS 132 Imperative Programming Study Unit 1: Introduction to Algorithms PDF

Department of Computer Science COS 132 - Imperative Programming Study Unit 1: Introduction to Algorithms Copyright ©2025 by Linda Marshall, Inge Odendaal, Mark Botros and Cobus Redelinghuys. All rights reserved. Contents 1.1 Introduction....................................

Department of Computer Science COS 132 - Imperative Programming Study Unit 1: Introduction to Algorithms Copyright ©2025 by Linda Marshall, Inge Odendaal, Mark Botros and Cobus Redelinghuys. All rights reserved. Contents 1.1 Introduction................................. 2 1.2 Algorithmic Thinking........................... 2 1.2.1 Toasted Sandwiches............................. 2 1.2.2 Steps of Algorithmic Thinking....................... 4 1.3 Flowcharts.................................. 4 1.3.1 Flowchart Symbols.............................. 5 1.3.2 Flowchart Structures............................. 6 1.3.3 Drawing flowcharts.............................. 8 1.3.4 Examples................................... 8 1.3.4.1 Collatz Conjecture........................... 8 1.3.4.2 Toasted Sandwiches........................... 10 1.3.5 Alternative Representations......................... 11 1.4 Pre and Post Conditions for Algorithms............... 11 1.5 Brief history of C++............................ 12 1.6 Conclusion.................................. 14 References....................................... 14 1.7 Document Change Log.......................... 14 1 1.1 Introduction This study unit introduces one of the fundamental skills any programmer needs to possess in order to survive in any development environment. This skill allows the programmer to develop a solution to a problem in an abstract manner, which they can then translate into a programming language which is compiled or interpreted to produce executable code. This skill is known as “algorithmic thinking” and the mastery of this skill is crucial for the successful completion of any programming module. 1.2 Algorithmic Thinking Algorithmic thinking will be introduced by first considering an example. The steps in- volved in developing an algorithm will be formalised for the specific example. 1.2.1 Toasted Sandwiches Before delving into the depths of algorithmic thinking, consider the following scenario: The week before going to university to pursue your dreams of obtaining your degree, you decide to throw a fancy sandwich party for you and your friends. You ask each of your friends to design a fancy sandwich, and they will need to explain to you how to create the sandwich. On the day of the party, one of your friends provides you with the following fancy sandwich description: A salami and salmon sandwich with brown bread. Between each layer of salami and salmon, there is lettuce and cucumber. Between the bread slices and the first layer of salmon and salami, there needs to be placed a bed of rocket and basil pesto. In the middle of the sandwich a layer of sun-dried tomato can be found. Overwhelmed by this description, you decide to break it down into smaller parts. You identify the following key points: Brown bread Layers of salami and salmon containing lettuce and cucumber. Between bread and salami and salmon layer, there is rocket and basil pesto. In the middle there are sun-dried tomatoes. From your vast experience of making fancy toasted sandwiches, you know the following: The bread needs to be buttered on both sides before being toasted. The number of layers in the sandwich is different depending on the person’s hunger levels. Basil pesto should only go in the inside of the sandwich. 2  To ensure the structural integrity of the sandwich, you know that the lettuce should be broken into smaller pieces and the cucumber should be cut into smaller pieces. With this knowledge, you decide to derive a set of steps to create the sandwich. 1. Prepare outer bread slices. 2. Ask the “sandwich eater” how many layers they would like. 3. Prepare that number of layers. 4. Add half of the layers to the sandwich. 5. Add the sun-dried tomatoes. 6. Add the rest of the layers to the sandwich. 7. Place the sandwich into the toaster. 8. Close the toaster and wait for it to be sandwich to be ready. This list can be expanded to be more specific: 1. Turn the toaster on. 2. Butter bottom bread slice on the inside. 3. Add basil pesto. 4. Ask the “sandwich eater” how many layers they would like. 5. Prepare that number of layers. 6. Add half of the layers to the sandwich. 7. Add the sun-dried tomatoes. 8. Add the rest of the layers to the sandwich. 9. Butter the inside of the top bread slice. 10. Add basil pesto to the inside top bread slice. 11. Add the top slice of bread to the sandwich. 12. Butter the outside of the top piece of bread. 13. Place the sandwich upside down on the toaster. 14. Butter the outside of the now top bread slice. 15. Close the toaster and wait for it to be sandwich to be ready. What you have just done is the process of applying algorithmic thinking using a set of steps to solve a problem by designing an algorithm. Most everyday tasks can be thought of in an algorithmic manner, like boiling a kettle, driving to work, greeting your friends and much more. 3 1.2.2 Steps of Algorithmic Thinking Algorithmic thinking consists of the following steps: 1. Decomposition: This step consists of breaking the problem down into smaller constituent parts. This allows for “easier” sub-problems to be solved which when combined, solves the original problem. 2. Pattern Recognition: This step consists of identifying similar parts previously defined or from experience. Experience allows you to apply a part of a solution from one problem in an attempt to solve another problem. By recognising patterns and re-using solutions, the speed at which you develop programs as well as the quality of the produced programs will increase. Thus it is important to expose yourself to as many problems as possible. 3. Abstraction: The process of abstraction is to identify the steps that are required to solve the problem. The steps are usually semi-granular high-level descriptions of how you can solve the problem. 4. Algorithm: Formalising the final algorithm is the culmination of all of the previous steps, and consists granularly of defining the rules/steps that need to be applied to solve the problem. Revisiting the toasted sandwich example in Section 1.2.1. We can see that we performed decomposition when we identified the key points of the algorithm to make the fancy sandwich. We applied pattern recognition to enhance the algorithm by looking at common things we do while making sandwiches. Combining decomposition and pattern recognition we created a set of abstracted steps to create the sandwich. Lastly, we expanded the abstracted set of steps to create the final algorithm for creating the sandwich. Although the numerical list we used to define the algorithm worked, we require a more formal and visual way to define the algorithms, for example, a flowchart. 1.3 Flowcharts Flowcharts are a visual representation of an algorithm. Flowcharts allow the algorithm de- signer to showcase all the basic building blocks (formally referred to as flowchart symbols) to be used for creating an algorithm. Another way to think of the visual representation of an algorithm is to see it as an abstraction of the algorithm. The idea behind visualisation is that external memory, in the form of a picture, is used to convey a difficult concept. This also has the benefit of technical and non-technical people understanding how the code will work without needing an in-depth understanding of the intricacies of program- ming. Once the abstracted algorithm is visually created, the process of converting to a programming language to be compiled or interpreted into concrete executable code, is simplified. 4 1.3.1 Flowchart Symbols Table 1 contains the basic flow chart symbols as defined in the ISO 5807 1 standard. When these symbols are combined any algorithm can be effectively modelled, and then translated into a high-level programming language to again be translated into executable code. Symbol Description Illustration Type Start The start symbol indicates where the initial/entry point is for the algo- rithm represented by the flowchart. Start Start or End The end symbol indicates the termi- nation point of an algorithm repre- sented by the flowchart. End Process The process symbol is used to indi- cate operations or manipulation of data is performed at that stage of Process the algorithm. Predefined The predefined process indicates a Process pre-defined sub-process that forms part of the algorithm but the steps are not explicitly shown or for- Predefined Process malised yet. Decision The decision symbol indicates a symbol choice/decision that is performed which can result in two or more al- ternative “paths” through the flow chart. The alternative options are A Decision B labelled. 1 Note you do not need to purchase this document. It was linked for interest’s sake. 5  Symbol Description Illustration Type Input/ This symbol is used to model input Output from external sources, like user in- symbol put, or output to external sources, like terminal output. Input/Output Flow The flow arrow symbol is used to in- arrows dicate the direction of the informa- tion flow. Table 1: Basic symbols used in flowcharts The symbols listed in Table 1 are a subset of possible flowchart symbols that are important for COS 132. There are other symbols that are less used, such as to indicate displays, stored data, databases, and many more. By combining these symbols in a highly structured manner, flowchart structures can be defined. 1.3.2 Flowchart Structures As discussed flow charts are used to model an algorithm in an abstracted visual manner. Thus, flowcharts allow us to illustrate the following high-level patterns: Linear Execution: A set of instruction that is executed in order one after the other to form a sequential structure. This is illustrated in Figure 1. Decision Making: A point in the algorithm where two or more alternative options can be selected which form a selection structure. This is illustrated in Figure 2. Repetition: A set of instructions which is repeated until some termination con- dition is satisfied to form repetition structures. This allows an algorithm to easily perform repetitive tasks. This is illustrated in Figure 3. 6  Start Start Start Process 1 Repeat? No No Process B Decision Yes Process 2 Yes Process 7 Process A Process 3 Finish End End Figure 1: A simple sequen- Figure 3: A simple repeti- tial flowchart with three pro- Figure 2: A decision flowchart with a Start, tion (loop) flowchart with a cess steps. Decision, two branches, and an End node. process inside the loop. 1.3.3 Drawing flowcharts As flowcharts are used by both technical and non technical people, some drawing conven- tions have been proposed: Ensure that flowcharts are easy to read and easy to follow. Flowcharts should fit on a single page. The sizes of shapes should remain consistent. Ensure that the styling of the flow arrows remains consistent. The font and styling of the text used in the flowchart remain consistent. Ensure that as far as possible, the flow arrows do not cross. Ensure that flow arrows consist of straight lines. Ensure symbols are appropriately spaced out. There are more conventions for flowcharts, often which is specified either by the company you work for or the programming language you develop for. Ensure that you are aware of the conventions and that you follow them. 1.3.4 Examples Two examples of flowcharts are shown below. The purpose of these two examples are to showcase how complicated problems can be reduced to algorithms that can be easily understood with the aid of flowcharts. 1.3.4.1 Collatz Conjecture The Collatz Conjecture, also known as the 3n + 1 problem, is a simple yet deceiving mathematical problem, as it remains unsolved till today. The Collatz Conjecture uses Equation 1 to create a sequence of numbers as defined by Equation 2:  3n + 1 if n is odd (1) f (n) = n  if n is even 2 where n ∈ Z+. ( n i=0 (2) CCi = f (CCi−1 ) otherwise where CCi is the ith number in the Collatz Conjecture number sequence. 8 The Collatz Conjecture states that the sequence defined by Equation 2 for any positive integer value, will eventually reach the value of 1. So for example, if we take CC5 we obtain the number sequence: 5, 16, 8, 4, 2, 1. If we take CC6 we obtain the number sequence: 6, 3, 10, 5, 16, 8, 4, 2, 1. CC5 and CC6 are trivial cases and these sequences can become extremely large. CC27 for example takes 111 steps before reaching a value of 1. Now using the process of algorithmic thinking we can produce an algorithm for the Collatz Conjecture and illustrate it as a flowchart – refer to Figure 4. Figure 4: Flowchart for the printing the Collatz Conjecture. In Figure 4 we used an input block to obtain the initial value of the sequence, and an output block to print out the current value of n. We used two conditional blocks to determine if the value of n == 1 and if n is odd. The flowchart in Figure 4 contains examples of all three structures discussed in Section 1.3.2. 9 1.3.4.2 Toasted Sandwiches The abstract algorithm laid out for the fancy toasted sandwich discussed in Section 1.2.1 can be expressed by the flowchart in Figure 5. The flowchart contains a series of predefined processes which encapsulates a series of smaller steps which can be modelled as their own algorithm. Figure 5: Flowchart of the abstract algorithm to make a fancy toasted sandwich 10 1.3.5 Alternative Representations Although flowcharts are a brilliant way to represent an algorithm, they can occupy a large amount of space, especially for small programs where a text-based solution will work better. This is where the idea of pseudo-code came from. Pseudo-code is where you express the algorithm in natural language sentences which again can easily be translated to executable code. Pseudo-code is less restrictive than flowcharts as the main requirement is each sentence should convey a single concept and that the pseudo-code should be easy to understand. There are multiple online resources you can find that delve into pseudo-code in more depth. Using the flowchart depicted in Figure 4, the Collatz Conjecture can be expressed with the following pseudo-code: Algorithm 1 Pseudo-code for the Collatz Conjecture algorithm depicted in Figure 4 Require: n ∈ Z+ while not n == 1 do print out n if if n is odd then n = 3n + 1 else n = n2 end if end while 1.4 Pre and Post Conditions for Algorithms Now that we know how to create algorithms, and how to visualise and express the algo- rithms, we need to formalise what can be assumed before the algorithm starts and what can be assumed after the algorithm has been completed. This is where the pre-conditions and post-conditions for algorithms comes in. Pre-conditions are all the conditions that can be assumed to be true before the algorithm starts. Post-conditions are all the conditions that can be assumed to be true after the algorithm terminates. Relating these back to the examples listed in Section 1.2.1 the pre-conditions for the Collatz Conjecture is that the input number is a positive integer and the post-conditions is that the sequence of numbers that were printed, terminated with the value of 1. For the toasted sandwich example, the pre-conditions are that all the ingredients exist and are available, that you possess the cooking skills to make a toasted sandwich and you have the friends to suggest the fancy sandwich. The post-conditions are that you get a tasty fancy sandwich and a messy kitchen. Now we have our algorithms designed, we can translate them into a high-level program- ming language. In our case, we will be translating the algorithms into the C++ program- ming language. 11 1.5 Brief history of C++ C++ is a strongly typed compiled language. This means that the data types of variables are determined at compile time. C++ initialy fell into the procedural paradigm of pro- gramming languages, but has been expanded to also fall into the object-orientated and generic programming paradigms. C++ was developed and implemented in 1979 by Bjarne Stroustrup (Figure 6), with the first version of C++ being released in 1983. C++ comes from a long line of programming languages, as illustrated by Figure 7, and is the direct successor of the C programming language. The name for C++ is actually derived from adding the increment operator (++) to C making C++. Figure 6: Bjarne Strousup [Obtained from the Columbia Engineering faculty page on 08/02/2025.] In 1985, The C++ Programming Language textbook was published, with the 4th edition of the book being published in 2013. The different versions of C++, are referred to as stan- dards, where the capabilities and functionality of different features of C++ is described. Interestingly, the implementation of some features differed depending on the author of the compiler. One such example is how random numbers are generated. Currently, the latest standard of C++ is C++232 which was released in October of 2024. For COS132 you will be using C++98. One of the C++ compilers is the GCC compiler, which started supporting C++ in 1987. The current version of GCC is 14.2 which was released on the 1st of August 20243 2 Again these standards are linked for curiosity’s sake. Please do not purchase these standards! 3 This information was verified on the 08/02/2025. 12 Figure 7: A brief history of high level programming languages from 1956 to 2004 [Obtained from Research Gate on 08/02/2025.] 13 1.6 Conclusion As stated at the start of this study unit, algorithmic thinking is at the core of programming and problem-solving. The ability to apply the steps outlined in this study unit to create an algorithm which is expressed in a flow chart can be the difference between a novice programmer and an excellent programmer. In this series of study units and by extension in COS 132, you will be expected to be able to do the following to demonstrate your algorithmic thinking capabilities: Design an algorithm for a given scenario and produce a flowchart for the algorithm. Convert a flowchart to and from a segment of C++ code. Convert a flowchart to and from a segment of pseudo code. Apply the steps provided in a flowchart when debugging code. Identify errors in flowcharts which resulted in a faulty algorithm being produced. Trace a path through a flowchart and determine the conditions needed to reach a certain state or given a certain precondition, trace the path through a flowchart. 1.7 Document Change Log Date Change 9 Feb 2025 Initial preparation and presentation of the document. 14