Computer science unit 2

Computer science unit 2

1. ALGORITHMS

   • Searchs
     • Linear
       • searches each item in list, compare w/ target until it matches/finished searching list
       • does not need to be sorted, simple to understand
       • inefficient on long lists, takes too long
     • Binary
       • needs to be sorted
       • efficient on large lists
         • very fast
           • cancels half of list by finding midpoint
       • finds midpoint of list
         • compares with search target
           • if search target > midpoint - looks at upper bound
             • continues until found
           • if search target < midpoint - looks at lower bound
   • Sorts
     • Merge
       • halves list into two until single elements then merges back together in order
       • efficient on large lists
       • fastest out of all sorts
       • too complicated for smaller lists
     • Insertion
       • go through data one by one + check if current data is bigger/smaller than the number that was before it
       • slow + inefficient on large lists
       • good for small lists, simple + accurate
         • pass through the array once
     • Bubble
       • repeatedly swapping adjacent item if they are in wrong order, until they are in the correct order.
       • not as efficient, takes many passes
       • simple to understand + implement

2. PROGRAMMING TECHNIQUES

   • Sequence
     • executed in the order they are written:
     • total = mark1 + mark2 average = total / 2 print (total, average)
   • Selection
     • next statement to be executed depends on whether the condition being tested is true or false
       • if statement
         • if average >= 80 then print ("Distinction") else print ("Pass") endif
   • Iteration
     • repetition
       • for... next
         • execute the loop a specified number of times - for counter = 1 TO 7
       • while... endwhile
         • execute the loop while a certain condition is true, tested at beginning
           • while emailAddress does not contain “@”
       • do... until
         • execute loop until certain condition is true, tested at the end of loop
           • do ... until emailAddress contains “@”
             • not in python, used for pseudocode

3. TRANSLATORS/COMPILERS

   • 1st generation
     • machine code
       • Directly Executable by the processor, computer understands
       • hard to debug, hard to understand, difficult to program in
       • 0001 - input 1100 - store 0010 - output
     • no translator needed
   • 2nd generation
     • assembly code uses mnemonics
     • easier to program in compared with 1st generation but still difficult
       • slower than 1st generation- needs to be translated
     • One Assembly Language instruction translates to one Machine Code Instruction (1-1 relationship)
     • uses assembler to translate
     • used to program Device Drivers
       • control the operation of a Hardware Device, GCD
   • 3rd generation
     • uses compiler to translate: translates in 1 go + displays error message afterwards
       • harder to debug, hardware specific - suited to certain computer
     • uses interpreter to translate: translates as program running (line by line) + if error found interpreting stopped; if not continue
       • longer to run, slower
     • easier to understand (uses English like key words) easier to debug
       • One instruction translates into many machine code instructions

4. ARRAYS/LISTS

   • data structure that is fixed in size, capable of storing data, accessed by an index
     • use 0 based counting (starts at zero)
   • sorce = [ ]
     • declaration
       • memory set aside for contents, giving name to memory space
         • x
   • score[0] = 3
     • 3 is value to be stored at index
       • assingment
         • putting data into memory location
           • x = 6
     • 0 is position in list
   • score = [1,2,3,4,5]
     • scores[0] = 4
       • score = [4,2,3,4,5]
       • changed value stored at position 0

5. SUBROUTINES

   • code broken up into manageable segments
     • set of program instructions that do specific task
   • call
     • execute subroutine
       • Menu ()
     • instruction that starts subroutine
   • parameters
     • info about data being passed to a function in brackets
       • def FirstTask (textToDisplay, num) :
         • num + textToDisplay = paramters
     • arguments
       • value passed to parameter
         • meal = input("Enter meal") price(meal)
           • sending response to subroutine
   • function
     • section of code, performs specific task, returns value
       • algorithm to calculate VAT
   • procedure
     • does not return value
     • algorithm for making a square