cs paper 1

Question 1

linear seach

Answer 1

-can be sorted/unsorted list
-starts at first item and checks each one
-efficient for smaller data sets
-inefficient for large data sets
-complexity of O(n) linear

Question 2

Binary search

Answer 2

-sorted data set
-starts at middle item and repeatedly divides list in half
-efficient for large date sets
-O(log n)

Question 3

bubbles sort

Answer 3

-orders an unordered list
-by comparing each item with the one next to it if out of order
-finished when no more swaps can be made
-inefficient, easy to implement
-popular for small data sets
-O(n2) -polynomial

Question 4

Merge Sort

Answer 4

-divide and conquer
-2/more identical sub-problems, from larger problem solve individually and combine the solutions
-data is repeadetely spilt until each item is its own list
-adjacent lists are merged back with each items being entered into correct place in new list
-works best with larger data sets where memeory is not a concern
-parallel processing
-O(n log n) linearithmic

Question 5

abstraction

Answer 5

-removing unnecessary detail and only showing details that are important in context

Question 6

need for abstraction

Answer 6

-method of computational thinking and problem-solving that focusus on whats important
-e.g. when you save a file (where is it stored?) level of detail is abstracted, don’t need to be concerned with how it all happens

Question 7

procedural abstraction

Answer 7

-result of abstracting away the actual values used in any particular computation
-e.g. (5 * 7) + 3 = (a * b) + c

Question 8

functional abstraction

Answer 8

e.g. (a * b) + c =
all you have to do is supply the number order, type of inputs required to get output

Question 9

data abstraction

Answer 9

-isolate how a compound data object is used from details of how it is constructed
-e.g. a stack
-could be coded using an array, linked list, OOP
-if data structure behaves like a stack we dont need to worry about specific implementation

Question 10

problem abstraction

Answer 10

-removing details from a problem until its represented in a way possible to solve as it has been reduced to one already solved

Question 11

problem decomposition

Answer 11

-process of taking a large problem and breaking it down into several smaller problems
-repeat process until lowest-level boxes represent a single task or action
-aim = end up with small,independent modules that can be written by a small team, so modules can be written/tested in isolation before being integreated back into solution

Question 12

composition

Answer 12

In bottom up development solutions are developed by plugging together
pre-existing components already proven to work
-Composition abstraction=Combining appropriate procedures to form compound procedure (All routines will be pre-written ,pretested and compiled as part of library)

Question 13

FSM

Answer 13

-model of computation
-Used to design computer programs and sequential logic circuits
-Abstract model power machine reacts to external events
-Changes state based on a trigger Condition or input
-to visualise fsm we draw STD/STT

Question 14

FSM notation

Question 15

State transition table