midterm 1 - basics

Question 1

define abstraction

Answer 1

being able to explain how something works

Question 2

top down vs bottom up problem solving

Answer 2

top/down –> start with the problem, identify solution –> determine steps required to achieve the solution

bottom/up –> construct independent components and combine into unknown final solution

Question 3

high level vs low level descriptions

Answer 3

high level = broad/generalistic explanation of the overall item

low level = detailed explantion about each component

eg
high level: internal combustion operates based on gas/o2 mixture to push pistons and rotate shaft
low level: the carburetor and fuel injector operate in sync based on the cam shaft to provide optimal fuel/air mixture for max energy output per 4-stage cycle

Question 4

define algorithm + list 4 examples

Answer 4

algorithm = a step by step process of problem solving. May involve inherent degree of intentional randomization. May be hyper specific or more flexible/robust

examples
divide/conquer (recursion)
binary search (1/2 method)
quicksort (lock/key)
4 colour sort

Question 5

divide/conquer (recursion) algo

Answer 5

problem solving algo

recursively divide the problem into many smaller subproblems –> each portion is trivially simple and easily solvable

combine indiv solutions to form overall solution

Question 6

binary search (1/2 method) algo

Answer 6

used as a basic search algo

divide search area in half –> is item here? yes
subdivide 1/2 –> check for item

repeat until search area is precisely narrowed down to isolate target item

Question 7

quicksort (lock/key) algo

Answer 7

sorting algo

pick any item (key) in the group, sort it –> lock it’s position (lock)

left group and right group beside lock
recursion –> pick new keys within these groups and sort accordingly. Repeat with subgroups and making new key/locks until the entire group/set is fully sorted

Question 8

four colour sorting algo

Answer 8

used in image processing to distinguish independant regions (eg mapping)

postulates that when colouring image sections in a manner that no adjacent sections share the same colour, any image regardless of complexity only requires a max of 4 colours

Question 9

describe CS graphs + graph terminology

Answer 9

graphs = visualization of data structure + relationships btw data points

components
vertices = data points
edges = data relationships

Question 10

diff graph types (4)

Answer 10

weighted graph = includes magnitudes per edge to convey relationship strengths btw data (eg smaller edge length = more closely related)

planar graph = standard data graph without overlapping any components (edges do not cross over eachother)

directed graphs = shows relationshp + how 1 data pt affects others using directionality (eg demonstrates X data modified causes downstream change to Y and Z data values)

undirected = data flow direction is not a factor. only shows relatedness

Question 11

graph colouring problem

Answer 11

in any data graph, vertices may be coloured in a manner that all edges are connecting 2 diff colour vertices. therefore all data graphs only need 3 colours to achieve this

similar to 4 colour image theorem, both concepts highlight that related data groups may be sorted into just a handful of secrtions “colours”

Question 12

continuous/analog vs discrete/digital

Answer 12

continous data is infinitely divisible and can be finely measured to a theoretically unlimited degree of accuracy. Often refers to the raw information input from user/environment

discrete/digital data has a limited degree of accuracy (eg finite number of decimal points) often due to hardware limitations of computers

Due to system limitations, there is a limited amount of values that may be stored. therefore a highly accurate data input is stored to a limited degree of accuracy. this causes an inherent loss of information/detail when an analog input is stored as a digital value (eg taking photos and losing colour accuracy)

Question 13

why use binary 1s and 0s?

Answer 13

information is simply boiled down as the flow of electricity, or no electricity –> on/off

complicating by storing info based on degree of electrical input (beyond all/nothing) may lead to recipient confusion when distinguishing degree of signal strength

1/0 is simple, minimizes confusion and is therefore reliable

Question 14

bits vs bytes

Answer 14

each binary position of 1 or 0, a “switch” is referred to as 1 bit

8 bits = 1 byte (why 8? arbitrarily chosen)

Question 15

in binary, how to determine possible data combinations?

Answer 15

2^k
where k = # of bits being used
2 denotes possible values per bit –> 1 or 0