Computer Science 101 Flashcards
What are the two states in binary due to electricity switches?
0 (off) and 1 (on)
What numbering system do humans commonly use?
Decimal system (0-9)
How is a number incremented in the binary system?
After a bit reaches 1 in binary, an increment resets it to 0 but also causes an increment of the next bit to the left: 0000, 0001, (rightmost bit starts over, and the next bit is incremented)
What is the base of the binary number system?
It uses base 2, so counting like 1, 2, 4, 8 …
How do you convert a binary number to a decimal number?
Add the values of the positions with a 1, from right to left, using powers of 2.
Example:
128 64 32 16 8 4 2 1
1 0 1 1 0 0 1 1 = 179
How do you convert a decimal number to a binary number?
write out the ^ to the power of numbers, working from the biggest number, subtract the numbers and put a 1 next to them until you’re left with 0
What is a logarithmic function?
The opposite of an exponential function; it increases quickly at first and then levels out.
What is an exponential function?
A function that increases rapidly - like timesing itself
Why is the growth pattern of n-notation important?
It allows comparing the efficiency and scalability of algorithms by understanding how their performance changes with increasing input size.
What is the Big O notation used for?
To represent the upper bound of the time complexity of an algorithm, indicating the worst-case scenario.
What does O(n) signify in Big O notation?
Linear time complexity
What does O(1) signify in Big O notation?
Constant time complexity (the time it takes to complete its task is constant and does not change with the size of the input data)
What is a fixed array?
An array with a predefined size. (you’re asking the computer to look through its hard drive, find a slot with room for the array - for example 3 pieces of data.)
What is a dynamic array?
An array that can grow in size as needed.
What would the run time be (using big O) to insert randomly into a fixed array?
O(n) - inserting randomly requires moving data around in the array, at worst it will need to move every item in the array
What is a linked list?
A data structure where each element (node) points to the next, and sometimes the previous, element.
What is the difference between a singly and doubly linked list?
A singly linked list has nodes that point only to the next node, while a doubly linked list has nodes that point to both the next and the previous nodes.
What is a stack?
A data structure that follows the Last In, First Out (LIFO) principle. (like a stack of trays in a canteen - grab and add from the top)
What is a queue?
A data structure that follows the First In, First Out (FIFO) principle.
What is a binary search tree (BST)?
A tree structure where each node has at most two children, and the left child is less than the parent node, while the right child is greater.
What is a heap?
A tree-based data structure where the parent node is either greater than (max heap) or less than (min heap) its children.
What is the purpose of a priority queue?
To manage elements based on their priority, where higher priority elements are served before lower priority ones.
What is a graph?
- A collection of nodes (vertices) connected by edges.
- Nodes represent entities such as cities, people, or web pages.
- Edges represent the relationships or connections between nodes, such as roads between cities, friendships, or hyperlinks.
- Graphs can be directed (edges have a direction) or undirected (edges have no direction).
- Common uses include representing networks, social connections, and pathways.
What is the difference between directed and undirected graphs?
Directed graphs have edges with a direction, while undirected graphs have edges with no specific direction.
