Unit 3–Intro to Programming

Chapter 1: Intro to Programming

Big Questions:

  • Why do we need algorithms?
  • How is designing an algorithm to solve a problem different from other kinds of problem solving?
  • How do you design a solution for a problem so that it is programmable?
  • What does it mean to be a “creative” programmer?
  • How do programmers collaborate?

Lesson 2: The Need for Algorithms

Objectives: Students will be able to………

  • Trace programs written in the “Human Machine Language”
  • Develop an algorithm to find the smallest playing card in a row of cards
  • Express an algorithm in the “Human Machine Language”
  • Identify the properties of sequencing, selection and iteration the “Human Machine Language”
  • Evaluate the correctness of algorithms expressed in the “Human Machine Language”

DO NOW:

  1. Go to www.code.org & log in
  2. Intro
    1. Recall the lessons learned about language. Yesterday’s activity focused on the inherent difficulties of trying to express precise processes with written language. We arrived at a few conclusions…
      1. We need to agree on a set of commands and exactly what terms mean
      2. The fewer commands we have, the easier it is to agree
      3. We want to know what are the “primitive” operations – the most basic set of operations that will allow us to do most of the tasks that the situation requires.
      • Language is important, but there is another part to programming. Once you have a well defined language you need to apply it to problems.
      • The art (and science) of using a well-defined language of primitive operations to solve problems is the art and science of algorithms.
      • The CS Principles definition of algorithm is: Algorithms are precise sequences of instructions for processes that can be executed by a computer and are implemented using programming languages.
      • One way to think of the study of algorithms is that it is the study of processes — how can you use a small set of instructions to clearly and correctly define process that will solve some problem?
      • Yesterday, with the LEGO blocks, you also attempted to design an algorithm. Any time you are trying to write a precise set of instructions for a process to solve a problem you are designing an algorithm.
      • Today we’re going to get into algorithms a little more deeply.
  3. Activity 1: It goes without saying that in a Computer Science class we are concerned with not just any processes, but computational processes – ones that can be executed by a computer – which have specific sets of constraints. We often get started thinking about algorithms and computational processes by trying to rigorously act them out ourselves as a sort of “Human Machine”. When acting as a machine, we can keep the limitations of a computer in mind. In this activity you’re going to pretend that you are a “Human Machine” that operates on playing cards on the table.
    1. Get the Human Machine Minimum Card Algorithm Activity Guide
    2. Get clear on the task, rules, instructions
    3. With a partner act out an algorithm
    4. Write down the steps
    5. As you are working you might ask yourself questions like:
      • “How do you know when to stop?”
      • “Do your instructions state where and how to start?”
      • “Is it clear where to put cards back down after you’ve picked them up?”
    6. You and your partner share with the class.
    7. As we look at these algorithms you came up with, we can see they are not all the same. However, there are common things that you are all making the human machine do and commonalities in some of your instructions. Can we define a language of common Human Machine commands for moving cards around? What are the commands or actions most of these instructions have in common?
    8. What are some commands?
    9. Write them down or group them based on type.
    10. Here are some examples:
      1. SHIFT (hand) – some form of shifting hands one position down the row left or right
      2. MOVE (hand) – some form of moving a hand directly to a particular card based on its position in the list or to the position of one of the other hands.
      3. COMPARE – some way to compare cards and do something based on the result like: “if card in right hand is less than card in left hand then…”
      4. GO TO LINE – some way to jump to an earlier or later line in the program
      5. PICK CARD UP/PUT CARD DOWN – some way to do this that also makes clear where to put a card back down. Typically something like: “Put right hand card down into the right-most open space in the row of cards”
  4. Activity 2: We have just identified a set of primitive commands that we can use to operate on a set of cards. To be very concrete let’s formalize this into a language. Get the Activity Guide – Human Machine Language – Activity Guide
    1. Read the first page. Be sure you understand the instructions and setup.
    2. Get with the partner you had before
    3. You should try to figure out the example programs with a partner, making use of the code reference guide.
    4. One partner reads, the other acts as the human machine.
    5. You should jot notes about what the program does.
    6. Do you understand how the language works?
    7. Let’s take turns describing each one.
    8. Go to the last problem
      1. Did you understand it?
      2. What would be your solution?
    9. This problem we identified with the last example speaks to the art and science of algorithm design and what can make it so interesting. The question is: can we fix the problem without adding more commands to the language? If we can fix a problem without extending the language, that’s a good thing. We can focus our attention on designing algorithms given these constraints. Let’s try to write FindMin using the Human Machine Language…
      1. First, what’s different about the problem setup for the Human Machine Language?
          1. This might be very challenging at first since the problem setup is slightly different
          2. The problem now has different initial assumptions.
            1. All cards are face up
            2. Card positions have numbers
            3. Don’t need to pick up cards or put them down
            4. There is actually no way to move cards at all – only hands
            5. The ending state is well defined – left hand touching the min card.
      2. Now use the Human Machine Language to write the algorithm for finding the min card.
        1. NOTE: You can just write the code, or you can use the cutout strips of the commands and write values into the boxes.
        2. Work with your partner.
      3. Share solutions to Find Min with the Human Machine Language
        1. You and your partner get together with another group to compare solutions.
        2. Each group should test out the other group’s code by acting as the human machine.
        3. During the comparison note any differences in people’s approach.
      4. It’s okay if you can’t quite finish before the period is over. This activity continues in the next lesson anyway.
  5. This is a first experience in evaluating some code.
  6. It’s important to actually try out a solution to identify any potential errors.
  7. It’s also important to see that people’s programs are different
  8. With 5-10 minutes remaining, respond to the following in your Word Online file for this class:
    1. Connect algorithms to programming.
      1. Yesterday we discussed the need for a programming language. Today we came up with our own programming language and used it to implement an algorithm. The CSP definition of algorithm is: “a precise sequence of instructions for processes that can be executed by a computer and are implemented using programming languages.”
      2. Notice two things about algorithms and programming…
        1. Different algorithms can be developed to solve the same problem–Even though you were all trying to solve the same problem (find min) as a class we came up with different methods for doing it. We would say we came up with different algorithms.
        2. Different code can be written to implement the same algorithm–This is sometimes surprising to newcomers. When writing “code” (even with with the human machine language) two people trying to write code to implement the same algorithm may very easily code it differently.
      3. These two facts – Different algorithms can be developed to solve the same problem and different code can be written to implement the same algorithm – embody art of programming and what makes programming so fun, engaging and creative. In programming, just like art, we strive to make beautiful things:
        1. A beautiful algorithm is an elegant and clever idea for how to solve a problem.
        2. A beautiful program is an elegant use of whatever language structures are provided to make the algorithm actually work on a computer.
  9. Foreshadow: tomorrow we’ll try some other algorithms in the human machine language.

Leave a comment

Your email address will not be published. Required fields are marked *