College Preparatory Computer Science Curriculum for Hich Schools. Outline of Exercises. Introduction and Philosophy. This collection of exercises intends to serve two basic purposes. The first one is to show that important ideas that are at the foundation of computer science can be introduces to student audiences at all different levels and with the use of a number of different hardware and software configurations (including just a simple calculator). The second purpose is to plant a seed. From this seed we hope to grow a large collection of exercises as well as tutorials and other study materials that would be developed by the researchers in the different areas. These materials would be designed for use in all different classroom settings - lectures, class manipulative experiments, closed computer laboratories, pencil and paper homework problems, and as a capstone, open ended long term programming projects. The connecting theme behind all these exercises is to stimulate thinking and facilitate experimentation - so that students not only hear about the different concepts, but always have the opportunity to experience them, to use them, to understand the applications and the implications. Another aim is to show the students the rich variety of the uses of computers as enabling tools - tools that give us the power to see or do things we could not see or do before. All along, we also want to make sure that the student pauses often to consider the social implications of computing, the legal and ethical issues. The students must understand that computers give great power to those that use them, but as is always the case with power, there is a great potential for misuse (whether out of negligence, ignorance, or malice). The proposed course is a two semester sequence where the student may receive a half year grade for completing just the first semester. We believe, that a student taking only one semester of college preparatory course in computer science should come away understanding the basic principles that are the building blocks of all computers and computer applications. The following list encompasses these principles: 1. Basic hardware components (CPU, memory, I/O devices, networks) Basic software components (operating system role, file system, program) 2. Representation of data in a computer (numeric, characters, graphic) Implications of limited representations (precision, ease of access, errors) 3. The algorithmic process and the notion of program. The basic building blocks of all algorithms: assignments/expressions, loops and repetitions, decisions 4. Basic problem solving strategies: Modularity, dividing a problem into less complex subproblems, the divide and conquer strategy, use of tools in computing 5. Analysis of programs for correctness and efficiency: Debugging and testing, correct representation of the algorithm Numerical accuracy Time complexity Space/ resource requirements 6. Knowledge and experience with at least two applications where the computer is tangibly useful (database management system, spreadsheet, computer graphics, publishing, ...) 7. Discussion of the social impact and ethical issues in computing. Student should walk away feeling comfortable with using a computer as an enabling tool in daily tasks, as well as having some understanding of what makes the computer so powerful (and at the same time so vulnerable). The exercises in this first collection are intentionally simple. They show that sutdents can learn a great deal about computer science regardless of the type of equipment or software available. They are also designed to stimulate thinking, discussion, and individul personal exploration of the different topics - as a preparation for the more formal study of the topic. They are the foundation on which we will build further. Suggested Exercises for College Preparatory Computer Science Curriculum for Hich Schools. This collection is part of the work of the Pre-College Committee of the Education Board of the ACM. This committee has been working for several years on developing a national college preparatory high school curriculum in computer science. The committee is proposing a one year course, modeled after other high school science courses. The objective of the course is to give students a good understanding of the basic problems facing computer scientists, the fundamental concepts that every computer scientist must understand, and to give students sufficient experience in using computers as problem solving tools. The committee started its work at the ACM Computer Science Conference in Louisville in 1989. It continued its work at NECC '89 in Boston, ACM CSC '90 in Washington, D.C., and at NECC '90 in Nashville. After suveying the current state of the computer science education in the high schools and assessing the needs, it prepared the first draft of the proposed curriculum in the winter 1990-1991. This draft was presented at ACM CSC '91 in San Antonio, and will be presented again at NECC '91 in Phoenix. A full day workshop preceeding NECC'91, sponsored by this committee will provide an opportunity for open public discussion of the different aspects of the proposed curriculum and to give all participants a chance to hear about other experiences with teaching computer science in high schools. One part of the workshop will focus on presenting different activities students can engage in, that would allow them to explore the fundamental concepts of computer science in many different settings. There is a great diversity in the hardware and software that is available in different school districts across the country. Therefore it is important that any national curriculum will give teachers the opportunity to present the ideas regardless of the available equipment and software. The same ideas can be presented using typical computer applications, or by programming in a higher level language, or using only a simple calculator. We want to outline just a few activities for each topic that will demonstrate the feasibility of this approach. We would also like to argue, that even the classes that are heavily geared towards programming may benefit from introducing the concepts through manipulative materials or participatory games. The author would like to thank the many people without whose support this work would have not been possible. First of all, thanks to all members of the Pre- College Committee Task Force on High School Curriculum: Charles Bruen, J. Philip East, Darlene Grantham, Susan Merritt, Chuck Rice, Gerry Segal, Carol Wolf, and coordinator, Lesley Klein. Their earlier work, discussions with them, and their encouragement, has been invaluable in making this collection. Next, thanks are due to my colleagues at College of Computer Science at Northeastern University - Cindy Brown, Harriet Fell, John Gauch, and Richard Rasala for years of discussions about how to better teach the introductory course, for the joint course preparations, for working out of ideas. Thanks are long overdue to Jonathan Gross and Walter Brainerd, who, long time ago (1972), wrote the book that showed me that yes, teaching computer science concepts can be FUNdamentally enjoyable, - and to the students in the course on BASIC at Columbia University in the summers of 1972 and 1973 - who proved that it can be done. Thanks to the student who in her final exam book at the end of a four page detailed explanation of how to compute area under the curve using three different methods added a short comment: 'This is all I know, I am just an English major.' Last, but not least, thanks to my family, Ron, Gisele, Joe, and Elenka, for giving me time, space, and encouragement for this work. Exercise Formats and Presentations. In order to really understand a concept and to be able to apply the new principles in a creative way to new situations, students must experience the concept in a number of different ways. Traditional lecture is one of them - probably the least effective, at least when the concept is completely new. Studies about learning indicate that the best method for learning new concept is to combine several approaches. The first one is being able to manipulate objects that demonstrate the concept and experiment with them. This is the motivation for some of the proposed exercises: binary card game, traffic simulation game, writing directions to a friend's house, manipulating squares with numbers to explore sorting algorithms. Next is a visual component. We would like to make it possible for students to see animations of various solutions as a graphical display on a computer. This is not always possible. However, students should be able to make graphs and charts representing different results, display the program results in a meaningful way. They can also study programs that have been written by others - be it in Pascal, or a demo for a database program. Another component is a closed lab. This means that the students have a limited time (usually one or two class periods) to accomplish a predetermined series of experiments. The objectives of these labs have to be well documented. Students may receive ahead of the time a description of the objectives and the methodology that will be used. They may follow up by writing a lab report and summarizing their findings. There are suggestions for the classroom presentation of the topic - preferably a presentation using the discovery method of delivery should be combined with a discussion of the different aspect of the problem, and also of the related social and ethical issues. We feel that all along students should be required to report some of their findings, result of some of their studies or some of their readings in a written form. It is very important to give the students an opportunity to practice different styles of writing - essays, technical report, summary of findings, design document, user's documentation, etc. If possible, they should also be required to make oral presentations that would parallel or complement the written reports. Finally, to truly understand the complexity of computer software design, the students should complete at least one open ended project - where they have to go through a planning stage, the design, some verification of the design, programming, debugging, documentation, and at the end the presentation of the completed project. The scope and topic of the project depends heavily on the available equipment (hardware, software), the hours available to students to use the equipment, and the availability of help/tutoring when the teacher is not available. In general, we will design for each topic an overview of the main issues, and suggest exercises for manipulation of the concept, visual or other representation, homework paper and pencil exercises, simple computer exercises suitable for closed lab, closed lab outlines, suggestions for discussions and for essays, and suggestions for projects. Introduction to Computers. Overview of the Topic. Students learn about the components of a computer and the method for storing information in the computer. The analogy between 'CPU - memory - I/O system' and 'written assignments (input, program) - student's work (CPU performing operations) - notebook/folder where they are stored (memory, file system)' allows one to explore several aspect of computers. Written assignments represent the input, but they also represent a program the student is supposed to execute. Note, that as the student grows more sophisticated, the instructions he/she receives become less and less detailed. While in the early grades students may get a quite detailed description of what is expected in a complete essay or research paper, later on aonly a brief explanation is needed. Similarly, once the student learns how to multiply two large numbers, it is assumed that the student will know how to perform the operation whenever needed. Similarly, the computer reads in the program that it is supposed to execute. In some cases the program is written with a great level of detail (machine language, assembly language, or even Pascal), but later on the program assumes many simpler operations are already known to the computer. For example the applications that handle databases, spreadsheets, graphics, word processors, etc. On the other hand, many operations that are performed frequently are 'burned into the computer's brains' - or in technical terms implemented in hardware. Multiplication is one of such operations, various conversions from numerical to character representation of numbers is another. Some computers contain hardware instructions that sort a number of items into ascending order, many have instructions that computer the physical memory location of an item in a matrix, given the row and column indices. Student performs the operations that have been assigned. The result of these operations is recorded on a paper that is then stored in some notebook or a folder. Student may consult several other notebooks, textbooks, or folders while working out a problem. Student is also using some of the knowledge previously stored in his/her brain. Obviously the written record of all this corresponds to the computer memory. It contains data, instructions, partial results of computations, etc. Some of the data is important and should be kept for a while, other information may be discarded when no longer needed - in analogy to deleting files. Data may be copied, cross-referenced, organized in piles, folders, labeled, etc. At this point the teacher can explain the hardware components of the computer in as great a detail as seems appropriate. Student may learn about the design of the chips, manufacturing, yields. Students should get some introduction to the history of computing as well as an explanation of the different computer generations, the increase in speed of computers, the decrease in size. Exercises. 1. (Of course) learn how to log on, how to create a file, modify it, delete it, print it. Learn the basic functions of a word processor. Try to think what is all the information the computer has to keep track of to be able to accomplish these tasks. have one student 'imitate' the computer while the other is giving the 'instructions'. 2. Select one of the features of the word processor (find string, automatic line breaks, page breaks, right alignment, ...) and try to explain how is it done. You may not yet get very precise answers - the objective is to start students thinking about the algorithmic process, to learn to express their ideas in clear unambiguous terms. 3. Find three uses of computers in the world around you. Discuss their impact on today's world. Select one of them and write a short essay comparing how the world functioned before this new invention with the way things are done today. What are the benefits? What are the problems the 'computer solution' created? What do you think can be done to solve these problems? Of course, use the word processor to type your essay. 4. Use the more complex features of the word processor to format a document, such as resume, restaurant menu, announcement of a club meeting, an advertisement. 5. Open up the computer case and look at the various components - find the CPU chip, the memory, the connections to the keyboard, to the disk drive, to other external units. Representation of Information in a Computer. Overview of the Topic. Students learn about the representation of data in a computer. Binary numbers, the ASCII code. They will also explore the representation of negative numbers, rules of the binary arithmetic, as well as representation of real numbers. This gives them a background for exploring the actual circuits that implement addition, gives them a feel for the complexity of multiplication compared with addition. Learning about the representation of real numbers allows them to study the accuracy of various computer generated results. One can talk about the largest integer, the smallest (negative) integer, the number of significant digits in a real number, the range of the exponents, Later on the students may compare the accuracy of two different sums of the same collection of data - one added in the increasing order, the other one in decreasing order. For data that spans several orders of magnitude, the first one will be much more accurate. When talking about encoding letters, one should point out the difference between the upper and lower case letters. Students can think about methods one can use to make the text comparison ignore the case. What about blank spaces, commas, periods and other delimiters. Exercises. 1. Octal Odometer: Suppose a car's odometer was representing the milage in octal system. The mileage wold then change from 1777 to 2000. Do a number of adding exercises to figure out what is the mileage going to be after we have gone x miles from the current reading of y miles. Now, buy a new car with only 3 miles on the odometer, but drive it backwards (assuming that the odometer turns backwards as you do it). Go back 2 miles, then one more, then 3 more, etc. What you get is the eight's complement representation of the negative numbers. Try now to go forward, see what will happen. Repeat the game with a binary odometer. 2. Binary Card Number Guess: A magician has six cards, card number i contains all numbers in the range 1 to 63 for which the i-th digit in the binary representation is 1. The magician asks a person to pick a number in the given range, and return to the magician all cards that contain that number. The magician then 'guesses' the number by adding the appropriate powers of two (which appear as the first number on each card). For example, if the magician receives cards with 1, 4, and 8 as the first numbers, it means the secret number was equal to 1 + 4 + 8 = 13. 3. On different calculators, and on a computer try to figure out what is the 'MAXINT', i.e. the largest integer the machine can represent. What happens when you try to use larger number, or to divide by zero. How many bits are being used by that number. What is the smallest negative number? 4. Try to find out about the representation of real numbers in your calculator. What happens when you computer (1/9)*9. In most cases you will not get 1 as a result. Think of what has happened. Try it for different fractions. (1/5)*5 should always work better. Why? an you think of an analogy with the decimal system? 5. Advanced students may want to approximate trigonometric functions using infinite series. By adding the smaller terms first we can achieve accuracy that surpasses the ability of the calculator, by writing down the digits we already are certain about, and leaving only the remaining fraction for the computer to work with. You can use this technique to compute factorials way beyond the largest integer the calculator can represent. 6. File Security. Think what happens when we try to 'erase' file from a computer. Typically, all that is needed is to delete the directory entry for this file and make the space it was using available for other files in the future. What if that file contained sensitive information? Would you have to do more? It is very easy today to gain access to many computers, especially those connected to one of the national networks. What can you do to safeguard sensitive data? - Encrypt them - so every letter is scrambled when it is stored, and unscrambled back when it is read. People who study cryptography work hard on finding encryption algorithms that are easy to compute, but very difficult to break. Computer Predictions - Use of a Spreadsheet. Overview of the Topic. One of the major uses of computers today is in making predictions for the future based on the data that represents recent history. Computers allow us to consider many more factors when making the predictions, they allow us to try several different formulas for making the predictions and evaluate their accuracy. Commercially available spreadsheet programs can be used for economic forecasting, for demographic projections, for evaluating marketing strategies, etc. Prediction and forecasting is also called deterministic simulation. The computer simulates what may happen in the future based on some fixed historical data and a formula that generates the new 'picture' from the historical data. Often the suitability of the formulas can be tested by trying to 'predict' events that already happened and evaluating how accurate the predictions were. In other cases there is a clear scientific formula that determines the future outcome. An example of this is the pollution exercise below. One of the things worth pointing out is that once the data is stored in the computer it can be dispalye in a number of different ways - as charts, tables, but also as a dymnamically changing visual image. This gives the user a great power to convey ideas and to detect pattern in the data that is perceivable from just tabulated numerical values. Later on we will talk about non-deterministic simulations. In these situations the events may or may not happen - with certain degree of probability, but otherwise the issues regargding the display of data and the power it gives us are the same. Exercises. 1. Deterministic Simulation of Pollution: Crystal Lake is fed by two streams with a given average daily water flow providing X galons of water per day. Water is taken from the lake by city of Mudville at a rate of Y galons per day. Returned sewage of Z galons per day contains z% of sludge. Factory at the other side uses M galons per day, returns N galons with n% of sludge per day. Outflow from the river at the lower end takes out T galons of water per day. The lake will die when it becomes Q% sludge. (Currently it is P% sludge.) What are the prospects for the next 10 years, when will it die, what happens if the city, or the factory reduce the degree of pollution?... Students can do these predictions using a simple calculator, using spreadsheet, or by programming simple programs in one of the procedural languages. The results can be tabulated and printed in numerical form or displayed as charts. (Parapharased from Gross, Brainerd: FUNdamental Programming Concepts, Harper & Row, 1972.) 2. Prepare a budget for next five years for a small oragnization or a club. For each expenditure estimate the need for the increase, estimate the increases in different types of revenue. Very the parameters to come up with three budgets - the lean one, the realistic one and the optimistic scenario. Justify the choices you have made, and make sure you have shown that they are supported by the projected data. 3. Get recent census data and use them to make a number of predictions. Find out what was the rate of growth or decline in a certain category over the past ten years, and use that information to predict what will happen in the future. If the outcome is undesirable, think of a way the trend can be changed. Then make new predictions based on the assumption that your solution is workable. 4. Take a poll in several classes of the number of younger sibblings, older sibblings, and only children. Use this data to predict the rate of change in the school population over the next few years. (Other data may enter into the consideration - who had moved within the last three years, students in private or parochial schools, magnet schools, etc.) 5. Try to minimize the 'real dollars' spent on a new car by considering different loan options, down payments, projected rate of inflation, length of the loan, interest rates. 6. Managing inventory: A factory produced three different products, with given number of different parts that go into each product, length of time needed to produce the parts, the product - match this with the potential demand. ... This can become a very complex problem, so choose the constraints and objectives carefully. Record Keeping Using Database Management Systems. Overview of the Topic. Students learn about the difficulties the computer encounters when trying to keep track of a large amount of interrelated records of information. Two systems that they are the most familiar with are the library catalog system, and the system used to assign students to courses, instructors to courses, grades to students, etc. Both of these are excellent examples of a reasonably complex database system. They can be used to illustrate the difficulty of cross- referencing data, making changes, finding the right information, and deleting some entries. When talking about retrieving data from a database management system the instructor should introduce boolean algebra to represent the different querries we send to the system. Illustrating the various boolean expressions on these concrete examples makes them more realistic and gives the student a motivation for learning it. The teacher should point out that some querries are processed much faster, if the boolean expression representing the desired information is written in a different form. Exercises. 1. Give the students index cards of different colors. Each color will represent one file. Then ask them to create a database management system that represents all teachers in a (fictitious) school, all students, all courses, all room numbers. Teacher entry should have teacher's name, home room number, and a list all courses (course numbers only) the teacher is teaching. Student entry should have student's name and a list of all the courses (course numbers only) student is taking. Course entry should list the course name, the course number, number of credits, course level, the teacher (name only), the time, the room number, and a 'pointer' to the student course list. Student course list contains the course number, and a list of students in the course (names only), and a grade assigned to each student. Room list contains for each time slot, the course number of the course that meets in that time. Each file is assigned to a pair of students. The group is now asked to perform typical operations on this 'hand managed' database: add new student into a course, let student drop a course, find all instructors of a given student, print student's schedule, or teacher's schedule. Later on we can add more complex querries. 2. Use boolean expressions to describe the querries requested in the first exercise. Invent other querries, and express them in terms of boolean expressions. Investigate how diffisult it is to process the querries, depending on the sequence in which the various subexpressions are evaluated. 3. Repeat the same exercise for a library catalog: authors, titles, publishers, book numbers, list of borrowers (for the whole library, as well as those that have currently taken out a given title), list of those waiting for the book, etc. 4. Work with a commercially available database system - implement one of these tow examples (or a new one). Perform the same operations, possibly measuring the time it takes to get the response. 5. Have a discussion about the need for regulations regarding the management of databases. Explore how the use of Social Security Number allows for identification of the same person in a number of databases - a potential for a serious abuse. Why is it important to keep some information private. (Examples: privacy of medical records, legal proceedings, ...) Note: The Privacy Act of 1974 prohibits the creation of new databases where the SSN is the primary identifier. A person cannot be required to give his/her SSN in order to get a drivers licence and to receive anumber of other services. The only place where this may be legally required is in the situations where earnings or other monetary transactions have to be reported to the IRS. Algorithmic Process. Overview of the topic. The objective is to introduce the students to the notion of algorithm. At first we want them to understand that algorithm is basically a very accurate description of some process - so accurate that the reader of the algorithm can perform the procedure without difficulties or confusion. The four main attributes of a correct algorithm are: A: There is a unique, well defined starting place. B: The instructions at each point are clearly stated. C: When there are several alternatives one can choose from for the next step, there is a clear rule that allows us to choose exactly one alternative. D: Some steps, or sequences of steps may be repeated, but the algorithm will stop after a finite number of steps. An example of an incorrect algorithm is the instructions on a bottle of shampoo. Wet your hair, apply shampoo, lather, rinse, repeat. For one thing, it is not clear what steps to repeat. Also, it does not indicate when to stop. The exercises allow the teacher to introduce the notion of algorithm without using the computer at all, or as a preparation tfor the first programming exercises, or as an introduction to a course geared more towards the use of computer applications. Once the students understand the need for expressing the algorithm in precise term, they are ready to learn about the basic building blocks of an algorithm: asignments, loops, and decisions. Again we stress the fact that these notions are not only related to procedural language programming, but are at the heart of building all applications that use computers. Exercises: 1. Ask students to guess a number between 1 and 1000. Let them count how many guesses did they have to make. Now ask them to describe their strategy. Look for inaccuracies in the descriptions. Explain, how the computer can be taught how to play the game. 2. Ask the students to tell you what was the largest number out of ten numbers you say. (Note: It actually is quite confusing to be saying ten numbers, counting how many did you give out already, and remembering which one was the largest.) When you say the ten numbers, the first question you ask is: Did I really give you ten numbers. (Most of the time the students just trust you, and noone counts how many there were.) Now ask them to do it againg, counting how many number did you say. Then ask them to describe the process. Write it on the blackboard in precise English. Explain the notion of loop, decision, arithmeic assignment. 3. Describe the algorithm for computing the average of a set of numbers; for finding the mean. 4. Describe the algorithm for generating (printing) all Fibonacci numbers that are smaller than 1000. (Note: Here the notion of while statement comes in.) 5. Describe the algorithm for finding all prime numbers smaller than 1000. (Note: Here you can start the discussion about comparing different algorithms, and increasing the efficiency. You do not need to check whether a number is divisible by any number larger than 100.) 6. The billing office has a list of all customers, and their current balance. Describe an algorithm that would send a refund check to every customer with a positive balance, and send a bill to all other customers, displaying the current balance. What is wrong with this algorithm? (Well, customers with balance zero would be billed for $0.00. This has actually happened in real life - the customer has gotten several notices, and the computer was finally satisfied when it received a check for zero dollars and zero cents. I think, in that case, the computer had kept a balance of negative zero, rather than just plain zero - which of course are all the same to the human beings.) 7. Write an algorithm that will compute how old are you, given this year (91) and the year of your birth (77). How good is this algorithm? Can you use it to tell you how old will you be in 1997? How about how old will you be in the year 2001? This is a major problem facing many businesses today. A lot of code written in COBOL allows for only two digit field to record the year. None of the old programs have been designed with the millenium change comming up. They have been used for years, and it is not easy to find all places where the year field is used in calculations. More Complex Algorithms. Overview of the topic. The objective is to let the students compare several similar algorithms. They should begin to understand, that some algorithms get to be quite complex, they can start learning that one can divide the problem into smaller subtasks that are solved dependently. They should also begin to appreciate how one can try to save the resources that the algorithm needs to complete the task. (Resources being time, some physical space, or any other physical resources.) Another discovery the students are ready to make is the fact that some tasks which look very easy to us may be quite difficult to translate into simple steps that the computer can understand. Exercises. 1. (Note: This is something that is quite simple to do for humans, because they can scan concurrently several letters in a row. It also would be easy for a computer that can compare two arbitrarily large strings in unit time.) Describe an algorithm that will find the first occurrence of a substring in a given string of characters. You are only allowed to look at one letter at a time. You can write down any information you gather along the way. Use a strip of text with a mask that allows you to look at only one of the letters to illustrate the idea to students. 2. Enhance the substring search so that it finds all occurrences of a substring in a given string. Watch out for the cases like looking for 'ana' in 'Antananarive' (which happens to be the capital of Madagascar.) 3. Describe thre different ways to get from your home to school (or any other route): the shortest 'code', the shortest 'execution time' (fastest to drive), and the 'least resources needed' (shortest mileage). For example, to get from Newton Centre to Northeastern University you have three options: A: The shortest code. Take Langley Road to Rte 9 East, continue for 6 miles, Northeastern will be on your right. B: The shortest execution time. (The fastest way.) Take Centre Street North to Massachusetts Turnpike (be careful not to miss the entrance.) Exit at Prudential, follow the signs to Prudential, until you come to the city street. You are now on Huntington Avenue, facing West. Bear left, to make sure you don't take a road that forks off to the right. Go throuh the underpass under Massachusetts Avenue. Northeastern will be on your left one block after the next traffic light. C: The least resources needed. (The shortest distance.) Take Beacon Street through Brookline, into Boston. After you have gone through Kenmore Square, turn right onto the Fenway. Keep left after getting onto the overpass. Go through three lights, following the park on your left. At the fourth light turn right onto Hemenway Street, go three blocks, turn left onto Forsyth Street, at the next light turn left onto Huntington Avenue. Northeastern is on your right. You can now talk about the different ways of evaluating algorithms - time complexity, space requirements, source code complexity. In today's computers people are not tooo worried about the length of the source code, except when the algorithm is implemented in hardware and the space is limited. This is a typical situation in embedded systems, especially those involved in on-board flight control of all kinds. 4. At this point you may start introducing some sorting algorithms. Let the students invent their own method using a strip of paper with sixteen slots, and fifteen numbered paper chits. once the chits are placed into the first fifteen slots, they may only be moved into an empty slot. Try to devise a method that takes the shortest number of moves. See how the method works on different arrangements of numbers. 5. A much harder variation is to put all numbers face down, and be allowed to only turn over two at a time, exchange or move them, and then place them again face down. This actually simulates much more closely what the computer does. You can now count how many times did you turn a number over (number of comparisons), as well as the number of moves as before. natomy of a Computer. Overview of the Topic. We feel that it is very difficult to become comfortable with use of a 'machine' if one has no understanding what makes it work. Yes, millions of people drive a car, and have no idea what is under the hood, but even the basic driver's education course teaches students the most fundamental auto mechanics. There are three different levels at which the students should understand the functioning of a computer. On the hardware level, they should understand tha the computer is built out of small single function circuits - each of them performing a simple function - all connected together to form CPU, memory and different I/O devices. At the software level, they should understand that the 'native' language of the computer is the machine language, and that there is a number of programs that translate instructions written in some higher level into this language. These programs (typically the operating system, together with some utility programs, and application programs) also provide services to the users - mainly in the form of management of resources, or by providing templates for solving typical subproblems. The third level that is becomming increasingly important can be characterize as network level. Students should understand how is it possible for several computers to share the workload, to cooperate in solving a problem, in general to communicate with each other. Again, as for all other topics, the coverage of the topic can range from purely conceptual all the way to detailed technical exposition. Exercises. 1. There is a number of simple inexpensive kits available (for example in Radio Shack) for building simple adders, LCD controllers, and other simple control circuits. Similar ones can be built from scratch. Students should experiment with them and actually build something. 2. Explain the functioning of a simple two or three digit adder built out of AND, OR gates and an inverter. 3. Use a simple (simulated) machine language to explain the working of a CPU: instruction decoding, operand fetch, instruction execution, result store. Ask students to write simple programs in this language. This could be a paper and pencil exercise, or the students can use a simulator on a real computer. Other alternative is to actually build simple calculator from a kit, and program it. Or the students may write programs for programmable calculators - which often operate on a level equivalent to the machine level. Compare the language of a good scientific calculator to assembly language. 4. Investigate the purpose and the working of assembler, compiler - try to take a simple program and hand-translate it into assembly language - then into machine language. Make small change in the origrinal program and trace these changes down to the machine level. 5. Talk about the scheduling the time during which certain tasks should be performed. this is an analogy to the process scheduling for the CPU. Investigate the complexity of the problem and the possible solutions by playing the 'scheduling game': One person manages the scheduling. Others are given index cards with arrival time, units of time needed to accomplish a task, and indication, whether or not the time can be split into several segments. The scheduler announces the current time, collects information from all newly arrived tasks, and decides which task gets serviced next. (Only one task can be serviced at any given time; an index card may contain data for several consecutive tasks, with wait periods between the completion of one task and arrival/initiation of the next task.) Another person meanwhile collects data on the waiting times - for each task, and for the entire system. The second time through, the scheduler is given a specific strategy to follow. Different strategies can then be compared. Also, you may give the scheduler a specific goal: minimize system idle time, minimize the average response time, ...) 6. Talk about the memory management. Investigate the complexity of the problem by playing a 'resouce manager game': One person is the resource manager. Others are given index cards with the folowing information: time when a resource is to be requested, the length of time for which the resource is needed, resource type, resource amount, whether the resource can be preempted or not. Again, additional person keeps the statistics on various waiting times, as well as on the use of the resources. Note, that now the system may end up in a deadlock. Again, the manager should be replaced after some time, the manager may be requested to follow a given strategy, or to aim for certaing goals. :wq Nondeterministic Simulations. Overview of the Topic. Nondeterministic simulations are used to predict outcomes and simulate situations which cannot be described by exact formulas, but to some extent depend on 'chance' or probability that some event occurs. Typical introductory exercises that are used to describe 'the laws of chance' include tossing coins, playing cards, rolling dice, selecting a marble of a given color from a bag of marbles. In order to represent 'random' events in a computer we need a special tool (a program) called the random number generator. It is used to generate a potentially infinite sequence of randomly distributed numbers within a certain range. A simple random number generator is only a few lines of code long. It is important not to stop with presenting only the examples of 'games of chance' here. The students need to understand that a number of very important applications used daily by millions of people are based on non-deterministic simulations. These include weather predictions, stock market predictions, election predictions based on polls, engineering design simlulation tools, use of simulators as training platforms for astronauts, pilots, and other high risk professions, modeling of complex systems before they are put into production. Exercises. 1. Study the basic laws of probability distribution by performing a number of experiments - tossing coins, rolling dice, picking cards from a deck, etc. Compare the mathematical formulas with your experimental results. 2. Write and test a simple random number generator. Now use it in a program that will simulate picking a random card, rolling dice, or tossing a coin. 3. Learn how to use a commercial simulation package. Use it to do demographic projections, predict results of elections, etc. - either using real data or by generating sample random inputs. 4. Suppose environmetal engineers have detected soil contamination in a given area, They want to know how large is the contanminated area. They select a boundary of a size one square mile. Now they collect random samples in different locations. (A random number generator determines where to take these samples.) By comparing the number of clean samples with the contaminated ones they can determine the size of the contaminated area. They can also use such sampling technique to determine the boundaries of the contaminated area. You can write a program that will for a given area inside a unit square generate the locations of random samples, then tabulate the clean vs. contaminated ones, and use this data to determine the extent of contamination. 5. Traffic Light Simulation Game: One person represents the traffic light, according to a set timer rules. One or two people collect data about the cars passing through. Others pick a card with a starting and destination point on it, and try to get through. (Some rules are set about how the time is measured - in comparison with 'car speeds'.) A | | | | ---------+ +---------- B X D ---------+ +---------- | | | | C 7. You can simulate other situations - the most typical are waiting lines. Waiting for a teller in the bank is the most often used setting, but one can think of airport and the planes waiting to take off and land. Artificial Intelligence: Games with Strategies. Overview of the Topic. A large number of computer applications is based on the principles similar to those used for playing games. There is a set of rules that one, two or several players must followThere is an objective each player is trying to achieve. There is a mechanism for determining whic one of the several possible next actions is the best in term of bringing us closer to achieving the objective. The other player is often an adversary - trying to achive the same goal as we are, or trying to thwart our progress. There are several approaches a computer (or human) can take when playing games. The easiest one is to make the first possible move (or any one of the possible moves at random). of course, we may not achieve the objective this way. The other method is to analyze the various possibilities, and decide on the basis of some criteria which move seems the best at the current time. This strategy can either be static in its nature - that means that we decide ahead of the time for all possible choices, which one is the best. This is usually possible for only a few small scale games - those where a 'winning strategy' exists. Some examples of such games are: guess a number, tic-tac-toe, tha game of NIM described below. Another, often emplyed strategy is for the computer to learn from its mistakes. After each game it analyzes the results, and records the 'values' of the moves used in this game (good ones and the bad ones). As the time goes on, the computer starts playing a better game. In very complex game-like programs, the computer often contains a large database of typical game situations and whole sequences of moves that are expected to follow., as well as a large collection of rules for evaluating the next move - combining the 'perfect strategy' technique with the rule based one, and the learning strategy. Exercises. 1. Start with Tic-Tac-Toe. It is quite simple, everybody knows the strategy, and it is very easy to describe. It is interesting in the fact that if both players play the 'perfect' game, nobody ever wins. Think of the way to record the current status, the possible moves, assigning value to moves or positions. A graph whose nodes are the various board configurations, together with directed edges connecting each configuration with all of its possible successors represents the game completely. One can assign weights to these edges, or even remove the completely undesireable ones from the graph. Show the graph that represents the perfect strategy. 2. A simple game of NIM. There is one matchsticks in the first row, two in the second row, and are three matchsticks in the third row. On each move a player is allowed to remove any number (greater than zero) of matchsticks from one of the three rows. Players take turns. The player that removes the last matchstick looses the game. Start by playing the game. Let the students search for the best strategy. They should soon find out theat the player who starts will inevitably loose, unless the opponent does not know how to play. You can now analyze the game. Represent the state of the game by three binary numbers (1 11 111) and start by looking for the positions to avoid (guaranteed loss) versus desirable positions (guaranteed win). For example you do not want to end up with (0 00 100) or (0 10 000), or (1 00 000) before it is your turn. On the other hand, you do want to have (1 00 100) or (0 10 100) or (0 11 100)... when it is your turn. By starting from the end you can climb all the way to the top, marking all desirable positions and eventually discovering the winning strategy. Now the game playing algorithm just selects from all possible moves the one with the highest 'weight'. Point out, that for more complex games, the computer may be given the initial estimates of the weight of different moves, but it will gather the experience and adjust the weights as it plays again and again. 2. Let the students play Master Mind. (One person selects a four digit number - or five digit number for more skilled players, and the other one has to guess the number. After each guess, the first player indicated which digits were guessed correctly and in the correct place, and how many were right digits in the wrong place. So if the secret number is 11253 and the guess is 21212 the reply has to be 0PPR0. P means the digit is in its right place, R means it is a right digit, but in the wrong place, 0 means wrong digit, wrong place.) See if they can describe their strategy. Try to write down the strategy, so others can play by following it. Are there any flaws in the strategy? How are you adjusting the strategy, once you have some concrete information about some of the digits? 3. Another game that allows for a lot of experimentation and is relatively easy to program is 'Connect Four'. There are ... columns of ... slots, and the players alternate in putting their pieces into the slots. The one that first gets four pieces in a row, column, or across any diagonal, wins the game. It is easy to program a dumb game, where the computer makes completely random moves. The first improvement would be to try to prevent the oponent from connecting four. Going beyond this gets to be quite difficult, but would make a very interesting open ended project. Numerical Methods. Overview of the Topic. The emphasis here is on showing the students that the computer based solution to the problem may often be very different from that used when solving the problem by hand. The reason for using a different approach is that while it is difficult to perform a large number of accurate computations by hand, the computer is eminently suitable for such tasks. We focus on quite mathematical problems that use approximation techniques: numerical integration, finding the roots onf an equation by successive approximations, evaluating functions using infinite series expansion. It is important at this point to look again at the accuracy of the results. The cumulative error in large successive summation can grow very large - sometimes even to the magnitude that renders all but two or three digits of the result unusable. The importance of careful analysis of the methods employed, the accuracy of the computer used, the need for detailed understanding of the representation of data in the computer should be emphasized and reiterated. Exercises. 1. Compute area below a curve specified by a function f(x) on an interval from zero to one. (Select several functions that are positive in this interval, and whose integral is easily computed analytically.) Do this using several different methods: * Use graph paper, plot the function, compute the area by counting the rectangles under the curve. Look for the functions where this works well, where it does not work, estimate the error. Use the trapezoidal rule, and repeat the process. * Use the formula from calculus to get the exact value. Compare this with the 'manual' result. Is the error estimate correct? * Use the simulation technique - generate random dots at positions (x,y) where 0