AQA AS and A Level Computer Science AQA AS and A Level Computer The aim of this textbook is About the authors to provide a detailed Pat Heathcoteis a well-known understanding of each topic and successful author of of the new AQA A Level Computer Science textbooks. Science Computer Science She has spent many years as a specification. It is presented in teacher of A Level Computing an accessible and interesting courses with significant way, with many in-text examining experience. She has questions to test students’ also worked as a programmer understanding of the material and systems analyst, and was and their ability to apply it. Managing Director of Payne- Gallway Publishers until 2005. The book is divided into 12 sections, each containing Rob Heathcote has many roughly six chapters. Each years of experience teaching chapter covers material that Computer Science and is can comfortably be taught the author of several popular in one or two lessons. It will textbooks on Computing. He also be a useful reference and is now Managing Director of revision guide for students PG Online, and writes and throughout the A Level course. edits a substantial number of Two short appendices contain the online teaching materials A Level content that could published by the company. be taught in the first year of the course as an extension to related AS topics. Each chapter contains exercises, some new and some from past examination papers, which can be set as homework. Answers to all these are available to teachers only, in a Teachers Supplement which can be ordered from our website www.pgonline.co.uk AQA AS and A Level Computer Science P.M. Heathcote R.S.U. Heathcote Published by PG Online Limited The Old Coach House 35 Main Road Tolpuddle Dorset DT2 7EW United Kingdom [email protected] www.pgonline.co.uk 2016 Acknowledgements We are grateful to the AQA Examination Board for permission to use questions from past papers. The answers in the Teacher’s Supplement are the sole responsibility of the authors and have neither been provided nor approved by the examination board. We would also like to thank the following for permission to reproduce copyright photographs: Screenshots of Arriva Bus App © Arriva PLC Colossus photograph © The National Archives Google Maps ‘StreetView’ © Google 2015 Screenshot from Roboform website © Roboform Alan Turing © By kind permission of the Provost and Fellows, King’s College, Cambridge from Archives Centre, King’s College, Cambridge. AMT/K/7/12 Trans-continental Internet connections © Telegeography Internet registries map © Ripe NCC Other photographic images © Shutterstock Graphics: Rob Heathcote and Roger Stayte Cover picture © ‘South Coast Sailing’ 2014 Oil on canvas 60x60cm Reproduced with the kind permission of Heather Duncan www.heatherduncan.com Design and artwork by OnThree www.on-three.com Typeset by Chapter One (London) Ltd, Ian Kingston First edition 2016, reprinted 2016 A catalogue entry for this book is available from the British Library ISBN: 978-1-910523-07-0 Copyright © P.M.Heathcote and R.S.U.Heathcote 2016 All rights reserved No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means without the prior written permission of the copyright owner. Printed and bound in Great Britain by Lightning Source Inc., Milton Keynes ii Preface The aim of this textbook is to provide detailed coverage of the topics in the new AQA AS and A Level Computer Science specification. The book is divided into twelve sections and within each section, each chapter covers material that can comfortably be taught in one or two lessons. In the first year of this course there will be a strong emphasis on learning to program. You will start by learning the syntax of your chosen programming language – that is, the rules of how to write correct statements that the computer can understand. Then you will code simple programs, building up your skills to the point where you can understand and make additions and amendments to a program consisting of several hundred lines of code. Sections 1 and 2 of this book can be studied in parallel with your practical programming sessions. It will give you practice in the skills you need to master. In the second year of this course the focus will turn to algorithms and data structures, covered in Sections 7 and 8. These are followed by sections on regular languages, the Internet and databases. Object Oriented Programming and functional programming are covered in the final section, which describes basic theoretical concepts in OOP, as well as providing some practical exercises using the functional programming language Haskell. Lists, the fact-based model and ‘Big Data’ are all described and explained. Two short appendices contain A Level content that could be taught in the first year of the course as an extension to related AS topics. The OOP concepts covered may also be helpful in the coursework element of the A Level course. Each chapter contains exercises and questions, some new and some from past examination papers. Answers to all these are available to teachers only in a Teacher’s Supplement which can be ordered from our website www.pgonline.co.uk. Approval message from AQA This textbook has been approved by AQA for use with our qualification. This means that we have checked that it broadly covers the specification and we are satisfied with the overall quality. Full details of our approval process can be found on our website. We approve textbooks because we know how important it is for teachers and students to have the right resources to support their teaching and learning. However, the publisher is ultimately responsible for the editorial control and quality of this book. Please note that when teaching the A Level Computer Science course, you must refer to AQA’s specification as your definitive source of information. While this book has been written to match the specification, it cannot provide complete coverage of every aspect of the course. A wide range of other useful resources can be found on the relevant subject pages of our website: www.aqa.org.uk. iii Contents Section 1 Fundamentals of programming 1 Chapter 1 Programming basics 2 Chapter 2 Selection 8 Chapter 3 Iteration 13 Chapter 4 Arrays 17 Chapter 5 Subroutines 21 Chapter 6 Files and exception handling 29 Section 2 Problem solving and theory of computation 33 Chapter 7 Solving logic problems 34 Chapter 8 Structured programming 39 Chapter 9 Writing and interpreting algorithms 42 Chapter 10 Testing and evaluation 48 Chapter 11 Abstraction and automation 52 Chapter 12 Finite state machines 60 Section 3 Data representation 67 Chapter 13 Number systems 68 Chapter 14 Bits, bytes and binary 72 Chapter 15 Binary arithmetic and the representation of fractions 77 Chapter 16 Bitmapped graphics 83 Chapter 17 Digital representation of sound 88 Chapter 18 Data compression and encryption algorithms 93 iv Section 4 Hardware and software 99 Chapter 19 Hardware and software 100 Chapter 20 Role of an operating system 103 Chapter 21 Programming language classification 106 Chapter 22 Programming language translators 110 Chapter 23 Logic gates 114 Chapter 24 Boolean algebra 118 Section 5 Computer organisation and architecture 125 Chapter 25 Internal computer hardware 126 Chapter 26 The processor 132 Chapter 27 The processor instruction set 138 Chapter 28 Assembly language 142 Chapter 29 Input-output devices 148 Chapter 30 Secondary storage devices 154 Section 6 Communication: technology and consequences 158 Chapter 31 Communication methods 159 Chapter 32 Network topology 164 Chapter 33 Client-server and peer-to-peer 168 Chapter 34 Wireless networking, CSMA and SSID 171 Chapter 35 Communication and privacy 176 Chapter 36 The challenges of the digital age 179 v Section 7 Data structures 187 Chapter 37 Queues 188 Chapter 38 Lists 194 Chapter 39 Stacks 198 Chapter 40 Hash tables and dictionaries 202 Chapter 41 Graphs 207 Chapter 42 Trees 211 Chapter 43 Vectors 217 Section 8 Algorithms 223 Chapter 44 Recursive algorithms 224 Chapter 45 Big-O notation 229 Chapter 46 Searching and sorting 235 Chapter 47 Graph-traversal algorithms 243 Chapter 48 Optimisation algorithms 249 Chapter 49 Limits of computation 254 Section 9 Regular languages 259 Chapter 50 Mealy machines 260 Chapter 51 Sets 265 Chapter 52 Regular expressions 269 Chapter 53 The Turing machine 273 Chapter 54 Backus-Naur Form 278 Chapter 55 Reverse Polish notation 283 vi Section 10 The Internet 287 Chapter 56 Structure of the Internet 288 Chapter 57 Packet switching and routers 292 Chapter 58 Internet security 294 Chapter 59 TCP/IP, standard application layer protocols 300 Chapter 60 IP addresses 307 Chapter 61 Client server model 313 Section 11 Databases and software development 318 Chapter 62 Entity relationship modelling 319 Chapter 63 Relational databases and normalisation 323 Chapter 64 Introduction to SQL 330 Chapter 65 Defining and updating tables using SQL 336 Chapter 66 Systematic approach to problem solving 342 Section 12 OOP and functional programming 346 Chapter 67 Basic concepts of object-oriented programming 347 Chapter 68 Object-oriented design principles 353 Chapter 69 Functional programming 360 Chapter 70 Function application 367 Chapter 71 Lists in functional programming 371 Chapter 72 Big Data 374 References 379 Appendices and Index Appendix A Floating point form 380 Appendix B Adders and D-type flip-flops 387 Index 391 vii CHAPTER 1 – PROGRAMMING BASICS String-handling functions Programming languages have a number of built-in string-handling methods or functions. Some of the common ones in a typical language are: Returns the length of a string len(string) Returns a portion of inclusive of the characters at string.substring(index1,index2) string each index position Determines if occurs in a string. Returns index (the string.find(str) str position of the first character in the string) if found, and -1 otherwise. In our pseudocode we will assume that string(1) is the first element of the string, though in Python, for example, the first element is string(0) Returns the integer value of a character (97 in this example) ord("a") Returns the character represented by an integer chr(97) ( a in this example) " " Q3: What will be output by the following lines of code? x = "Come into the garden, Maud" y = len(x) z = x.find("Maud") OUTPUT "x= ",x OUTPUT "y= ",y 1-1 OUTPUT "z= ",z To concatenate or join two strings, use the + operator. e.g. “Johnny” + “Bates” = “JohnnyBates” String conversion operations converts the character “1” to the integer 1 int("1") converts the integer 123 into a string “123” str(123) converts the string “123.456” to the real number 123.456 float("123.456") converts the real number 123.456 to the string “123.456” str(123.456) returns a number that you can calculate with date(year,month,day) Converting between strings and dates is usually handled by functions built in to string library modules, e.g. strtodate("01/01/2016"). Example: ß date1 strtodate("18/01/2015") ß date2 strtodate("30/12/2014") ß days date1 - date2 OUTPUT date1, date2, days This will output 2015-01-18 2014-12-30 19 5 SECTION 2 – PROBLEM SOLVING AND THEORY OF COMPUTATION Chapter 12– Finite state machines Objectives • Understand what is meant by a finite state machine • List some of the uses of a finite state machine • Draw and interpret simple state transition diagrams for finite state machines with no output • Draw a state transition table for a finite state machine with no output and vice versa What is a finite state machine? A finite state machine is a model of computation used to design computer programs and sequential logic circuits. It is not a “machine” in the physical sense of a washing machine, an engine or a power tool, for example, but rather an abstract model of how a machine reacts to an external event. The machine can be in one of a finite number of states and changes from one state to the next state when triggered by some condition or input (say, a signal from a timer). In a finite state machine: • The machine can only be in one state at a time • It can change from one state to another in response to an event or condition; this is called a transition. Often this is a switch or a binary sensor. • The Finite State Machine (FSM) is defined by a list of its states and the condition for each transition 2-12 There can be outputs linked to the FSM’s state, but in this chapter we will be considering only FSMs with no output. Example 1 Draw an FSM to model the states and transitions of a door. The door can be open, closed or locked. It can change from the state of being open to closed, from closed to locked, but not, say, from locked to open. (It has to be unlocked first.) Transition condition Transition State Close door Lock door Opened Closed Locked Open door Unlock door 60