[PDF] Computer Science Field Guide Programming sometimes referred to as

View - Download Computer Science Field Guide

Previous PDF

Next PDF

Computer Science

Field Guide

v2.8.1

Print Edition

Sponsors

Funding for this guide has been generously provided by these sponsors Produced by the CS Education Research Group, University of Canterbury, New

Zealand, and by many others.

The Computer Science Field Guide uses a Creative Commons (CC BY-NC-SA 4.0) license

2 of 521Computer Science Field Guide - v2.8.1

1. Introduction

Watch the video online at https://www.youtube.com/embed/v5yeq5u2RMI?rel=0

1.1. What's the big picture?

Why is it that people have a love-hate relationship wit computers? Why are some people so fanatical about particular types of computers, while others have been so angry at digital devices that they have been physically violent with them? A nd what does this have to do with computer science? And what is computer science anyway? I'm glad you asked! Put simply, computer science is abou tools and techniques for designing and building applications that are very fast, have great interfaces, are reliable, secure, helpful --- even fun. A lot of people confuse computer science with programming. It h as been said that "computer science is no more about programming than astr onomy is about telescopes" ( Mike Fellows). Programming is the tool that computer scientists use to bring great ideas to life, but just knowing how to give programmed instruc tions to a computer isn't enough to create software that delights and empowers people. For example, computers can perform billions of operations e very second, and yet people often complain that they are too slow. Humans can perceive delays of about one tenth of a second, and if your program takes longer than that to respond it will be regarded as sluggish, jerky or frustrating. You've got well under a seco nd to delight the user! If you are searching millions of items of data, or displaying millions of pi xels (megapixels), you can't afford to do things the wrong way, and you can't just tell your users that they should buy a faster computer ... they'll probably just buy someone else's faster software instead! Here's some advice from Fred Wilson, who has invested in many high pro le tech companies: First and foremost, we believe that speed is more than a feature. Speed is the most important feature. If your application is slow, peo ple won't use it. I see this more with mainstream users than I do with power users. I think that power user sometimes have a bit of sympathetic eye to the challenges of buil ding really fast web apps, and maybe they're willing to live with it, but when I l ook at my wife and kids, they're my

1. Introduction

www.cs eldguide.org.nz/en/3 of 521 mainstream view of the world. If something is slow, they're just gone. ... speed is more than a feature. It's a requirement. -- Fred Wilson (Source) A key theme in computer science is working out how to make things run fast, especially if you want to be able to sell your software to the l arge market of people using old-generation smartphones, or run it in a data centre where you pay by the minute for computing time. You can't just tell your customers to buy a faster de vice --- you need to deliver ef cient software.

1.2. Beyond speed

Computer science isn't just about speed. Try using the following two calculators to make a simple calculation. They both have the same functionality (they can do the same calculations), but which is nicer to use? Why? (This book has many interactives like this. If the calculat ors don't work properly, you may need to use a more recent browser. The interactive material in this book works in most recent browsers; Google Chrome is a particularly safe bet.) Use the interactive online at http://www.cseldguide.org.nz/en/interactives/awful-calculator/index.h tml The second calculator above is slower, and that can be fr ustrating. But it has a fancier interface --- buttons expand when you point to them to highlight what you're doing. Does this make it easier to use? Did you have problems b ecause the "C" and "=" keys are so close? How interfaces work is a core part of computer science. The aesthetics --- images and layout --- are important, but what's much more cru cial is the psychology of how people interact. For example, suppose the "OK" and "Cancel" button in dialogue boxes were occasionally reversed. You would always need to che ck carefully before clicking on one of them, instead of using the instinctive moves you've made countless times before. There are some very simple principles based on how people think and behave that you can take advantage of to design systems that people love. Making software that can scale up is another important theme. I magine you've built a web interface and have attracted thousands of customers.

Everything goes well until your site

goes viral overnight, and you suddenly have millions of customers. If the system becomes bogged down, people will become frustrated waiting for a respons e, and tomorrow you will have no customers --- they'll all have mo ved on to someone else's system. But if your

1. Introduction

4 of 521Computer Science Field Guide - v2.8.1

programs are designed so they can scale up to work w ith such large amounts of data your main problem will be dealing with offers to buy your com pany! Some of these problems can be solved by buying more equip ment, but that can be an expensive and wasteful option (not just for cost, but because of th impact on the environment, including the wasted power used to do the proce ssing inef ciently). With mobile computing it's even more important to keep things lean and ef cient --- heavy duty programs chew up valuable battery life, and proce ssing and memory must be used sparingly as these affect the size, weight and even heat d issipation of devices. If your system is successful and becomes really popular, pretty soon people will be trying to hack into it to steal valuable customer data or pas swords. How can you design systems so that you know they are secure from such attacks and your customers can trust you with their personal information or business transactions?

All these questions and more are addressed by the

eld of computer science. The purpose of this guide is to introduce you to those ideas so that you have a better idea of whether this eld is for you. It is aimed at high-school level, and is inten ded to bring you to the point where you have a good overview of the eld, and are well prepared for further in-depth study to become an expert.

We've broken computer science up into a whole lot

of topics that you'll often nd in curricula around the world, such as algorithms, human-computer inte raction, compression, cryptography, computer graphics, and arti cial intelligence. The reality is that all these topics interact, so be on the lookout for the connections. This guide isn't a list of facts for you to memorise, or to copy and paste into projects! It is mainly a guide to things you can do --- experiences that will en gage you with the topics. In fact, we won't go through all the topics in great detail , but will give you references to websites and books that explain things thoroughly. The idea of this guide is to give you enough background to understand the topics, and to d something meaningful with them.

1.3. Programming

And what about programming? You can get through this wh ole guide without doing any programming, although we'll suggest exercises. Ultima tely, however, all the concepts here are re ected in programs that people write. If you want to learn programming there are many excellent courses available. It takes time and practice, and is well worth doing in parallel with working through the topics in this guide. There are a number of free online systems and books that you can use to teach yourself prog ramming. A list of options for all ages learning to program is available at www.code.org, where there is also a popular video of some well-known high- iers in computing that is good to show classes.

1. Introduction

www.cs eldguide.org.nz/en/5 of 521 Programming is just one of the skills you'll need to be a computer scientist. In this book you'll be exercising many other skills --- maths, psycholo gy, and communication are important ones.

1.4. How to use this guide

This guide is intended to support a variety of curricula, a nd teacher guides will become available for using it in different contexts. For stu dents, we've designed most chapters so that they can stand alone; the few that build on previous chapters explain at the outset what preparation you need (the most useful general preparation is the chapter on data representation, because everything on a computer is st ored using binary numbers and so they have an important role in many areas of compu ter science.) Each chapter begins with a section about the "big picture" --- wh the topic is useful for understanding and designing computer systems, and what can be achieved using the main ideas in the chapter. You'll then be introduced to key ideas and applications of the topic through examples, and wherever possible we'll have interactive activities that enable you to work with the ideas rst hand. Sometimes these will be simpli ed versions of the full sized problems that computer scientists need to deal with -- our inte ntion is for you to actually interact with the ideas, not just read about them. Make sure you give them a go! We nish each chapter by talking about the "whole story," giving hints about parts of the topic that we omitted because we didn't want to make the chapter too overwhelming. There will be pointers for further reading, but be warned th at some of it might be quite deep, and require advanced math or programming skills If you are doing this for formal study, you'll end up having to do some sort of assessment. The curriculum guides provide ideas for projects and activit ies that could be used for this.

1.5. About this guide

This guide is free for you to copy, share and even modify. It is currently available online, and as a downloadable PDF le (although it's much better viewed in the other formats because you can watch the videos and use the interactive acti vities). The source material (all raw text, images, videos and interactive programs) is available through the "Contribute on GitHub" link. This guide is licenced under a Creative Commons Attribution-NonCommercial-ShareAlike licence , which means that you are welcome to take copies and mod ify them. If you do make improvements, we ask that you share those, and acknowledge this guide by linking

1. Introduction

6 of 521Computer Science Field Guide - v2.8.1

back to our web site. You can give away the guide (or an derivatives), and you can use it for teaching, but you're not allowed to sell it direct ly for pro t. Production of the guide was partially funded by a generous grant from Google Inc., and supported by the University of Canterbury. Of course , we welcome donations to support further work on the guide.

1.6. Further reading

Each chapter gives suggestions for further reading for that particular topic. There are also plenty of general books and websites about computer science that you might want to read to keep your view of the topic broad.

Books that we particularly recommend include:

Algorithmics, by David Harel

Computational fairy tales, by Jeremy Kubica

Algorithmic adventures: from knowledge to magic, by Ju rag Hromkovic

The Turing Omnibus, by A.K. Dewdney

Wikipedia has a fairly extensive entry on computer science.

The AQA Computing A2 book(s), by Sylvia Lang

eld and Kevin Bond, give a more detailed account of many of these topics. There are also some excellent general web sites about Com puter Science, many of which we've referenced in other chapters: Computer Science For Fun --- a very readable collection of short articles a bout practical applications of topics in computer science Babbage's bag is an excellent collection of technical articles on many topics in computing. CS Bytes has up-to-date articles about applications of computer scienc e. Thriving in our digital world has some excellent information and interactive material on topics from computer science. The Virginia tech online interactive modules for teaching com puter science cover a range of relevant topics. CS animated has interactive activities on computer science.

CS for All

1. Introduction

www.cs eldguide.org.nz/en/7 of 521

2. Algorithms

Watch the video online at https://www.youtube.com/embed/FOwCCvHEfY0

2.1. What's the big picture?

Every computer device you have ever used,

from your school computers to your calculator, has been using algorithms to tell it how to do whatever i was doing. Algorithms are a very important topic in Computer Science because they help softwa re developers create ef cient and error free programs. The most importa nt thing to remember about algorithms is that there can be many different algorithms for the same p roblem, but some are much better than others! Use the interactive online at http://www.cseldguide.org.nz/en/interactives/sorting-algorithm-compa rison/ index.html Computers are incredibly fast at manipulating, moving and loo king through data. However the amount of data computers use is often so large that it doesn't matter how fast the computer is, it will take it far too long to examine every single piece of data (companies like Google, Facebook and Twitter routinely proc ess billions of things per day, and in some cases, per minute!) This is where algorithms come in. If a comp uter is given a better algorithm to process the data then it doesn't matter how mu ch information it has to look through, it will still be able to do it in a reasonable amou nt of time. If you have read through the Introduction chapter y ou may remember that the speed of an application on a computer makes a big difference to a h uman using it. If an application you create is too slow, people will get frustrated with it a nd won't use it. It doesn't matter if your software is amazing, if it takes too long they will simpl give up and try something else!

2.1.1. Algorithms, Programs and Informal Instructions

At this stage you might be thinking that algorithms and computer programs kind of sound like the same thing, but they are actually two very di stinct concepts. They are each different ways of describing how to do something, but at different levels of precision:

2. Algorithms

8 of 521Computer Science Field Guide - v2.8.1

Often you can get away with describing a process just using so me sort of informal instructions using natural language; for example, an informal instr uction in a non computing context might be "please get me a glass of water". A human can understand what this means and can gure out how to accomplish this task by thinking, but a computer would have no idea how to do this! Use the interactive online at http://www.cseldguide.org.nz/en/interactives/high-score-boxes /index.html An example in a computational context might be if you wanted to nd a high score in a table of scores: go through each score keeping track of the largest so far. Informal instructions like this aren't precise; there's no way that a computer could follow those instructions exactly, but a human could probably get the general idea of what you mean if they know what you're trying to achieve. Thi sort of description is only useful for quickly giving another human the general idea of what you mean, and even then there's a risk that they won't properly understand it. In contrast, an algorithm is a step by step process that describes how to solve a problem and/or complete a task, which will always give the correct result. For our previous non- computing example, the algorithm might be 1) Go to the kitchen. 2)

Pick up a glass. 3) Turn

on the tap. 4) Put the glass under the running water and remove it once it is almost full. 5) Turn off the tap. 6) Take the glass back to the pe rson who gave the instruction. A human could follow these instructions easily, but it's still using ge neral English language rather than a strict list of computer instructions.

Algorithms are often expressed using a loosely de

ned format called pseudo-code, which matches a programming language fairly closely, but leaves out details that could easily be added later by a programmer. Pseudocode doesn't have strict rules about the sorts of commands you can use, but it's halfway between an informal in struction and a speci c computer program. With the high score problem, the algorithm might be written in p seudo-code like this: if the table is empty display that there is no high score, and quit otherwise, note the first score in the table for each of the other scores in the table, if that score is larger than the one noted, replace the noted one with the current score display the currently noted score

2. Algorithms

www.cs eldguide.org.nz/en/9 of 521 Algorithms are more precise than informal instructions and do not require any insight to follow; they are still not precise enough for a computer to follow in the form they are written, but are precise enough for a human to know exactly w hat you mean, so they can then work out how to implement your algorithm, either doing it t hemselves, or writing a computer program to do it. The other important thi ng with this level of precision is that we can often make a good estimate of how fast it will be. For the high score problem above, if the score table gets twice as big, the algorithm will take about twice as long. If the table could be very big (perhaps we're tracking millions o games and serving up the high score many times each second), that might already be enough to tell u that we need a better algorithm to track high scores regardless of which la nguage it's going to be programmed in; or if the table only ever has 10 scores in it, then we kno that the program is only going to do a few dozen operations, and is bound to be r eally fast even on a slow computer. The most precise way of giving a set of instructions is in the foquotesdbs_dbs24.pdfusesText_30

[PDF] Et avant la France - mediaeduscoleducationfr - Ministère de l

[PDF] La vérité vous affranchira » (affranchir - L 'Appel aux jeunes

[PDF] Les homophones ES EST ET CE2

[PDF] aide-mémoire pour l 'élaboration d 'un plan de communication

[PDF] Guide autorisation A5 V20 KB - GD MAROC

[PDF] Quelques conseils pratiques - SNES Créteil

[PDF] Les établissements de santé

[PDF] Table des matières Les relations diplomatiques et - Larcier

[PDF] loi n° 010 sur règles de création des établissements publics - Caisse

[PDF] Le système de santé tunisien _Etat des lieux et défis - UNFPA Tunisie

[PDF] Réglementation applicable aux établissement recevant du public

[PDF] Définition des établissements sanitaires ou sociaux et - Edimark

[PDF] ouverture etablissement secondaire par une personne - CCI Marne

[PDF] Lexique des établissements et services médico-sociaux - Onisep

[PDF] Spatialisation des bioclimats, de l 'aridité et des étages de végétation