Topic 4: Computational thinking, problem-solving and programming

Objectives:

4.1 General Principles

Thinking Procedureally
4.1.1Identify the procedure appropriate to solving a problem.
4.1.2Evaluate whether the order in which activities are undertaken will result in the required outcome.
4.1.3Explain the role of sub-procedures in solving a problem.
Thinking Logically
4.1.4Identify when decision-making is required in a specified situation.
4.1.5Identify the decisions required for the solution to a specified problem.
4.1.6Identify the condition associated with a given decision in a specified problem.
4.1.7Explain the relationship between the decisions and conditions of a system.
4.1.8Deduce logical rules for real-world situations.
Thinking Ahead
4.1.9Identify the inputs and outputs required in a solution.
4.1.10Identify pre-planning in a suggested problem and solution.
4.1.11Explain the need for pre-conditions when executing an algorithm.
4.1.12Outline the pre- and post-conditions to a specified problem.
4.1.13Identify exceptions that need to be considered in a specified problem solution.
Thinking Concurrently
4.1.14Identify the parts of a solution that could be implemented concurrently.
4.1.15Describe how concurrent processing can be used to solve a problem.
4.1.16Evaluate the decision to use concurrent processing in solving a problem.
Thinking Abstractly
4.1.17Identify examples of abstraction.
4.1.18Explain why abstraction is required in the derivation of computational solutions for a specified situation.
4.1.19Construct an abstraction from a specified situation.
4.1.20Distinguish between a real-world entity and its abstraction.

4.2 Connecting Computational Thinking and Program Design

4.2.1Describe the characteristics of standard algorithms on linear arrays.
4.2.2Outline the standard operations of collections.
A collection is a group or items forming a conceptual unit. In some of the examples we have seen, a Word object containing a (word, definition) can be stored in a variety of collections.
    There are four main categories of collections:
  • Linear: Arrays, lists, stacks, queues
  • Hierarchial: Heaps, trees, hashes
  • Connected: Graphs
  • Unsorted: sets, maps

The standard operations (or methods acting on) collections include

  • Adding an object to the collection
  • Removing an object from the collection
  • Being able to search for an item in the collection
  • Being able to traverse through a collection

Ref: BWagner.org
    Collection Resources

  • Collection Handout and StudyWords.java an java applet

  • StudyWords.java as an application: Collections Lab Version 2

  • Practice test question (Collections) The Half Marathon Problem
    Solution file The Half Marathon Problem

      Extension Activity - Programming the half-marathon problem
      1. Dowload the Marathon.java program
      2. Download the data Participants.dat
      3. The Marathon class contains the following ArrayLists: 
        	
   ArrayList PARTICIPANTS = new ArrayList(); // max number of participlants = 450 
 	 			                     // contains the name of the team they are on 
   ArrayList TIMES = new ArrayList();    // The finish time of each runner 
   ArrayList TNAMES = new ArrayList();     // if each team had the min of 150 participants 
   ArrayList TEAM  = new ArrayList();    // links team members together
      4. Review the main program 
         public static void main(String[] args) {
     Marathon	half = new Marathon(); 
     try {
          half.loadParticipants("Participants.dat"); 
          half.findTeams(); 
          half.linkTeams(); 
          half.printTeams(); 
         }
     catch (Exception e)
        {
          System.err.format("Exception occurred in main program");
          e.printStackTrace();
        }
}
      5. Review method loadParticipants() and see how the input file is processed and the ArrayLists PARTICIPANTS and TIMES are initialized.
      6. Review the method findTeams() and see how the list of PARTICIPANTS is traversed to create a list of TNAMES which contains a list of all of the unique team names.
      7. Assignment 1:
        Complete method linkTeams() to make a "link" between each member of a team. See the handout from last week for more details. The list of teammates is circular, so if you start at any index you should be able to find all of the members who are on the same teams.
      8. Assignment 2:
        Complete method printTeams() to print the name of each time on a line with the indexes of all other participants who are on the same team.
      9. Challenge Assignment 1:
        Modify the printTeams() method to also print the teams competitive time: teams are comprised of 3-5 team members, the sum of the lowest three scores on a team becomes the teams time.
      10. Challenge Assignment 2:
        Have your program identify the teams that came in first, second, and third, along with each teams time.

      Sample Marathon.java solution.

4.2.3Discuss an algorithm to solve a specific problem.
    Examples:
  • Practice test question Collections The half-Marathon problem requires algorithms.
4.2.4Analyse an algorithm presented as a flow chart.
4.2.5Analyse an algorithm presented as pseudocode.
4.2.6Construct pseudocode to represent an algorithm.
    CW/HW Problem:
  • Create an algorithm, represented using pseudo-code that will read in a series of numbers, one per line and then display the following statistics:
    • The minimim and maximum values
    • The mean (average, second quartile)
    • The first quartile (q1) and the third quartile(q3)
    • The inter-quartile range (iqr = q3 - q1)
    • The median
    • The total number of items that were read
    • A list of all of the outliers, if any
      Define a data item to be an outliner if either:
      • the value is less than [q1 - (1.5)(iqr)]
      • the value is greater than [q3 + (1.5)(iqr)]
  • The format of the output is up to you
Trace
Tables		Using Trace Tables for program segments and pseudocode
4.2.7Suggest suitable algorithms to solve a specific problem.
4.2.8Deduce the efficiency of an algorithm in the context of its use.
4.2.9Determine the number of times a step in an algorithm will be performed for given input data.

4.3 Introduction to Programming

Nature of Programming Languages
4.3.1State the fundamental operations of a computer.
4.3.2Distinguish between fundamental and compound operations of a computer.
4.3.3Explain the essential features of a computer language.
4.3.4Explain the need for higher level languages.
4.3.5Outline the need for a translation process from a higher level language to machine executable code.
Use of Programming Languages
4.3.6Define the terms: variable, constant, operator, object.
4.3.7Define the operators =, ., <, <=, >, >=, mod, div.
4.3.8Analyse the use of variables, constants and operators in algorithms.
4.3.9Construct algorithms using loops, branching.
4.3.10Describe the characteristics and applications of a collection.
4.3.11Construct algorithms using the access methods of a collection.
4.3.12Discuss the need for sub-programmes and collections within programmed solutions.
4.3.13Construct algorithms using predefined sub-programmes, one-dimensional arrays and/or collections.