Fundamentals of Algorithms Flashcards
Understand and explain the term algorithm
An algorithm is a sequence of steps that can be followed to complete a task
Understand and explain the term decomposition
Breaking a problem into a number of sub-problems, so that each sub- problem accomplishes an identifiable task, which might itself be further subdivided
Understand and explain the term abstraction
the process of removing unnecessary detail from a problem
Understand and explain how the linear search algorithm works.
Goes through the list checking each element until it has found a match
Understand and explain how the binary search algorithm works.
Continues dividing list into 2 until element is found. Has to be in order
Understand and explain how bubble sort works.
Swaps the elements until they are in order
Understand and explain how merge sort works.
DIVIDE, CONQUER AND COMBINE
Advantages and disadvantages of the searches
Linear is much more simpler but binary is more efficient. Linear can be used on any type of list, even unordered, usually smaller ones. Binary can only be used on ordered lists, takes fewer steps so can be used on larger lists
Compare and contrast merge sort and bubble sort algorithms
Bubble sort: Easily implemented on a computer, efficient way to check if list is already in order. Doesn’t use much memory.
Inefficient way to sort a list, does not cope well with a very large list.
Merge sort: More efficient and quicker than bubble sort for large lists, very consistent running time.
Slower than other algorithms for smaller lists, uses more memory
Understand the concept of a data type
A means of classifying different data. Determines what operations can be conducted and how the data will be stored.
What is casting?
Changing the data type
What is a sequence, iteration and selection?
Sequence - all lines executed
Selection - decisions made that determine the execution
Iteration - code repeated until specified conditions met
What is a variable?
References to locations in the memory containing single values
What is a constant?
Identifier that are associated with values that remain fixed during the programs execution
Why are constants and variables used?
They are easier to read by making the code more clear. and have a better ability to update as you only need to update the initial value once
What is a subprogram?
An “out of line” block of code that performs a specific task
Advantages of subprogram
Saves time when there is a pattern in a codecan be either user-written or pre-existing
What is a local variable?
Variables that are only declared inside a function and are local to that subroutine
Explain why it is good practice to use local variables?
You can use multiple variables with the same name in a program as they take precedence over variables with the same name
Describe the structured approach to programming
The three controls should have a single entry and exit and the problem should be decomposed into specific, sea-contained and independent modules.
Independent subroutines should not be reliant of global variables as data should be passed through parameters and there should be indentations.
