Regular Expressions & Data Cleaning

• Assignment 2 due date is Feb. 24th by 11:59pm.
• The due date for Assignment 2 has been extended from what is given in the course syllabus.
• Assignment 2 covers regular expressions and cleaning data.
• Data will be used as an example next class (week 6).
• Survey participation is worth 100 participation points and must be done by Friday (Feb. 7th) at 11:59PM.
• Input values can be in any unit but do not list the units (numbers only).

Notepad++ Examples

• Substitutions are demonstrated in Notepad++.

Phone Number Reformatting Example

• Phone numbers can be reformatted to ###-###-#### ext. ##### form.
• Find: (\d{3})[-](\d{3}-\d{4}) x(\d{5})
• Replace:\1-\2 ext\. \3

Name Column Split Example

• Name column can be split into First and Last name columns.
• Find: ^([a-zA-Z\-\. ]+), ([a-zA-Z\-\. ]+)\t
• Replace: \2\t\1\t

Title Removal Example

• Mr. and Dr. titles can be removed from first names.
• ^(Mr|Dr)\. with a space at the end is used to find the titles.
• The transformed data can be pasted into Excel.

Assigned Readings

• Readings for the week include:
  • GCFGlobal: Algorithms Tutorial
  • GCFGlobal: Hardware and software
  • GCFGlobal: Programming Languages
  • GCFGlobal: Sequences, selections, and loops
• VBA readings for the next few weeks can be found at Home & Learn.

What is Computation?

• Physical objects are used such as abacus, slide rules, etc.
• Human computation includes mental or pencil and paper arithmetic.
• Computers were people in the 1930s – 1940s.
• Natural computation uses ants, DNA, and molecules.
• Analog electronic computing circuits represent numerical values with voltage.
• Circuits provide voltages that represent computed functions like addition or integration.
• Digital electronic computing uses circuits where a voltage threshold is either met (1) or not (0).
• Voltages on many lines represent numbers.

Moore's Law

• Gordon E. Moore noticed in 1965 that integrated circuit speeds doubled about every two years
• Computer processor speed has since doubled about once every 18 months to two years from the 1950s.
• The law has become a self-fulfilling prophecy.

Limits of Computation

• Hard limits of computation theoretically exist due to the:
  • Speed of light
  • Planck length
• Sets of questions are "decidable" if an algorithm correctly returns true or false for all questions in the set.
• Undecidable problems exist where is no possible algorithm.
• Computers cannot solve undecidable problems.
• Examples of undecidable problems:
  • Determining if an arbitrary program with finite input will finish running.
  • Deciding whether a mathematical expression is zero.
  • Determining if two grammars describe the same language.
  • Determining if a particular kind of equation has a solution.

Algorithms

• The algorithm must be Unambiguous, Executable, and Terminating.
• An algorithm is a step-by-step process to solve a problem.
• Algorithms sequence of steps.
• Unambiguous algorithms require no "assumptions" to execute.
• Unambiguous algorithms use precise instructions
• Executable algorithms can be carried out in practice.
• Terminating algorithms eventually come to an end, stop, or halt.
• Pseudocode is an informal high-level and human-readable description, intended for humans, not machines.
• Most algorithms can use these simple structures: Sequences, Selections, and Loops

Sequences

• Sequences are series of actions completed in a specific order.

Selections

• Selections ask a question to figure out the next path, known as “if” statements.

Loops

• Loops repeat an action until a certain condition is met.

Evaluating Algorithms

• Evaluate if an algorithm is "good".
• Compare algorithms that have the same inputs and results.
• Check if results are the same or are they equivalent.

Phone Book Algorithm Example

• Use an algorithm to look up a person's phone number in a phone book.
• Linear Search is an example, where you start on the first page and check each page.
• Binary Search is another example, where you start halfway through and throw away half that does not contain the name and repeat.

Correctness

• Check If the algorithm can be executed without error for all cases.
• Check if the algorithm guaranteed to terminate for all inputs.

Time Complexity

• Normally measures worst-case scenario of time complexity.
• It measures many basic steps.

Programming

• Programming involves converting an algorithm into precise instructions computers can read.
• Programming is the process of creating an executable computer program.
• Programming is also is known as coding or implementation.
• Machine instructions use low-level commands.
• Assembly code is a human-readable form of machine instructions.

Programming Languages:

• Artificial languages give instructions people can understand.
• Examples include JAVA, VBA, Python, C, C++, C#, FORTRAN, COBOL, R, PHP.
• Programs are written in compiled languages.
• The programs are translated into machine code using a compiler.
• Java and C use compiled programming languages.
• In interpreted languages an interpreter is used, such as with Ruby and Python.
• Algorithms serve as the general procedure, while programs are the specific instructions.