Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Computer Science the Fundamentals (or some of t...

Computer Science the Fundamentals (or some of them at least)

Justin Yost

April 07, 2017
Tweet

More Decks by Justin Yost

Other Decks in Programming

Transcript

  1. Computer Science the Fundamentals (or some of them at least)

    Justin Yost Senior Software Engineer Wirecutter 1
  2. Computer Science • The formal field of study towards approaching

    computers, sometimes this is using, designing and writing software for those computers. 2
  3. What do you need to know? Data Structures, Algorithms, Basic

    Cryptography, Search Algorithms, Big O Notation, P vs. NP, Statistics, Theory of Automata, Boolean Logic, Language Theory, Programming Paradigms, Hardware Design, Complier Design, Software Engineering and more... 3
  4. Highlights • Data Structures • Algorithms • Big O Notation

    • P vs. NP • Programming Paradigms • Turing Completeness 5
  5. Character • Single symbol or glyph • Different encodings means

    this character may be different lengths • C style char is 1 byte (most common systems do this) • Full unicode requires 21 bits to store a single code point (ie a single symbol) 8
  6. Floating Point Integers • Finite numbers with a sign •

    Example: binary32, binary with 8 bits, stores values up to ~3.402823 × 10^38 • Because of math, it has precision issues at certain points • But smaller storage for number values 9
  7. Integer • Signed and Unsigned • Always precise • Short

    version is the 1 to 1, binary representation of a number, no math needed 10
  8. Enum • Data type where you predefine a limited set

    of possible values • Example: Enum for Credit Card Types, MC, Visa, Amex, etc 11
  9. Advanced Data Structures • These are built using the others

    • Typically using software implementations as opposed to hardware implementations • Some are provided by the language, some by a framework, some in other ways • These are useful for particular scenarios and typically aren't general purpose 12
  10. Linked List • A series of nodes where each node

    contains a value field and a link to the next node • Used to represent graphs and trees, think a series of GPS coordinates that show a path walked for a map • Linked Lists can be more complicated, doubly linked lists, circular linked lists • Commonly used to represent other more complex data structures 13
  11. 14

  12. Array • A series of elements defined by an index

    • Most arrays have fast retrieval by index (1 operation), slow to search (scan whole array) 15
  13. Hash Table • Associative array, where elements are indexed by

    a (sorta) unique key • Value is taken, a hash function is used, then value is stored at the index in the array equal to the hash output • Searching for a value is fast (1 operation), Searching for an index is fast (1 operation), Insert and Delete is generally fast 16
  14. Hash Function? • A value is converted to some different

    representation of that value • This operation is one way • Most hash functions have collisions, ie certain multiple values will produce identical hash outputs • md5, sha, etc are hash functions 17
  15. 19

  16. Queue • A collection where the order of items in

    the collection stays the same • Think a line for a grocery store • Common queue types - FIFO, LIFO 20
  17. Stack • Custom collection similar to a queue • Only

    two operations - push and pop (sometimes peek) • Think a Pez dispenser • Basically a LIFO Queue 21
  18. Quicksort • Common fast sorting algorithm • Divides a collection

    along a pivot • Puts everything higher than the pivot above the pivot, everything lower than the pivot, below • Selects a new pivot and repeat • Developed in 1959, still used today • No knowledge of anything, this is your algorithm 23
  19. 24

  20. Bubble Sort • Start at the beginning • Compare the

    two values • If not sorted, swap the items • Go to the next position and repeat • Repeat process through the list until items sorted, ie no swaps occur • Super easy to implement 25
  21. 26

  22. Depth First Search • Search a tree by going down

    the nodes first • Solving a maze (where there is only one path) 27
  23. 28

  24. Breadth First Search • Search a tree by going across

    the nodes first • Shortest path searches between two nodes 29
  25. 30

  26. A* Search • Path finding algorithm that optimizes for certain

    solutions (shortest distance, etc) • Used in games to go from x to y, when you can't see the path 31
  27. Dijkstra's Algorithm • Path finding algorithm, typically used to produce

    a shortest path tree • For a given source find the shortest path to every other node • For a given source find the shortest path to a destination node • Used in networking algorithms, variations used in Google Maps, AI research, etc 32
  28. Big O Notation • The abstract number of operations required

    to complete a task • Short version: What's the most complex part of a piece of software and what does that look like when we add more data 33
  29. Big O - Informal Definition • If f(x) is a

    sum of several terms, if there is one with largest growth rate, it can be kept, and all others omitted. • If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) can be omitted. 34
  30. Big O of Searches • Quicksort - Average Case -

    O(n log n) • Bubble sort - Average Case - O(n^2) 35
  31. 36

  32. Quick and Dirty Calculation • Count number of loops performed

    given an input • How quickly does the number of loops performed increase compared to the input of data increase 37
  33. P vs. NP • Big massive unsolved problem in Computer

    Science • Also means today some problems are just too hard/slow (in general) today 38
  34. What is P • P means a problem that is

    solvable in polynomial time • O(n^k) (where k is constant) • This doesn't mean these are easy or fast to solve 39
  35. NP • Non-deterministic Polynomial time to solve • O(n^n) •

    P time to verify the answer • NP time to calculate the answer 40
  36. NP Complete • Knapsack, Traveling Salesman, Graph Coloring • One

    solution to NP Complete problems works for others • Mostly a mathy subset of NP problems 41
  37. P vs. NP • Can we can prove (write an

    algorithm) that solves NP problems in P time • If so lots of problems become way faster to solve especially for graph theory 42
  38. Imperative • Side effects allowed • Describe what the software

    should do • ie. PHP, single file, no functions 44
  39. Procedural • Step up of Imperative • Software is grouped

    into common blocks that can be called procedurally • ie. PHP with functions 45
  40. Declarative • Logic is expressed without describing the control of

    operations • Software describe what needs to happen not the how it occurs • Side effects do not happen • ie. Haskell, regular expressions 46
  41. Functional • Software uses mathematical functions to express the solution

    • Based upon lambda calculus (basically the math that proves computers work) • ie. Erlang, some parts of PHP has this (array_map) 47
  42. Object Oriented • Objects have data and operations to perform

    on that data • Probably what you do every day • ie. PHP (with classes), Java, C#, Swift, Ruby, etc 48
  43. Turing Machine • An abstract machine that manipulates symbols on

    a strip of tape according to a table of rules. 49
  44. Turning Completeness • The rules (software, hardware, etc) is Turing

    complete if it can be used to stimulate any other single-taped Turing complete machine. 50
  45. Citations • Linked List Image - By Lasindi - Own

    work, Public Domain, https://commons.wikimedia.org/w/index.php? curid=2245162 • Binary Tree Image - By Derrick Coetzee - Own work, Public Domain, https://commons.wikimedia.org/w/index.php? curid=488419 • Quicksort Animation - By en:User:RolandH, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php? curid=1965827 • Bubblesort Animation - By Swfung8 - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php? curid=14953478 • Depth First Search Image - By Alexander Drichel - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/ index.php?curid=3791979 • Breadth First Search - By Alexander Drichel - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php? curid=3786735 • Big O Notation Chart - By Cmglee - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php? curid=50321072 51