clc80

1. Write pseudocode for bubble sort.

While swapped != FALSE
   FOR EACH element in ARRAY
      IF element > element + 1
         tempElement = element
         element = element + 1
         element + 1 = tempElement
         swapped = true
      ELSE IF

clc80

Short Answer
1. What is a real-life scenario that uses linear search?
Opening a box that contains old books and wanting to find a particular novel. We would have to search through all the books one by one until we find the book we wanted. 


2. What is a real-life scenario that uses binary search?
Searching for a book in the library. Here our sorted list is the well-arranged books in alphabetical order. Our target element is the book we prefer to read. All we need to do is determine the total number of racks, then find the middle rack. If we don’t find the book, then we accordingly determine whether to omit the first half of the racks or the second half. We repeat this process till we finally find our book or run out of racks to look in.

3. Given the alphabetically sorted collection in this checkpoint, how many iterations would it take to find the value G using linear search?
It would take 7 iterations to find the value of G.

clc80

1. Define and compare recursion and iteration.
Iteration is looping through an array or going through a list one by one until you run out of things to loop through. 
Recursion is calling a function again for each item in a list/array. 

Recursion might not be as easy to get at first but it makes the code easier to read and easier to implent as opposed to iteration. 

2. Name five algorithms that are commonly implemented by recursion.
factorial
Fibonaci Numbers
primality Tester

clc80

1. What is time complexity and what is its relation to algorithms?
Time complexity is how long it takes to execute a program. Time Complexity is most commonly estimated by counting the number of elementary steps performed by any algorithm to finish execution.

2. What is runtime?
Runtime is the physical time dureation of the algorithm. 

3. How is the runtime of an algorithm calculated?
The most common metric for calculating runtime is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N, as N approaches infinity. 
a) Add up how many instruction the algorith will execute
b) Simplify the expression to the largets term

clc80

1. Using proper pseudo-code, describe the following primitive algorithms:

Making coffee;
Clean pot
Put water in the pot
Throw away old filter
Add new filter
Measure out coffee grounds
Place coffee grounds in filter
Add water in tank

clc80

Exercises

1. What is a binary tree and what makes it unique to other trees?
A Binary tree is a data structure that isn't linear. It's herarchical it looks like a family tree. A binary tree is different from other trees in that it can have no more than 2 childen. Usually called a right and left child. 

2. What is a heuristic?
A heuristic is a mental shortcut that allows people to solve problems and make judgments quickly and efficiently. These rule-of-thumb strategies shorten decision-making time and allow people to function without constantly stopping to think about their next course of action.

3. What is another problem besides the shortest-path problem that requires the use of heuristics?
Playing and winning at Chess is another problem that requires the use of heuristics. . It would be tempting to design an algorithm that could investigate every single possible move that players can make and investigate the impacts of such moves on the outcome of the game. However such an algorithm would have to investig

clc80

1. What are some pros and cons of using linked lists instead of arrays?
PROS
Arrays have a somewhat fixed size, Linked lists are dynamic in size
Room has to be made when adding elements to an array, not with linked lists
Items have to be moved when items are deleted from an array, not with linked lists

CONS
Random access is not allowed. Elements are accessed in order starting with the top
Extra memory is needed for the pointer

clc80

1. What is the main difference between a stack and a queue?
The main differences between stack and queue are that stack uses LIFO (last in first out) method to access and add data elements whereas Queue uses FIFO (First in first out) method to access and add data elements

2. What are the similarities between stacks and queues? 
One big similarity is that the user is not allowed to pick items from the middle of the queue or the stack. No indexes are available, as in arrays.

3. Imagine you are an engineer tasked with implementing the UNDO and REDO options in a word processor such as Microsoft Word. Which data structure would you use for each option and why?
In the case of an UNDO it would be a stack because we want to undo the last thing that we deleted. 
In the Redo task would also be a stack. We usually want to redo the last command that we did so it's also a last in first out situation. 

clc80

1. What is a hash table?
Just like it sounds like a hash table is a table. A hash table just like an object works with the idea of a key value pair. 
The key should be a unique key from all the others in the table. A hash table is made up of two parts: an array (the actual table where the data to be searched is stored) and a mapping function.

2. What is hashing?
Hashing is the conversion from a string to a numerical index. In hash tables the key is usually a string. The process of hasing will create a numerical index value for that string. 
It needs to be converted into a number since arrays can only be indexed by numbers.

3. How does a hash table store data?
With an array I can put something in the boxes, then get it back by telling the program go get what is in box 5. This is known as direct addressing, and in the case of arrays, it takes a single operation due to the way RAM works.

clc80

1. A line of people at an amusement park ride.

The line is composed of members, represented as strings.
There is a front to the line, as well as a back.
When someone enters the line, place them at the end.
People may leave the line whenever they see fit, and those behind them take their place.
Given the above real-world information, use an array data structure to code the following solution.

a) Use an array input: ["Vivian", "Ava", "Josh", "Patrick", "Mike"]
b) Insert a new person, "Mary" at the end of the line. In other words, you should insert Mary after Mike.