Computer science unit 2

ALGORITHMS
1. Searchs
  1. Linear
    1. searches each item in list, compare w/ target until it matches/finished searching list
    2. does not need to be sorted, simple to understand
    3. inefficient on long lists, takes too long
  2. Binary
    1. needs to be sorted
    2. efficient on large lists
      1. very fast
        cancels half of list by finding midpoint
    3. finds midpoint of list
      1. compares with search target
        if search target > midpoint - looks at upper bound
        continues until found
        if search target < midpoint - looks at lower bound
2. Sorts
  1. Merge
    1. halves list into two until single elements then merges back together in order
    2. efficient on large lists
    3. fastest out of all sorts
    4. too complicated for smaller lists
  2. Insertion
    1. go through data one by one + check if current data is bigger/smaller than the number that was before it
    2. slow + inefficient on large lists
    3. good for small lists, simple + accurate
      1. pass through the array once
  3. Bubble
    1. repeatedly swapping adjacent item if they are in wrong order, until they are in the correct order.
    2. not as efficient, takes many passes
    3. simple to understand + implement
3. scheduling and sequence
  1. First in first out (FIFO)
    1. stack
  2. Last in first out LIFO\FILO
    1. queue
  3. Least recently used (LRU)
  4. Time aware least recently used (TLRU)
  5. Most recently used (MRU)
  6. Least-frequently used (LFU)
PROGRAMMING TECHNIQUES
1. Sequence
  1. executed in the order they are written:
  2. total = mark1 + mark2 average = total / 2 print (total, average)
2. Selection
  1. next statement to be executed depends on whether the condition being tested is true or false
    1. if statement
      1. if average >= 80 then print ("Distinction") else print ("Pass") endif
3. Iteration
  1. repetition
    1. for... next
      1. execute the loop a specified number of times - for counter = 1 TO 7
    2. while... endwhile
      1. execute the loop while a certain condition is true, tested at beginning
        while emailAddress does not contain “@”
    3. do... until
      1. execute loop until certain condition is true, tested at the end of loop
        do ... until emailAddress contains “@”
        not in python, used for pseudocode
TRANSLATORS/COMPILERS
1. 1st generation
  1. machine code
    1. Directly Executable by the processor, computer understands
    2. hard to debug, hard to understand, difficult to program in
    3. 0001 - input 1100 - store 0010 - output
  2. no translator needed
2. 2nd generation
  1. assembly code uses mnemonics
  2. easier to program in compared with 1st generation but still difficult
    1. slower than 1st generation- needs to be translated
  3. One Assembly Language instruction translates to one Machine Code Instruction (1-1 relationship)
  4. uses assembler to translate
  5. used to program Device Drivers
    1. control the operation of a Hardware Device, GCD
3. 3rd generation
  1. uses compiler to translate: translates in 1 go + displays error message afterwards
    1. harder to debug, hardware specific - suited to certain computer
  2. uses interpreter to translate: translates as program running (line by line) + if error found interpreting stopped; if not continue
    1. longer to run, slower
  3. easier to understand (uses English like key words) easier to debug
    1. One instruction translates into many machine code instructions
ARRAYS/LISTS
1. data structure that is fixed in size, capable of storing data, accessed by an index
  1. use 0 based counting (starts at zero)
2. sorce = [ ]
  1. declaration
    1. memory set aside for contents, giving name to memory space
      1. x
3. score[0] = 3
  1. 3 is value to be stored at index
    1. assingment
      1. putting data into memory location
        x = 6
  2. 0 is position in list
4. score = [1,2,3,4,5]
  1. scores[0] = 4
    1. score = [4,2,3,4,5]
    2. changed value stored at position 0
SUBROUTINES
1. code broken up into manageable segments
  1. set of program instructions that do specific task
2. call
  1. execute subroutine
    1. Menu ()
  2. instruction that starts subroutine
3. parameters
  1. info about data being passed to a function in brackets
    1. def FirstTask (textToDisplay, num) :
      1. num + textToDisplay = paramters
  2. arguments
    1. value passed to parameter
      1. meal = input("Enter meal") price(meal)
        sending response to subroutine
4. function
  1. section of code, performs specific task, returns value
    1. algorithm to calculate VAT
5. procedure
  1. does not return value
  2. algorithm for making a square

Next up

Computer science unit 2

Description

Resource summary

Similar

	Created by Somto Ibeme about 6 years ago

	Copied by джордж гаврилович about 4 years ago