Computer Science: The Good Parts (2016)

Slides presented at ThatConference 2016

Transcript

2. Computer Science: The Good Parts @jeffcohen
3. The Good Parts Data Structures Algorithms Computational Thinking Culture Complexity
5. A data structure is a way to organize data. Different data structures exist for a reason. Data Structures Algorithms List Array Hash Tree Graph
6. Data Structures Algorithms List Array Hash Tree Graph 2 5 1 9 v
7. Data Structures Algorithms List Array Hash Tree Graph 2 5 1 9 a a[0] a[1] a[2] a[3]
8. Data Structures Algorithms List Array Hash Tree Graph h purple color baseball sport cookies fruit
9. Data Structures Algorithms List Array Hash Tree Graph
10. Data Structures Algorithms List Array Hash Tree Graph h purple color baseball sport cookies fruit
11. Jeff Alice Bob Amy Dave Data Structures Algorithms List Array Hash Tree Graph
12. Jeff Alice Bob Amy Dave Data Structures Algorithms List Array Hash Tree Graph
14. Data Structures Algorithms • Who's status updates would I like to see? • What should I buy? • What advertisement would influence my behavior the most right now? • I'm bored. How do I get to the pool? • Our website crashed. How do we get our airplane schedule back to normal?
15. Dijkstra's Algorithm Traveling Salesman Problem Data Structures Algorithms Graph Theory
16. Jeff Alice Bob Amy Dave Data Structures Algorithms List Array Hash Tree Graph
17. Culture: Knowing vs. Understanding
18. Select the data structure that resembles the real-life problem that you’re trying to solve. Data Structures Algorithms
19. An algorithm computes a result by operating upon a data structure. Data Structures Algorithms
20. Data Structures Algorithms
22. Margaret Hamilton Source code of the Apollo Guidance Computer
23. An algorithm computes a result by operating upon a data structure. The complexity of an algorithm depends upon the data structure it is forced to work with. Complexity
24. O( ) O(n) O(log n) O(n^2) Complexity: "Big O" Notation
25. def search(people, name_to_find) for person in people if person.name == name_to_find return person end end return nil end Complexity: "Big O" Notation
26. 0 100 200 300 O(n) Complexity: "Big O" Notation
27. def search(people, name_to_find, from = 0, to = nil) to ||= people.count - 1 mid = (from + to) / 2 if name_to_find < people[mid].name search(people, value, from, mid-1) elsif name_to_find > people[mid].name search(people, value, mid+1, to) else people[mid] end end Complexity: "Big O" Notation
28. O(n) 0 100 200 300 O(n) O(log n) Complexity: "Big O" Notation
29. def calculate_total(customer) total = 0 for order in customer.orders do for item in order.line_items do total += item.price end end total end Complexity: "Big O" Notation
30. O(n2) def calculate_total(customer) total = 0 customer.orders.each do |order| order.line_items.each do |item| total += item.price end end total end 0 100 200 300
31. The Test Kitchen
32. http://blog.atom.io/
34. Alan Turing
35. Computer science is not computer programming. It’s the pursuit of understanding how humans think and solve problems. Computational Thinking
37. • Break problems into small pieces. • Focus on one thing at a time. • Follow the recipe of a proof. • Make the invisible visible. • Do the simplest thing that can possibly work. • Describe your problem out loud (rubber ducky!) • There's no problem that another level of indirection can't solve. :-)
 Computational Thinking
38. Grace Hopper
40. You don't manage people; you manage things.
 
 You lead people.
41. Humans are allergic to change. They love to say, "We've always done it this way." I try to fight that.
 
 That's why I have a clock on my wall that runs counter- clockwise.
42. A ship in port is safe; but that is not what ships are built for. Sail out to sea and do new things.
43. Stand on Shoulders
44. Applied Science! • Watch out for nested loops. • Know how to use different data structures. • Solve a problem from first principles. • Try to classify method “complexity” (Big O). • Read the source of code you use. • Learn how to benchmark your code. • Join the tradition of doing something meaningful!
 
 

45. @jeffcohen Jeffrey Cohen csthegoodparts.com Computer Science: The Good Parts