Algorithms and Data Structures Flashcards
What is an algorithm?
A set of rules or instructions for completing a task.
Study Flow charts for algorithms.
Explain some simple data structures.
Stacks: A stack is a data structure that works under a specific philosophy: Last In, First Out (LIFO). Pop will take the top piece of data from the stack, which removes it. Push will add a new item to the top (and only the top) of the stack. (Sequential)
Linked lists: Sequential data storage structure. Instead of being stored in a simple stack of data, each element is linked to the next.
Arrays: It provides random access for reading and writing data. they refer to elements in the structure by an index number.
Multidimensional Arrays: Think of a checkerboard.
What does bounded mean?
They have a set size.
Why is it important to sort data?
To more efficiently find the data.
What is a binary search?
It continually splits the data size into two.
Explain some search algorithms.
Linear search: It starts at the beginning and looks at each element in order.
Jump search: Let’s say the book is 2,500 pages long. We calculate the square root of n, the number of pages, which gives us 50, which we will use for the jump size, or m. Ken will first jump to page 50 and see if Josh is higher or lower, then keep jumping until he is past Josh. Then, he will go back to the previous jump and do a linear search (page by page) on the next 50 pages to find him.
Binary search: Ken would start at page 1,250 of our 2,500-page book, and if Josh was higher in the list then jump half the remaining space, 625 pages, and keep splitting it until he arrived on the proper page.
Explain some sorting algorithms.
Bubble sort: You can imagine how it works by thinking of the largest values “bubbling” to the top, like air bubbles in your drink. The rules for bubble sort are this: starting at the beginning, compare the first two values. If the first one is larger, move it to the second. If it is not, they are already in order. Then compare the next two values and do the same until you reach the end. Once this is done, do it again for every element except the last one, since it will be in order now.
Binary insertion sort: The binary insertion sort is based on the same method we used for a binary search—by splitting the data in half repeatedly.
Quick sort: Imagine a teacher with a stack of graded papers. The teacher wants to sort all of the papers by grade. The pile is split into all the grades higher than 55 (this number is the pivot and can be chosen by different methods) and those less than 55. Then the two piles are split around another pivot bringing the total number of piles to four. The teacher then sorts each pile separately and when they are done, can simply put all the piles back together in order from lowest pile to highest. It can be thought of as a “divide and conquer” type of method.
What affects the quality of an algorithm.
Huge data spaces: Some data spaces are so large that an exhaustive search of the data space will simply cost too much time. Instead, programmers create an algorithm that will create a “good” solution as opposed to an optimal solution.
Algorithm accuracy: Some algorithms are required to give the optimal solution. For instance, if we are sorting data, the algorithm cannot stop until everything is sorted with 100 percent accuracy.
Correct algorithms: Any algorithm that is used must be mathematically correct.
Algorithm termination: An algorithm must know when to stop its calculations. A good programmer will terminate the algorithm at the first moment the task is complete without wasting any processor time on the computer.
What is the “Big-O” notation?
The “Big O” function demonstrates the mathematical complexity of an algorithm, which is based on the data size of “n” elements. For instance, bubble sort takes approximately n2 steps to be completed, so we write it as: O(n^2)
