yjohn/intro-to-computer-science

This is a repo for the gentle introduction to Computer Science for our students at Code Your Future in Glasgow.

Introduction to Computer Science

This is a repo for the gentle introduction to Computer Science for our students at Code Your Future in Glasgow.

Things to do before the class

• Set up an account at Hackerrank
• Watch the video Work at Google — Example Coding/Engineering Interview
• You are given an array of numbers: [32, 16, 13, 9, 1, 99, 34, 64]. Try to think in how many ways you can sort its elements. We are not interested here in using any programming language, just plain English. The following videos may help you to understand the idea behind the pseudocode:
  • Algorithms in pseudocode and flow diagrams
  • 5 Minutes to Code: Programming Basics "Pseudocode"
  • What's an algorithm? - David J. Malan

Algorithms

What is an algorithm? (5 min)

Intuitively speaking, an algorithm is a step-by-step procedure (a “recipe”) for performing a task (of solving a problem). [1]

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. [10]

Do we REALLY need to learn about algorithms and data structures? (5 min)

Yes and no.

Excercise (10 mins)

How can we create an algorithm to make a tea?

Excercise (10 mins)

Solve Simple Array Sum on Hackerrank

Everyday problems that need good algorithms (20 min)

• Navigation - find the shortest path from A to B, say using Google Maps to get the best route from Edinburgh to Glasgow. Visualise the search with Dijkstra algorithm . Also check route finding.

• Online banking relies on public key cryptography - how to be sure that nobody can see your communication with the bank.
  How would you send a password over insecure network?
  Padlock and box exchange analogy.
  Also, watch RSA encryption: Step 1 on Khan Academy

• Google as a search engine
  Before Google, search engines were not really reliable (they couldn't even find themselves!)

  Our main goal is to improve the quality of web search engines... However, the Web of 1997 is quite different... "Junk results" often wash out any results that a user is interested in. In fact, as of November 1997, only one of the top four commercial search engines finds itself (returns its own search page in response to its name in the top ten results). One of the main causes of this problem is that the number of documents in the indices has been increasing by many orders of magnitude, but the user's ability to look at documents has not. People are still only willing to look at the first few tens of results.(how often do you go to page 2) Because of this, as the collection size grows, we need tools that have very high precision (number of relevant documents returned, say in the top tens of results). Indeed, we want our notion of "relevant" to only include the very best documents since there may be tens of thousands of slightly relevant documents. This very high precision is important even at the expense of recall (the total number of relevant documents the system is able to return). [2]

• Seaching for a book in the library catalogue DiscoverEd
  
  

• Detecting spam emails - classification problem

• Postcode recognition
  Ever wonder how mail is sorted? @1:00

  

  

  Automatic Number Plate Recognition

• Real time face recognition on the airports
  Is there a cat on this image?
  
  And now?
  
  How about now?
  
  HEX to Binary

• Computer graphics

• Amazon recommendation system

Excercise (15 mins)

You are given an array of numbers: [32, 16, 13, 9, 1, 99, 34, 64]. In how many ways we can sort its elements? We are not interested here in using any programming language, just plain English.

Why do we need (better) algorithms? (10 min)

• drives innovation - new algorithm may create a new business opportunity - Blackford Analysis Ltd
• there are a lot of problems that still need to be solved, so chellange and fun
• helps improve the performance - competition! Matrix multiplication algorithm
• computers are stupid, so they need exact instructions

Excercise (15 mins)

Arrays - DS on Hackerrank

When algorithms go wrong

• TripAdvisor

  My first project at TripAdvisor was to add new sort options to the web page that listed all the hotels in a city. It was a quick task—just enough to become familiar with the codebase—and I was able to get it done and pushed to production in my first week. Shortly thereafter, I was in my manager’s office for our first one-on-one meeting, and I watched as he clicked on the hotel listings for Paris, selected the new sort option, and waited. And waited. And waited. It took nearly two hours for the page to load. Well, it was probably closer to two minutes, (...) Later that night—much later—I figured out that my fancy new code was making two database calls every time it compared hotels during the sorting process. It takes on the order of n log n comparisons to sort n items, so for Paris, which has roughly 2,000 hotels, that works out to roughly 40,000 database calls for a single page load. I might not have melted that day, but our database server nearly did. [4]

• appending the DOM

• Pokemon app

• Tay (bot)

  Microsoft had not given the bot an understanding of inappropriate behavior.(...) Because these tweets mentioned its own account (@TayandYou) in the process, they appeared in the feeds of 200,000+ Twitter followers, causing annoyance to some.

• T-shirt company called Solid Gold Bomb

  Fowler had set up an algorithm to upload thousands upon thousands of T-shirt designs to his online stores. The designs were based on the infamous “keep calm and carry on” catchphrase, a slogan which was originally dreamt up as a way of preserving morale in the event of a Nazi invasion of Britain. Fowler had decided to “parody” it by getting a computer programme to come up with random variations such as “keep calm and dance on” or “keep calm and play football”.

• Google Apologizes For Tagging Photos Of Black People As ‘Gorillas’

  When Jacky Alciné checked his Google Photos app earlier this week, he noticed it labeled photos of himself and a friend, both black, as “gorillas.”

Excercise (15 mins)

[TODO] Factorial or Fibonnacci function.

What are characteristics of a good algorithm? (5 min)

• efficient (speed and space)
• correct
• simple

How do we evaluate algoritms? (10 min)

The running time of a program depends on a number of factors such as:

• The input given to the program (input size example)
• The running time of the algorithm on which the program is based.
• The quality of the implementation and the quality of the code generated by the compiler
• The machine used to execute the program

Big O notation

Also check the StackOverFlow

Functions used in complexity analysis

https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation

Abstract Data Types

1. What is a data structure?

Data structure is a systematic way of organising data and making it accessible in certain ways. [1]

Check the basic data types on FreeCodeCamp

Stack

Example JS implementation
Maximum Element on Hackerrank

Queue

Example JS implementation

Hackerrank

Sorting

Sorting algorithm is an algorithm that puts elements of a list in a certain order, i.e. numerical or alphabetical. Check sort function in JavaScript.

Sorting algorithms animation

Insertion sort

(sorting cards)

for i = 1 to length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

Insertion sort JS code

Selection sort

Selection sort on Khan Academy

SelectionSort(A)
// GOAL: place the elements of A in ascending order
1  n := length[A]
2  for i := 1 to n
3     // GOAL: place the correct number in A[i]
4     j := FindIndexOfSmallest( A, i, n )
5     swap A[i] with A[j]
      // L.I. A[1..i] the i smallest numbers sorted
6  end-for
7  end-procedure


FindIndexOfSmallest( A, i, n )
// GOAL: return j in the range [i,n] such 
//       that A[j]<=A[k] for all k in range [i,n]
1  smallestAt := i ;
2  for j := (i+1) to n
3     if ( A[j] < A[smallestAt] ) smallestAt := j
      // L.I. A[smallestAt] smallest among A[i..j]
4  end-for
5  return smallestAt
6  end-procedure

Merge sort

An example of Divide and conquer algorithm

Visualisation of the merge sort

By Swfung8 - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14961648

Quicksort

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p – 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo - 1    
    for j := lo to hi - 1 do
        if A[j] ≤ pivot then
            i := i + 1
            if A[j] < pivot then
                swap A[i] with A[j]
    if A[hi] < A[i + 1] then
        swap A[i + 1] with A[hi]
    return i + 1

Visualise

Comparison

Hackerrank

Searching

Hackerrank

Resources

1. Spam classification example by Andrew Ng

Bibliography

1. http://www.inf.ed.ac.uk/teaching/courses/inf2b/algnotes/note01.pdf
2. The Anatomy of a Large-Scale Hypertextual Web Search Engine by Sergey Brin and Lawrence Page
3. The PageRank Citation Ranking: Bringing Order to the Web
4. Hello, Startup: A Programmer's Guide to Building Products, Technologies, and Teams
5. What Will Happen When Your Company’s Algorithms Go Wrong?
6. Google Apologizes For Tagging Photos Of Black People As ‘Gorillas’
7. Google apologises for Photos app's racist blunder
8. Sorting Algorithm at Wikipedia
9. Sorting Algorithms at Brilliant
10. Introduction to Algorithms by Thomas H. Cormen
11. Selection sort pseudocode from the University of Miami
12. Big Oh notation on StackOverflow
13. 10 Common Data Structures Explained with Videos + Exercises