A Bit of Computer Science
In this section, you’ll learn some fundamental computer science concepts that will help you when solving problems with a bit more complexity than just simple web serving. You get to try on your engineering hat and solve some computational problems.
Step 1: A Very Brief Introduction to Computer Science
In the world of programming, there’s a difference between solving a problem the brute force way and solving a problem WELL. We touched on the first layer of this when we covered basic object-oriented programming and how you should break apart your code into well-organized chunks.If you assume those lessons were all about learning how to write good code, these next few lessons are going to be about training yourself to work out the best code to write – the most elegant solution to the problem at hand. It becomes particularly important whenever you start working with large data sets.
Some problems require you to use tools beyond just arrays and iterators. You’re going to build chess and it’s not fundamentally difficult (it’s just a rules-based game after all) but there are some tricks that you’ll want to use to help you solve it. There’s no sense reinventing the wheel when others have already worked out good methods for solving certain types of problems.
Points to Ponder
Look through these now and then use them to test yourself after doing the tasks
- What is an algorithm?
- What is pseudo-code?
Your Tasks
1. Look through David Malan’s Introduction to Algorithms What’s an algorithm? (http://ed.ted.com/lessons/your-brain-can-solve-algorithms-david-j-malan)
2. Watch YouTube video What is an Algorithm? (https://www.youtube.com/watch?v=87uzB76-C0c). Start at 4.00. This provides a more structured look at solving problems using algorithms.
An algorithm is a sequence of unambiguous instructions for solving a computational problem.
Additional Resources
- Read Wikipedia’s Computer Science (https://en.wikipedia.org/wiki/Computer_science)
- Read Wikipedia’s Algorithm (https://en.wikipedia.org/wiki/Algorithm)
Step 2: Recursive Methods
Learn how making a function call itself can be helpful for making big problems into smaller problems
Recursion is the idea that a function calls itself. It’s used to take a big problem and start breaking it down into smaller and smaller pieces (“Divide and Conquer“) and continuing to feed their solutions back into the original function until some sort of answer is achieved and the whole chain unwinds.
See Wikipedia’s Divide and conquer algorithms (https://en.wikipedia.org/wiki/Divide_and_conquer_algorithms)
An extract:
In computer science, divide and conquer (D&C) is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
There’s also a right and wrong way to use recursion. The fact is, any problem you can solve recursively you can also solve using iterators. If you find yourself saying “why didn’t I just use a while loop here?” then you probably should have. You won’t often end up using a recursive solution to a problem, but you should get a feel for when it might be a good idea. Some problems also break down into far too many pieces and totally overwhelm your computer’s memory. There’s a balance.
Points to Ponder
Look through these now and then use them to test yourself after doing the tasks
- Why is recursion a useful technique for solving a big problem?
- What are the limitations of using recursive solutions?
- What types of problems are more suited for simple loops than recursion?
- What is meant by “recursive depth?”
- What is a “stack overflow” (the concept, not the website)?
- Why is that relevent to a recursive problem?
Your Tasks
1. Read Dan Nguyen’s The Bastard’s Book of Ruby Chapter on Recursion (http://ruby.bastardsbook.com/chapters/recursion/)
2. Watch Joshua Cheek’s Ruby Kickstart Introduction to Recursion (https://vimeo.com/24716767). Watch at least up to 17.45.
3. Read the Implementation Issues section of the Wikipedia article Divide and conquer algorithms (https://en.wikipedia.org/wiki/Divide_and_conquer_algorithms#Implementation_issues) to get an overview of some of the limitations of recursion.
Test Yourself
- Complete the Ruby Computer Science – Recursion Quiz from CodeQuizzes (http://www.codequizzes.com/computer-science/recursion)
Additional Resources
- Read What is Ruby recursion and how does it work? (https://stackoverflow.com/questions/6418017/what-is-ruby-recursion-and-how-does-it-work)
- Read 4.1. Efficient Recursion (http://webdocs.cs.ualberta.ca/~holte/T26/efficient-rec.html)
- Read Natasha the Robot’s Inception All Over Again: Recursion, Factorials, And Fibonacci In Ruby (http://natashatherobot.com/recursion-factorials-fibonacci-ruby/)
- Read Functional Programming Techniques with Ruby: Part III (http://www.sitepoint.com/functional-programming-techniques-with-ruby-part-iii/). The first part covers recursion.
Project: Recursion
Introductory Task: Fibonacci
The Fibonacci Sequence, (See Wikipedia’s Fibonacci number (https://en.wikipedia.org/wiki/Fibonacci_number)) which sums each number with the one before it, is a great example of a problem that can be solved recursively.
Your Tasks
1. Write a method #fibs which takes a number and returns that many members of the fibonacci sequence. Use iteration for this solution.
2. Now write another method #fibs_rec which solves the same problem recursively. This can be done in just 3 lines.
Project: Merge Sort
We spent some time early on dealing with sorting (ie. bubble sort). Now it’s time to take another look at sorting with Merge Sort (https://en.wikipedia.org/wiki/Merge_sort) a type of sort that lends itself well to recursion and can be much faster than bubble sort on the right data sets. You’ll build a method which sorts a given array but uses a “merge sort” method for doing so.
Background Viewing
The first step is to actually understand what the merge sort algorithm is doing:
1. Watch the YouTube video Merge Sort (https://www.youtube.com/watch?v=EeQ8pwjQxTM) from Harvard’s CS50x course.
Published on 26 Sep 2012
2. Watch the YouTube video Merge sort – how it works (1) (https://www.youtube.com/watch?v=OAsokGNa18k) fot a more formal look at the concepts,
Merge sort is based on the Divide-and-Conquer design strategy.
The merge step of merge sort constructs a sorted array by merging two smaller sorted arrays, in linear time.
Your Tasks
1. Build a method #merge_sort that takes in an array and returns a sorted array, using a recursive merge sort methodology.
2. Tips:
- Think about what the base case is and what behavior is happening again and again and can actually be delegated to someone else (ie. that same method!).
- It may be helpful to check out the background videos again if you don’t quite understand what should be going on.
Additional Resources
- Look at Merge Sort (http://www.sorting-algorithms.com/merge-sort)
- For further attempts at recursion try the first 5 problems at Project Euler’s Problem Archives (https://projecteuler.net/archives)
Step 3: Common Data Structures and Algorithms
Learn why we use different data structures to handle our data and some classic algorithms for searching through them to help solve problems
The basic idea of a data structure is to store data in a way that meets the needs of your particular application. You might be inclined to store a particular kind data in one giant array, but it would be rather time consuming to locate a specific value if you had a significant number and depth of items. So you need to look to other options.
Depending on the application, there are a batch of other basic data structures available to help you out. The differences between them typically have to do with trade-offs between how long it takes to first populate the structure, how long it takes to add or find elements, and how large the structure is in memory.
You should be able to identify and solve certain problems where plain old Arrays, Hashes and Sets are not appropriate. New structures and strategies will be particularly relevant, for instance, when you’re trying to search through a large batch of data for a particular value or plan out a strategy several moves in advance.
You’ve already had a brief introduction to algorithms over some of the other lessons and you even got to write your own Merge Sort algorithm in the last project. You’ll find that sorting algorithms are quite common. Another major area for algorithms is in search, where milliseconds count. When you’re searching through enormous troves of data, the quality of your search algorithm is incredibly important. Traversing a data tree looking for a particular element is a related problem that’s common in data intensive applications.
Luckily for you, these complex algorithmic problems have all been solved many times in the past. Understanding how they are solved will give you some great tools to apply to other (similar) problems on your own. Algorithms are really just ways of solving problems systematically. In this brief introduction, we’ll focus on a couple of algorithms that you may run into when coding on your own – breadth-first-search and depth-first-search.
Points to Ponder
Look through these now and then use them to test yourself after doing the tasks
- What is a data structure?
- What is a stack?
- What is a queue?
- What’s the difference between a stack and a queue?
- What is a stack useful for?
- What is a queue useful for?
- What’s the best way to implement stacks and queues in Ruby (hint: think simple)?
- Why bother having many different search algorithms?
- What is breadth-first-search (BFS)?
- What is depth-first-search (DFS)?
- What situations would you want to use BFS?
- What situations would you want to use DFS instead?
- When would BFS be impractical?
Your Tasks
1. Look at Wikipedia‘s article on Data structure (https://en.wikipedia.org/wiki/Data_structure) for a high level overview.
2. Watch the YouTube video Stacks and queues: the basics (https://www.youtube.com/watch?v=6QS_Cup1YoI)
What are stacks and queues? When are they useful?
Graph ADT how-to – performing a:
– Breadth-first Traversal
– Depth-first Traversal
Additional Resources
- Look at Khan Academy’s great Algorithms course (https://www.khanacademy.org/computing/computer-science/algorithms)
- Look at Coursera‘s more advanced algorithms course Algorithms: design and Analysis (https://class.coursera.org/algo-004/lecture/preview)
- Look at Mike Bostock’s Visualizing Algorithms (http://bost.ocks.org/mike/algorithms/)
- Look at Coursera’s FREE course on algorithms Algorithms: Design and Analysis, Part 1 (https://www.coursera.org/course/algo)
- Look at Udacity’s FREE course on algorithms Intro to Algorithms – Social Network Analysis (https://www.udacity.com/course/intro-to-algorithms–cs215)
- Look at Ilya Grigorik’s Ruby Algorithms: Sorting, Trie & Heaps (https://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/)
Project: Data Structures and Algorithms
Project 1: Searching Binary Trees
You learned about binary search trees (https://en.wikipedia.org/wiki/Binary_search_tree) where you take a group of data items and turn them into a tree full of nodes where each left node is “lower” than each right node. The tree starts with the “root node” and any node with no children is called a “leaf node”.
You also learned about tree search algorithms like breadth-first-search and depth-first-search. You learned that BFS is best used to find the optimum solution but can take a very long time (impractically long for broad and deep data sets) while DFS is often much faster but will give you the FIRST solution, not necessarily the best. Here you’ll get a chance to implement both.
Your Tasks
You’ll build a simple binary tree data structure from some arbitrary input and also the “crawler” function that will locate data inside of it.
1. Build a class Node. It should have a value that it stores and also links to its parent and children (if they exist). Build getters and setters for it (ie. parent node, child node(s)).
2. Write a method build_tree which takes an array of data (ie. [1, 7, 4, 23, 8, 9, 4, 3, 5, 7, 9, 67, 6345, 324]) and turns it into a binary tree full of Node objects appropriately placed. Start by assuming the array you get is sorted.
3. Now refactor your build_tree to handle data that isn’t presorted and cannot be easily sorted prior to building the tree. You’ll need to figure out how to add a node for each of the possible cases (ie. if it’s a leaf versus in the middle somewhere).
4. Write a simple script that runs build_tree so you can test it out.
5. Build a method breadth_first_search which takes a target value and returns the node at which it is located using the breadth first search technique. Tip: You will want to use an array acting as a queue to keep track of all the child nodes that you have yet to search and to add new ones to the list (as you saw in the video Graph Traversals :: Depth first search (DFS) & Breadth First Search (BFS) Algorithms (see above). If the target node value is not located, return nil.Build a method depth_first_search which returns the node at which the target value is located using the depth first search technique. Use an array acting as a stack to do this.
6. Next, build a new method dfs_rec which runs a depth first search as before but this time, instead of using a stack, make this method recursive.
7. Tips:
- You can think of the
dfs_recmethod as a little robot that crawls down the tree, checking if a node is the correct node and spawning other little robots to keep searching the tree. No robot is allowed to turn on, though, until all the robots to its left have finished their task.
- The method will need to take in both the target value and the current node to compare against.
Project 2: Knight’s Travails
A knight in chess can move to any square on the standard 8×8 chess board from any other square on the board, given enough turns. See this animation (https://upload.wikimedia.org/wikipedia/commons/c/ca/Knights-Tour-Animation.gif). Its basic move is two steps forward and one step to the side. It can face any direction.
All the possible places you can end up after one move look like this:
Your Tasks
Your task is to build a function knight_moves that shows the simplest possible way to get from one square to another by outputting all squares the knight will stop on along the way.
You can think of the board as having 2-dimensional coordinates. Your function would therefore look like:
knight_moves([0,0],[1,2]) == [[0,0],[1,2]]knight_moves([0,0],[3,3]) == [[0,0],[1,2],[3,3]]knight_moves([3,3],[0,0]) == [[3,3],[1,2],[0,0]]
Put together a script that creates a game board and a knight.
1. Treat all possible moves the knight could make as children in a tree. Don’t allow any moves to go off the board.
- Decide which search algorithm is best to use for this case. Hint: one of them could be a potentially infinite series.
- Use the chosen search algorithm to find the shortest path between the starting square (or node) and the ending square. Output what that full path looks like, ie.:
> knight_moves([3,3],[4,3]) You made it in 3 moves! Here's your path: [3,3] [4,5] [2,4] [4,3]
Additional Resources
- Watch the YouTube video 3. B-Trees from Coursera (https://www.youtube.com/watch?v=pJ6aeg8x1Ig)
Video from Coursera – Princeton University – Course: Algorithms, Part I