Algorithms

Question 1

what is an algorithm?

Answer 1

a set of clearly defined , step by step instructions used to solve a problem, with a clear start and end point, providing a valid output from valid inputs

Question 2

what kinds of problem are solved by algorithms (generally)?

Answer 2

• routing problems - data packets across internet, quickest salesman route, etc.
• timetabling aircraft crews so they don’t work overtime
• searching info from the internet on a database
• encrypting communication
• sorting lots of data
• writing a compiler program to translate a high level language into machine code

Question 3

what makes a good algorithm?

Answer 3

• correct outputs for all valid inputs
• must terminate at some point
• each step is a clearly defined task
• well defined inputs + outputs
• problem should be solvable
• designed so others can understand + modify
• precise + efficient
• able to handle invalid inputs

Question 4

what is time complexity?

Answer 4

how much time is required to solve a particular problem using an algorithm - refers to the number of operations or steps to complete + independent of hardware performance

Question 5

what is Big O notation?

Answer 5

• shows the effectiveness of an algorithm by expressing time/space complexity of an algorithm
• shows an upper limit for the amount of time taken relative to the number of data elements inputted

Question 6

what is scalability?

Answer 6

how much the algorithm slows down when input size into the algorithm increases

Question 7

what is constant time complexity?

Answer 7

• O(1)
• algorithm always takes the same number of steps, regardless of input size
• eg. accessing an item in an array using an index

Question 8

what is linear time complexity?

Answer 8

• O(n)
• the number of steps increases proportionally with input size n
• eg. traversing an array

Question 9

what is polynomial time complexity?

Answer 9

• O(n^2)
• performance is directly proportional to the square of the size of the data set
• eg. nested FOR loops

Question 10

what is exponential time complexity?

Answer 10

• O(2^n)
• running time will double with every additional item in the dataset
• run time increases exponentially and quickly becomes very large
• usually when you have to try every possible combination
• eg. recursive algorithms

Question 11

what is logarithmic time complexity?

Answer 11

• O(log n)
• time taken depends on half the input size - in proportion to the log of the input
• number of steps grows slowly even when input size grows rapidly
• eg. binary search

Question 12

what is a permutation?

Answer 12

the number of ways that n items can be arranged

Question 13

what are the 2 types of permutation?

Answer 13

• repetition allowed - eg. combination lock with 4 digits 0-9
• no repetition allowed - eg. 4 differently coloured ball in a bag that you draw out one at a time

Question 14

what is the time complexities of the 2 types of permuation?

Answer 14

• repetition allowed: O(n^r), where n=number of available elements, r= length of each permutation
• no repetition allowed: O(n!) - very very inefficient for large values of n

Question 15

rank the different time complexities in order of most to least efficient

Answer 15

1. O(1)
2. O(log n)
3. O(n)
4. O(n^2)
5. O(2^n)

Question 16

how do you calculate the Big O of an algorithm?

Answer 16

• count the number of assignment statements in the algorithm
• only the dominant term is significant - any other constant coefficient is ignored
• eg. O(3n^2 + 5n + 2) -> O(n^2)

Question 17

what is a binary tree?

Answer 17

a rooted tree with a maximum of 2 child nodes

Question 18

what are the 3 parts of a node?

Answer 18

• data (primitive/complex)
• left pointer to a child
• right pointer to a child

Question 19

what are the 3 types of traversals?

Answer 19

• pre-order - visit the root, then traverse the left subtree, then the right subtree
• in-order - traverse left subtree, then visit the root, the traverse the right sub tree
• post-order - traverse left subtree, then traverse the right subtree, then visit the root

Question 20

what is a balanced binary tree?

Answer 20

where nodes are distributed in such a way that the height is kept to a minimum to enable more efficient searching

Question 21

what is an unbalanced binary tree?

Answer 21

where the heights of the left and right subtrees of one or more nodes differs significantly - more linear structure -> inefficient operations