Computer Science: Component 02 Flashcards
Computational Thinking
Describe the 3 principles of computational thinking.
1. Decomposition - breakig down a complex problem down into smaller problems & solving them indivdually
2. Abstraction - picking out the important bits of information from the problem, ignoring details that don’t matter.
3. Algorithmic Thinking - a logical way of getting from the problem to the solution. If the steps you take to solve a problem follow an alogorithm then they can be used and adapted.
Writing Algortihms
Outline the 3 ways algorithms can be created/interpreted.
1. Pseudocode - Pseudocode reads like a programming language and will clearly show an algorithm’s steps without worrying about the syntax.
- It is also quick to write and can be easily converted into any programming language.
2. Flowcharts - A method of visually representing an algorithm with the use of different shapes for different commands
3. Programming languages - Writing out the actual program in a terminal such as python.
Writing Algortihms - Flowcharts
Describe the different Boxes used in a Flowchart along with their function.
1. Oval = Start / Stop
- Used at the beginning and end of the algorithm
- Sometimes called terminals
2. Parrellelogram = Inputs/Outputs
- Anything that’s put into or taken out of an algorithm goes into a parrellelogram box.
3. Rectangle = Process
- General instructions, processes and calculations go in rectangular boxes.
4. Diamonds = Decisions
- Often a yes or no question, these are put in diamond boxes.
5. Rectangles with 2 parrell lines = Sub programs
- Reference other flowcharts.
6. Arrows = Program direction
- Arrows connect boxes and show the direction you should follow. Some boxes might have multiple arrows going in or out of them.
Search Algorithms
Describe the process for a Binary Search
1. First you find the middle item in the ordered list.
- If there is an even number of items, shift one spot to the left instead.
2. If this is the items, you stop the search.
3. If not, compare the items being searched to the middle term, if the number comes before the middle term, remove the second half of the list, else, remove the first half of the list.
4. Repeat steps 1 to 3 until you find your item.
Search Algorithms
Describe the process for a Linear Search
1. Look at the first item in the unordered/ordered list.
2. if this is the items your looking for, stop the search
3. If not, look that the next Item in the list.
4. Repeat steps 2 - 3 until you find your item or every item has been checked.
Comparison:
- Linear searches are much simpler than binary searches but not as effienct
- A Linear search can be used on ordered or unordered lists.
- Linear searches tend to only be used on smaller lists.
Sorting Algorithms
Describe the process for a Bubble Sort
( Include Advs & Disadvs )
1. Look at the first 2 items in the list.
2. If they’re in the right order, you don’t do anything, else, you swap them.
3. Move on to the next pair of items ( 2nd and 3rd entries ) and repeat step 2.
4. Repeat step 3 until you reach the end of the list, ( this is called one pass ), the last item will now be in the correct place, so don’t include it in the next pass.
5. Repeat all of these steps until there are no swaps in a pass.
Advantages:
- It’s a simple algorithm that can easily be implemented
- It’s an efficient way to check if a list is already in order.
- Doesn’t use very much memory as all the sorting is done using the original list.
Disadvantages:
- It’s an efficient way to sort a list, if there were 10 unordered items you would have to do 45 comparisons!
- It does not do well with very large lists due to its ineffiecency.
Sorting Algorithms
Describe the process for a Merge Sort
( Include Advs and Disadvs )
1. Split the lists in half ( the smaller lists are called sub-lists ) - the second sub-list should start at the middle item
2. Keep repeating step 1 on each sub-list until all the lists only contain 1 item.
3. Merge pairs of sub-lists so that each sub-list has twice as many items, Each time you merge sub-lists, sort the items into the right order.
4. Repeat step 3 until you’ve merged all the sub-lists together.
Advantages:
- In general it’s much more efficient and quicker than the bubble sort and insertion sort algorithms for large lists.
- It has a very consistent running time regardless of how ordered the list are.
Disadvantages:
- It’s slower than other algorithms for small lists
- even if the list is already sorted it still goes through the whole process.
- It uses more memory than the other sorting algorithms in order to create separate lists.
Sorting Algorithms
Describe the process for an Insertion Sort
1. Locks the first item, then looks at the second item in the list.
2. Compare it to all items before it, ( in this case just the first item ) and insert the item in the correct place.
3. Repeat step 2) for the third, fourth, fifth, etc. Items until the last number in the list has been inserted into the correct place.
Advantages:
- It’s an intuitive way of sorting things that can be easily coded
- it copes very well with small lists
- All the sorting is done on the original list so it doesnt equire very much memory.
- Quick at checking if a list is already sorted
Disadvantage:
- Doesn’t cope well with long lists.
Defensive design
Describe the different things to consider when creating a secure program.
- Anticipating Misuse: planning ahead to take steps agaisnt potential misuse.
- Authentication: Ensuring only autherised users can gain acess to a system
- Maintable code: Allowing other programmers to easily read and quickly understand code.
- Validation: Checking whether data meets certain criteria before passing it into a program.
Defensive design
Explain what is ment by Input validation and the different types of validation checks
Input validation - Checking if data meets a certian criteria before passing it into a program
- Range check: Checks the data is within a specified range.
- Presence check: Checks the data has actually been entered.
- Format check: Checks the data has the correct format.
- Look-up table: Checks the data agaisnt a table of acceptable values.
- Length check: Checks the data is the correct length.
Defensive Design
Describe how;
A) Authentication can be used for programs
B) Maintability can be used for programs.
A) Authentication can confirm the identity of a user before they’re allowed to access cetain pieces of data or features of the program.
A1) Some common ways to increase the security of a password-based system are;
- Force users to use strong passwords and have them change passwords regularly.
- Limit the number of failed authentication attempts before access to an account is lost.
- Ask for a random selection of characters from the password on each authentication.
B) Different ways of increasing program maintability are;
- Subprograms - this makes code more reusable, called modularisation
- Identation - improves readability and clearly shows each block of code.
- Appropiate Variable Names - ensured the purpose of a variable is understood.
- Comments - Enable a programmer to understand the purpose of the code. Crucial in team working
Testing
Explain what is ment by iterative and final testing.
Iterative testing - Takes place during program development
- The programmer develops a module, tests it and repeats this process until it works
- This is used to identify and fix small errors to prevent larger ones.
Final testing - Takes place after development and before the program is released to the end user
- This testing takes place once all modules have been individually tested to ensure the whole program works.
- Used as modules that may work individually may crash when working together.
Testing
Describe the different types of test data.
- Normal data - Data a program should accept & process
- Boundary data - data at the extreme of what a program can handle
- Invalid data - Data of the correct type that does not get accepted.
- Erroneous data - Data of the wrong type that should get denied.
Translators
Describe the purposes and features of;
A) High-level languages
B) Low-level languages
A) High-Level Languages
- One instruction of high-level code represents many instruction of machine code.
- The same code will work for many different machines and processors.
- The programmer can easily store data in lots of different structures without knowing about the memory structure.
- Code is easy to read,understand and modify.
- Must be translated before a computer is a able to understand it.
- You don’t have much control over what the CPU actually does so programs will be less memory effiency and slower.
B) Low-Level Languages
- One instruction of assembly code usually only represents one instruction of machine code.
- Usually written for one type of machine or processor.
- The programmer needs to know about the internal structure of the CPU and how it managed memory.
- Code is very difficult to read, understand and modify.
- Commands in machine code can be executed directly without the need for a translator.
- You control exactly what the CPU does and how it uses memory so programs will be more memory effiect and faster.
Translators
Describe the features of;
A) Compilers
B) Interpreters
A) Compilers;
- Translates all of the source code at the same time and creates one executable file. - called the object code
- Only needed once to create the executable file.
- Returns a list of errors for the entire program once compiling is complete.
- Once compiled the program runs quickly, but compiling can take a long time.
B) Interpreter
- Translates and runs the source code one instruction at a time, but doesn’t creat an executable file
- Needed every time you want to run the program.
- The interpreter will return the first error it finds and then stops, useful for debugging.
- Programs will run more slowly because the code is being translated as it runs.
IDEs
Explain some different commons features found within IDEs.
1. Run-time environment - allows the code to be run quickly within the IDE - this is done using a start or run button.
- The run-time environment can also help to indentify logic errors in the program as the programmer can see which part of the code is running when errors occur.
2. Error diagnostics - these and other debugging tools help to find and fix errors in a program - they’ll tell you the location of the error and often suggest ways to fix it.
3. Code editor - The main part of the IDE, it’s where the code is written. Most code editors will have line numbering and auto-colour coding for things like strings, functions, loops variables etc.
- Good code editors have other features like; auto-correct, auto-identation and auto-complete.
4. Translators ( compilers, interpreters or both ) - which allows source code to be understood by the computer. If the IDE has both you can take advantages of each translator’s best features.
