Embedded Files
VOCABULARY
Parallel Algorithm - A model where an algorithm can do multiple operations at once and receive and perform multiple instructions at once
Distributed Algorithm - A specific type of algorithm used on computer software that uses interconnected processers. The algorithm runs different sections and calculations of the algorithm at the same time, each on a different processer
Iteration - A repetitive portion of an algorithm that repeats a specified number of times or until a specific condition is met (basically a loop) Iteration is the process of repeating a process/step
Binary Search - An algorithm for finding an item in a list of sorted items, which works by repeatedly dividing in half the portion of the list that could contain the item until there is only one element left. It is much more efficient than a linear search algorithm as it reduces the number of computations the computer needs to do.
List - An ordered collection of elements declared with brackets ([ ]) and separated by commas (,), with each position linked to a corresponding index starting from 0. (ex. list = [0,1,2,3], and accessing an item in a list would be list[index])
Efficiency - Efficiency of a program is measured by how fast, reliable and easy to code/understand a program is. An efficent program would meet all three conditions and be fast with lots of optimization, consistent and have little to no errors, and sufficiently commented and organized to be easy to write and understand.
Heuristic - A algorithm or problem solving approach to find a sufficient and satisfactory solution to a problem where finding the optimal or exact solution is impractical or impossible. (ex. the locker simulation program is a heuristic solution to the problem instead of the impractical method of manually getting 100 students and lockers and having them perform the problem)
Loop - Lines of code that change the sequential flow of control by repeating a set of statements 0 or more times, until a certain condition is met, or infinitely (when the condition never evaluates as true). Basically, a piece of code that will run over and over until it is programmed to stop. There are two types of loops for and while loops.
Traversal - The process of accessing each item in a list one at a time, usually using a loop, and can help determine if a specific item is in a list.
Algorithm - A step - by - step set of instructions implemented by a program to develop and express solutions to a computational problem. A set of rules that are followed in calculations and problems solving operations by a computer.
Index - An index is a tool used to point to a specific item in a list or array using its position (ex. if list = ["apple","banana","blueberry"] list[1] (1 is the index) = "banana")
WRITTEN RESPONSES
Traversals Investigation
The data/information contained in the lists is specific information about each dog breed/name, a photo, and the max height that is taken from the data set . The dogHeight list contains the maximum height of the dog (integer), while the dogNames list contains the name/breed of each dog (string), and finally the dogImages list contains a photo url/image of each dog (URL). There are also the filteredDogName sand filteredDogImages lists, which are used to store the elements or dogs that satisfy the height that the user selects after a loop is ran that appends the information into the list.
The lists help manage complexity in the program as not only makes it more organized, but also makes the program much more simpler and efficient. The three lists allow us to take any information we need about a certain dog . as after it is taken from the data table, all indexes in each list correspond to the same dog. This means we can check a height in the dogHeight list, and after figuring out if it goes in small, medium or large, we know what index to use for the other two lists (dogName and dogImages) to add to the filtered lists. Having lists for all the dogs already means we don't have to return to the tables for any more information as we already have lists with everything. The filteredDogName and filteredDogImages lists store all the possible dogs, allowing us to only have have to randomly pick a index to find a dog to output. We can then clear theses list for reuse after the user switches heights.
Without lists, it would be much more complex to write. Since we don't have a list of the possible dogs (ie: filtered lists) the only way we can randomize the dog picked is to first get a random index, and then use that index to retrieve the dog name, height and image (all stored in variables) from the data set. Then we would check the height, and if it matched, we could output the information. However, this is much more inefficient, as since we're not randomizing from a set of dogs that already work, and it could theoretically take forever until the random number was a index that corresponded to a dog that the size the user wanted. And even it it didn't take long, every single new attempt would mean we have to retrieve the information from the table again, and since we have no way of checking if we've checked a dog already, there is a possibility for us to check the same dog that didn't work multiple times because without a list, we have no way of storing that information.
Lists definitely reduce the complexity of the program a lot by being able to retrieve and store all the data beforehand, easily search through, find, and store dogs that meet the condition (also while not repeating any cases), and then storing them in filtered lists so that we can randomize from a group that already works, meaning we only have to randomize once until we can output the value and then we can clear the filtered lists and restart after the next user input.
Locker Simulation
The locker project simulates the locker problem by using a four-step process of first creating a list to keep track of the lockers, running the simulation using loops and booleans, using a traversal to read and create a list of all lockers that remain open, and finally format and print the result.
STEP 1: Creating a list to keep track of the lockers
After first creating a list to represent all the lockers (lockerList) we use a simple loop to create a list with 1000 zeros. The reason for this is that we can use the simple concept of binary to represent the current state of the locker. Instead of 0 and 1 representing on and off, in our case, 0 and 1 represent if the locker is closed or open. So since the lockers start off as closed, we give all the lockers a starting value of 0.
STEP 2: Running the locker problem simulation
This is probably the most important part of the program. To try to simulate the 1000 people, we use nested loops to cycle through each student, as well as the changes that they will perform.
Since we want to simulate the changes performed by 1000 students, we set up a simple for loop (for(i = 1; i < 1001; i++)) with i being the number of the current student we are simulating. Next, we have to take every i th locker and either open or close it, depending on its state. There are many ways to do this such as cycling through all the numbers and changing its parity (open close state) if does not return a remainder (using mod %), or you could look for the largest factor of the numbers and run a separate loop until it hits that number. However, the method we decided to use a raw interpretation of the problem, and that was to create a "factoring variable" j. Since all the numbers we need to change are just the multiples of the student number, all numbers can be represented as "ij" (some i times some j). So we can nest a while loop, with the condition being to repeat until our ij exceeds the maximum number (1000). Starting from j = 1, and adding 1 to j (j = j + 1) everytime a multiple is resolved, the while loop will run through all multiples of i.
(we also make sure to when changing our term, having the index at i*j - 1 because the list is from 0 to 999 while our multiples are from 1 to 1000)
Now the only thing we have to do is change the term's parity, which we can easily do using a boolean.
All the boolean does is check if the locker is closed, to then open it, or else we know the locker is open, so we close it.
Step 3: Creating a list of opened lockers
After we have ran our simulation, our lockerList looks kinda like this -> [0,0,1,0,1,0,0,0,1 ... ] (just an example, not how it actually looks) and we need to extract all the open lockers, or in our case all the locker positions with a value of 1.
To do this, we use a simple traversal, that scans each individual term of the list, checks if the parity is 1, and if it is, appending it to a openedLockers list (that was previously defined).
Step 4: Formatting and printing
Now that we have a our answer, after adding spacing and making it look clean with concatenation, we are done.
Why is it better?
The locker simulation is much better than a real world simulation because it is much more efficient and practical. To do it in real life, you would need to find 1000 people and 1000 lockers, assign them values, and start the simulation. To also optimize time a bit more, we can have everyone go at once (even though a more likley way is to have everyone go in order), however, it would still take a lot of time for all 1000 people to finish changing their respective lockers (although it gets progressively faster). This also doesn't take into account potential human error as given the amount of lockers and people and the amount of interaction it is very likley that someone might accidently skip or change the wrong locker. We also have to send someone to check to see which lockers are open, which would also take time and be prone to some error. On the contrary, our heuristic solution of a computer simulation is much better. While technically not the actual problem, it is much faster and can solve it in around 3 seconds. It is also a lot more efficient and better suited to a possible scale up, to mabye 10,000 or 100,000 people, although it would be slower, it would be miles faster than a human simulation. These reasons make a computer simulation much more preferred over a real world event. (not to mention costs and convincing needed to get that many people)
Algorithms
Undecidable Problem - A problem that should give a yes or no answer, but no algorithm exists that can answer right on all inputs (ex. halting problem)
Unreasonable Time Algorithm - A problem that would take a massive amount of computing power to solve. While theoretically possible, its exponential growth, time and computing power needed makes it unreasonable. (ex. simulating a human)
The main factor that differentiates a undecidable problem from a unreasonable time algorithm is the fact that one of them has no algorithm that can solve it while the other is theoretically possible but impractical. A case like the halting problem is undecidable because no algorithm exists that can output the correct yes or no answer. However, a different problem/algorithm like one that simulates a human (technically sort of could) have an algorithm that could solve and simulate it, however, the computing power we have right now cannot process the 37.2 trillion atoms in our body in a reasonable amount of time (ie. probably more than hundreds of years into the future). The difference between the two lies in if an algorithm exists that is able to theoretically solve the problem, if none exists, it is a undecidable problem, however, if one although impractical, exists, then it is a unreasonable time algorithm.
Page updated
Google Sites
Report abuse