1.4 data types, structures and algorithms(unfin)

Question 1

primitive data types

Answer 1

complete item, cannot be broken to parts

examples:
integer
real/floating point
character
string
Boolean

Question 2

abstract data types

Answer 2

type/class whose behaviour is defined by a set of value and a set of operations

ABSTRACTION - concerned for what it is representing, not how it is constructed

examples:
list (depends)
stack
queue

Question 3

composite data types

Answer 3

one or more fields dynamically linked to fields in another data type

examples:
class
array
list (depends)

Question 4

static vs dynamic

Answer 4

if it can grow during run time
static: fixed in size, cannot grow
dynamic: flexibility to grow

Question 5

binary

Answer 5

types:
-positive integers
-sign and magnitude
-twos complement
-floating points

operations:
-addition, subtraction
-shifting: AND, OR, XOR

Question 6

ASCII

Answer 6

-aka American Standard Code for Information Interchange
-2^7= 128 different characters
-capital letters A-Z : 65-90
-lower case letters a-z : 97-122
-there are also codes for numbers and symbols

dis: limited character set

Question 7

Unicode

Answer 7

uses a varying number of bits allowing for over 1 million different characters

stores different languages, symbols and emoji

Question 8

arrays

Answer 8

definitions:
(1)composite data type
(2)ordered, (3)finite set of elements of a (4)single type
(5)data are stored in contiguous block of memory
(6)static

notes:
quick searches (binary/ direct access)
slow sort and moving order

Question 9

records

Answer 9

Collection of related fields(of fixed numbers) with mixture of data types
used in database

Question 10

lists

Answer 10

definition: (and diff with array)
abstract data type
list of ORDERED items where items can occur more than once
values are stored NON-CONTIGUOUSLY
more than one data type
dynamic

Question 11

tuples

Answer 11

composite data type
list of ordered items
immutable and static

Question 12

linked list

Answer 12

dynamic data structure
each node has data and pointer

Question 13

graphs

Answer 13

what is a graph?
-arcs/edges
-nodes/vertices
(-weights -> forms a network)

types:
-connected: every node can be reached
-simple: no loops or double connection
-simply connected: simple + connected
-complete: mesh - all nodes connected
-directed: only one direct to travel btw the nodes
-undirected
-bidirectional

Question 14

stack

Answer 14

-ADT
-holds an ordered, linear sequence of items
-LIFO
-recursion (subroutine calls)
-overflow/underflow
-pointers: head and next_free

operations:
push
pop
peek
isEmpty
isFull

Question 15

tree

Answer 15

-simple connected graph with no cycles
-top level is called root
-parent is unique to the children (one to many relationship)

Question 16

binary search tree

Answer 16

each parent has max 2 children
leaf nodes are the bottom level, with no children

Question 17

hash table

Answer 17

-stored as array, with a key map to a unique index
-position of data is determined by hashed value of the key
(position can be called buckets)

collision: when two keys produce the same hash value, the item will be placed in the next available space
(solution to collision: LINEAR PROBING AND CHAINING)
-> rehashing can be done as table grows

use: DBMS- indexing, as it allows quick access

Question 18

sign and magnitude vs twos complement

Answer 18

sign and magnitude: first binary is only the sign
twos complement: first binary is positive/negative number

Question 19

floating point

Answer 19

mantissa is the value, exponent is the power
- the decimal must be place in the most significant numbers
- positive mantissa: make binary bigger
- negative mantissa: make binary smaller
- addition and subtraction: convert to mantissa to the bigger value, then change exponent
-> ignore the overflow

Question 20

logical bitwise operator

Answer 20

mask: binary string that is used to identify the bit you want to operate on

operations:
clear: make the bit 0 (AND 0, XOR 1 mask)
check : return the bit (0/1) (OR 0 mask)
set : make the bit 1 (OR 1 mask)
toggle: flip the bit (XOR 0 mask)

practice: 8 bit binary, check the 7th digit

Question 21

binary shifting

Answer 21

-logical: only applicable to the unsigned (meaning positive and negative numbers are ignored)
-arithmetic: keep the sign (leave the sign bit and shift); negatives: keep negative (two’s complement)
-cyclic: the bit that is floated out goes back at the other end

Question 22

K-map

Answer 22

to simplify Boolean expressions
used for truth tables
written in gray code

Question 23

Boolean expressions with logical operators

Answer 23

what does the CIRCUITS and SYMBOLS look like?
AND
OR
XOR
NOR
XNOR

Question 24

rules to simplify boolean expressions

Answer 24

De Morgan’s Laws: breaking a negation AND changing the operator
NOT(X or Y)-> NOT X n NOT Y
distribution:
A n (B or C) =(A n B) or (A n C)
A OR (B n C) =(A or B) n (A or C)
association: reordering
A n (B n C) = (A n B) n C
commutation: AnB = BnA
absorption: X n (X or Y) = X
double negation: NOT NOT A = A

Question 25

logic gates

Answer 25

flip flops full adder half adder

Question 26

d-type flip flops

Answer 26

logic circuit which can store the value of one bit -2 input : C(clock) and D (A clock is a regular pulse generated by the CPU which is used to coordinate the computers’ components) -when clock is 0 nothing happens to Q -when clock is 1 it recalls to D -notQ is for validation and error checking rising edge flip flop (edge triggered): only measures the data when the clock is at the rising

Question 27

half adder

Answer 27

adds together the number of inputs which are true, and outputs that number in binary -output: sum and carry out how does the truth table looks like?

Question 28

full adder

Answer 28

circuits can be chained together as there is a carry in input -input: extra carry in -output: sum and carry out how does the truth table looks like?