U6 - Programming and Algorithms

Lesson 1 - Algorithms

Problem Solving - recognizing patterns and similarities

Problem - a general description of a task that can (or cannot) be solved with an algorithm

Algorithm - a finite set of instructions that accomplish a task

Sequencing - putting steps in an order

Selection - deciding which steps to do next

Iteration - doing some steps over and over

Lesson 2 - Algorithm Efficiency

Efficiency - a measure of how many steps are needed to complete an algorithm

Linear Search - a search algorithm which checks each element of a list, in order, until the desired value is found or all elements in the list have been checked

Binary Search - a search algorithm that starts at the middle of a sorted set of numbers and removes half of the data; this process repeats until the desired value is found or all elements have been eliminated

Lesson 3 - Unreasonable Time

Polynomial - any algorithm whose efficiency includes an n^2, n^3, n^4, …

Exponential - any algorithm whose efficiency includes a 2^n, 3^n, 4^n, …

Reasonable Algorithms - Polynomial, Linear, Log / Sorted

Unreasonable Algorithms - Exponential / Group

Reasonable Time - algorithms with polynomial efficiency or lower (constant, linear, square, cube, etc.)

Unreasonable Time - algorithms with exponential or factorial efficiencies

Lesson 4 - Limits of Algorithms

Factorial - mathematical function n!, ex: 4! = 4 x 3 x 2 x 1, 3! = 3x 2 x 1

Decision Problem - is there a path?

Optimization Problem - what is the shortest path?

Heuristics - finding a ‘good enough’ solution when an actual solution is impractical or impossible

Traveling Salesman Problem - a type of optimization problem. It is unreasonable so we use a heuristic solution

Undecidable Problems - no algorithm can be constructed that is always capable of providing a correct yes-or-no answer, ex: the halting problem

Lesson 5 - Distributed Algorithms

Sequential Computing - steps are performed in order, one at a time

Parallel Computing - some steps are performed at the same time, this method is only as fast as its slowest section

Limit to Processing Power - at a certain point, adding more processors doesn’t really help (parallel programs don’t get faster forever)

Distributed Computing - programs are run by multiple devices

Speedup - the time used to complete a task sequentially divided by the time to complete a task in parallel