Page 1

• Computer programs are the instructions we give to machines for them to solve certain problems.

• Computer programs are important because:

  • They speed up the process of calculations

  • They can help us avoid errors when calculating by hand

• Basic components of a computer and the Internet:

  • Input, processing, output

• Programming languages: C++, Javascript

• Pseudo Code:

  • Informal way of programming; expresses programmer needs but produces codes not recognized by computers

  • General rules:

    • Every line is a separate sentence

    • Every sentence is a single process. No "and" should be used

  • Examples:

    • a= a+b (output = a)

    • X and y are two variables used inside the following PC:

      • If x>y

      • Then output=x

      • Else output= y

• Basic programming structures:

  1. Function

Page 2

• Input

• Variable

• Declare a variable

• Variable and input

• Processing

• If ... then ... (conditional), For.. (loop) and while...(loop)

Page 3

• For ... (loop) & While... (loop)

• Output

• Print

• Nesting

  • Having one process inside another

• Add Comments

  • Parts of the program that aren't executed

  • Delphi uses "//"

  • JavaScript uses "//"

  • C++ uses "//"

  • HTML uses "<!--...-->"

  • CSS uses "/* ... */"

  • R uses "#"

  • Python uses "#" and """ "

• Function

• Procedure

  • Has an output

  • Does not have an output

• Quiz 4: What does the following function do?

  • Increase x by 10

  • For i=1 to 10 do x = x +1

  • Return x

Page 4

• Quiz 10

  1. Computer Programming - instructions we give machines so they can help us solve problems

  2. Which of the following is not a programming language:

     • a. R

     • b. C#

     • c. C

     • d. Router

  3. What does the following function do?

     • x = x^x

     • output = x

     • The function assigns the value of x^x to x

  4. What does the following function do?

     • n=386

     • For i = 1 to n do x = x + n

     • Return x

     • increase the value of x by n*n

  5. What does the following function do?

     • While n < 100 do n=n + 0.001

     • Return n

     • Add 0.001 to n until the value of n is equal to or larger than 100, whichever comes first

  6. What does the variable n in the following function do?

     • n = 0

     • While x > 0 do begin x = x - 1 n = n + 1 end

     • Return x

     • count the number of times this loop is performed

  7. What does the following function do?

     • If x = 3 then do x = x + y

     • Return x

     • Add y to x if x is 3

  8. What does the following function do?

     • If x = y then do x = x*2

     • Else do x = y*2

     • Return x

     • If x and y are equal, assign the value of x*2 to x and return x; if x and y are different, assign the value of y*2 to x and return x

  9. What does the following function do?

     • For i = 1 to 10000 do For j = 1 to 10000 do n = i + j

     • Output = n

     • Assign the value of 10000 + 10000 to n, return n

  10. What does the following function do?

      • For i = 1 to 10000 do For j = 1 to 10000 do begin n = 1 Print n End

      • Print 100 million 1s

  11. What does the following function do?

      • For i = 1 to 10 do If x > 1 then do x = x + 1

      • Output = x

      • Increase the value of x by 10 if x is larger than 1

Page 5

• What does the following function do?

  • If Timer = n then For i = 1 to n do TimeCounter = n - i

  • Print TimeCounter

  • Count down

• What does the following function do?

  • For i = 1 to 10 do input = input + 1

  • For j = 1 to 10 do input = input +1

  • Output = input

  • Increase the value of input by 20

• What does the following function do?

  • x = 10

  • While x <> 0 do x = x - 1

  • If x = 0 then do x = 10

  • Return x

  • assign the value 10 to x

• Algorithm Analysis: Properties of Algorithms:

  • Problem Size

  • Time Complexity - The number of steps that the algorithm takes to solve a problem with a problem size of n.

  • Space Complexity - The computer memory needed for the algorithm to solve a problem with a problem size of n.

• Notations:

  • Different algorithms have different time and space complexity

  • These complexities can change according to the problem

• Three Notations: Page 8

  • Quick sort has a Big O of O(N2) in a worst case scenario

  • Quick sort has a Big O of O(NlogN) in a best case scenario

  • On the exam, when asked “What is the Big O of modern sorting algorithms?”

    • The answer is O(NlogN)

    • Concept of logarithms: If b = X^a, then a=logxb

  • Why does O(logN) not have the subscripted x?

  • Quick sort will be faster by selection luckiness, faster than merge sort

  • Merge sort has a Big O of O(NlogN) in a worst case scenario

  • Merge sort has a Big O of O(NlogN) in a best case scenario

  • Big O for Searching and Sorting

    • Big O for ___________ is _____________

    • Searching on an unsorted list; O(N)

    • Modern sorting algorithms; O(NlogN)

    • Searching on a sorted list; O(logN)

  • Is it always worth the effort to sort?

    • Assume we have 10 items on a list and we are looking up 1 number, is it worth sorting before searching?

    • Assume we have 10 items on a list and we are looking up 5 numbers, is it worth sorting before searching?

    • Assume we have 10 items on a list and we are looking up 10 numbers, is it worth sorting before searching?

  • To simplify the problem, which of the following is bigger? xN or NlogN+xlogN? O(N!)

  • Algorithms with a Big O of O(N!)

    • Optimization (e.g., traveling sales man)

  Page 9

  • In the worst case scenario, quick sort should be slower than merge sort. However, in real life sorting scenarios, quick sort can be faster than most other sorting methods, including merge sort.

  • Useful material: http://cs.stackexchange.com/questions/3/w

  • Compilation

    • O(1) e.g., assign a constant to a variable

    • O(logN) e.g., search on sorted list

    • O(N) e.g., search on unsorted list

    • O(NlogN) e.g., modern sorting algorithms

    • O(N2) e.g., a for-loop nested in another for-loop

    • O(N!) e.g., optimization, brute force algorithms

  • How would you draw these algorithms on a graph? Where would O(N3) be? What about O(N4)? O(N5)?

  • Big O Chart

    • Algorithm: Quick sort

    • Data structure: Array

    • Time complexity: Best - O(n log(n)), Average - O(n log(n)), Worst - O(n2)

    • Space complexity: Worst - O(n)

    • Algorithm: Merge sort

    • Data structure: Array

    • Time complexity: Best - O(n log(n)), Average - O(n log(n)), Worst - O(n log(n))

    • Space complexity: Worst - O(n)

    • Algorithm: Brute force

    • Time complexity: O(n!)

    • Optimization: O(n!)

    • Algorithm: Binary Search

    • Time complexity: Searching on a sorted list - O(log(n)), Searching on an unsorted list - O(n)

    • Modern Sorting algorithms: O(n log(n))

  Page 10

  • Big O on any algorithm will be the number of lines of code

  • When calculating, be sure to compare both X and N and you will most likely find that n log n +x log n

  • Searching on an unsorted list: xN - Slower sorting

  • Searching on a sorted list: N log n x Log n - Faster

  • n log n + x log n = total score

  Page 11

  • Quiz 11 | Algorithm Analysis I

    • What is the Big O of the following function? Assume a and b are constants. x = a + b - Big O (2)

    • What is the Big O of the following function? Assume i is a loop counter variable and n is a constant. For i = 1 to n do print i - Big O (n)

    • Which of the following about Big O is correct?

      • Big O is about how a function uses different variables to generate an outcome

      • Big O is about the complexity of a function

    • What is the Big O of a function that looks up a certain item on an unsorted list? (linear search) - O(n)

    • What is the Big O of merge sort in a worst case scenario? - O(NlogN)

    • What is the Big O of merge sort in a best case scenario? - O(NlogN)

    • What is the Big O of quick sort in a worst case scenario? - O(N^2)

    • What is the Big O of quick sort in a best case scenario? - O(NlogN)

    • What is the Big O of searching on a sorted list? - O(logN)

  • Quiz 12 | Algorithm Analysis II

    • Consider the concept of time to run an algorithm mentioned in this class. How long would it take to search once on an unsorted list with 10 items? - 10

    • Consider the concept of time to run an algorithm mentioned in this class. How long does it take to sort a list with 100 items? - 100*log100

    • Consider the concept of time to run an algorithm mentioned in this class. How long does it take to search on a sorted list with 1000 items? - log1000

    • Consider the concept of time to run an algorithm mentioned in this class. If we need to look up 10 items on an unsorted list with 100 items, how long would it take? - 1000

  Page 12

  • Consider the concept of time to run an algorithm mentioned in this class.

    • If we need to look up 10 items on a sorted list with 100 items, it would take 10 log 100.

  • Consider the concept of time to run an algorithm mentioned in this class.

    • If we need to look up 10 numbers on an unsorted list with 100 items, it would be worth it to sort the list.

  • Consider the concept of time to run an algorithm mentioned in this class.

    • If we need to look up 3 numbers on an unsorted list with 100 items, it would be worth it to sort the list.

  • What is the Big O for brute force cracking SSL/TLS encrypted messages? O(N!)

  • What is the Big O for optimization? O(N!)

  • Graphs For The Internet:

    • A graph of how items on the internet are connected to one another

    • Algorithm calculates how much older Bob is compared to Kate if Bob is older than Kate

      • a = Bob’s_age

      • b = Kate’s_age

      • c = 0

      • if a > b then Begin

        • c = a – b

        • print “Bob is” c “years older than Kate.”

      • Repeatedly reduce n forever

        • n = -2

        • b = -1

        • While n < b do

          • n = b + n

  • Importance of understanding graphs when examining the internet

    • Internet is a huge graph

    • E.g., How computers and devices are connected

    • E.g., How websites and other Internet services are connected

    • Make the Internet better

      • E.g., Calculate least cost for routing

      • E.g., Find out the most secure way to connect devices

  • Internet & Information Environment 12

  Page 13

  • Basic concepts of graphs

    • Node

    • Edge

    • Weighted Graph

    • Unweighted Graph

    • Directed Graph

    • Undirected Graph

  • Dijkstra’s Algorithm:

    • The Purpose is to Calculate the Shortest Route

  • Internet & Information Environment 13

  Page 14

  • pivot unvisited calculate d

  • 1 2 3 4 5 {1} {2 3 4 5} {1} 0 2 16 18 50

  • {2} {3 4 5} {1 2} 0 2 16 14 22

  • {4} {3 5} {1 2 4} 0 2 16 14 19

  • {3} {5} {1 2 3 4 } 0 2 16 14 19

  • {5} {} {1 2 3 4 5} 0 2 16 14 19

  • Internet & Information Environment 14

  Page 15

  • Quiz 13 | Graph Basics

  • 1. What is not a reason studying graphs is important?

    • Graphs help us understand how the Internet is connected.

    • Graphs help us find out the most reliable ways to connect a device to the Internet.

    • Graphs help us figure out the least costly route on the Internet.

    • Graphs help us understand how sorting algorithms work.

  • 2. A part of the following graph is marked out in RED. What would you call the red part? Edge

  • 3. A part of the following graph is marked out in RED. What would you call the red part? Node

  • Internet & Information Environment 15

  Page 16

  • 4. What would you call this graph? A Weighted Graph

  • 5. What would you call this graph? A Directed Graph

  • 6. Which one of the following choices is the shorted route between New Brunswick and Los Angeles in the following graph? New Brunswick → Chicago → L.A.

  • 7. What is shortest path in a graph?

    • The least total weight between the starting node and the ending node

  • Internet & Information Environment 16

  Page 17

  • 8. Observe the following graph. What is the shortest distance (i.e., the length of the shortest path) between node #5 and node #6?

  • Quiz 14 | Dijkstra’s Algorithm

  • 1. Consider the following graph. If we start from 4 and end at 5, when using dijkstra's algorithm to find shortest path, which node would be the first pivot? 4

  • 2. (Continued from the previous question) Which node should be the second pivot? 2

  • 3. (Continued from the previous question) Which node should be the third pivot? 3

  • Internet & Information Environment 17

  Page 18

  • 4. Consider the following graph. If we start from 3 and end at 8, when using dijkstra's algorithm to find shortest path, which node would be the first pivot? 3

  • 5. (Continued from the previous question) Which node should be the second pivot? 1 or 6

  • 6. Consider the following graph. If we start from 3 and end at 4, when using dijkstra's algorithm to find shortest path, which node would be the first pivot? 3

  • 7. (Continued from the previous question) Which node should be the second pivot? 1

  • 8. (Continued from the previous question) Which node(s) should be the third pivot? 5 AND 6 (Choose Both)

  • 9. (Continued from the previous question) Which node(s) should be the fourth pivot? 5 AND 6 (Choose Both)

  • 10.(Continued from the previous question) Which node should be the fifth pivot? 2

  • Internet & Information Environment 18

  Page 19

  • 11. (Continued from the previous question) What is the total weight of shortest path? 13

  • 12.What does Dijkstra's algorithm do?

    • It helps reduce the Big O of Internet routing algorithms from O(N!) to approximately O(NlogN).

  • For i=1 to 10 ft5v x=x+1 Print x

  • Why Ranking?

    • Business:

      • Client:

        • Google Page Rank

        • Reddit post/comment rank

        • Term Project 1: Ranking Search engines

    • Create ranking

      Page 21

      • PostRank PostTime - RedditStart log10(UpVote - DownVote) + if (UpVote - DownVote) >0 4500 = log10(UpVote - DownVote), if (UpVote - DownVote) = 0

      • PostTime - RedditStart log10 (UpVote - DownVote) if f(UpVote - DownVote) <0 4500

      • If UpVote > DownVote then time effect is positive

      • If UpVote = DownVote then time effect is o

      • If UpVote < DownVote then time effect is negative

      Page 22

      • Steps On How to Design Ranking Systems

      • Step 1: Feature selection

      • Step 2: Scoring

      Page 23

      • Exercises:

      • (1.) How would you design a post ranking algorithm to make reddit posts rank higher the more UpVotes they get?

      • (2.) How would you design a post ranking algorithm to make universities rank higher on a university’s list if they have a long history, have a lot of students, and have minimal negative views?

      • (3.) How would you design a post ranking algorithm to make universities rank higher on a university’s list if they have a long history, have a lot of students, and have minimal negative views?

      Page 24

      • Using Reddit Score = (log10(Up Votes - Down Votes)) + (Post Time/45,000)

      • Rank = (Up Votes - Down Votes) / (Post Time)

      Page 25

      • Rank = Post Time / (Up Votes - Down Votes)

      • Rank = (Up Votes) - (2 * Down Votes)

      • Rank = Up Votes - Down Votes - Post Time

      Page 26

      • Hacker News Rank = (Votes - 1) / (Age^1.5)

      Page 27

      • Quiz 15 | Ranking

      • 3. Use the Reddit scoring algorithm of Log10(Up Votes - Down Votes) + PostTime/45,000.

      • 4. Consider the Hacker News scoring algorithm of (Votes -1)/(Age^1.5).

      • 5. Consider a website that ranks posts.

      Page 28

      • Consider a website that ranks posts

        • Four posts listed with Title, UpVotes, DownVotes, and PostTime

        • Ranking formula: UpVotes - DownVotes - PostTime

        • Highest ranked post: Reddit, what is a good movie for when you need to escape from reality and maybe cry a little?

      Page 29

      • Consider a website that ranks posts

        • Four posts listed with Title, UpVotes, DownVotes, and PostTime

        • There exists a ranking algorithm that could put these posts in any order

      Page 30

      • Big O notation

        • Worst Case Scenario in Algorithms for Time and Space Complexity

        • Examples of Big O notation:

          • O(1): x = a

          • O(logN)

          • O(N)

          • O(NlogN)

          • O(N!)

          • Polynomial algorithms: O(n^3)

          • Quick sort in worst case scenario: O(N^2)

          • Quick sort in best case scenario: O(NlogN)

          • Merge sort in worst case scenario: O(NlogN)

          • Merge sort in best case scenario: O(NlogN)

          • Modern sorting algorithms: O(NlogN)

          • Searching on a sorted list: O(LogN)

          • Searching on an unsorted list: O(N)

          • Brute Force: O(N!)

      Page 31

      • Graph Basics

        • Reasons for studying graphs

        • Nodes, Edges, Weights

        • Shortest path

      • Dijkstra’s Algorithm

        • What it does

        • Reasons for studying it

        • How to calculate shortest path

      • Ranking Algorithms

        • Reasons for studying ranking

        • Three steps: Feature Selection, Scoring, Sorting

        • Designing ranking formulas