Book Reading: The Algorithm Design Manual

Oct. 30, 2016

1. Warm up the talk: 
It is a mix of feelings when Julia spent last Saturday to work on HackerRank walmartLabs codesprint. She bet on the hard algorithm and tried to try her luck, she ended up over 10+ hours scoring 0 on the algorithm. She experienced bad behavior to write a bad function when she was tired; and then, she disciplined herself to write a good function. She tried to reduce second loop to n/2000 (line 139), n/100 to guess the timeout (3 seconds) range - O(n) or O(nlogn). Tried to exhaust all the tricks to work better with unknown test cases on HackerRank.com.

She felt some disappointment after the contest, because of bad performance, her gambling behavior - bet on the hard algorithm. She turned the experience to very positive one - did some research what to work on next.

The algorithm design manual

http://www.algorist.com/

Please write down the time spent on the book.

2. Side track to the good/ bad function illustration:

A bad function:
https://www.hackerrank.com/contests/walmart-codesprint-algo/challenges/fibonacci-sum-1/submissions/code/7561665

Here is the gist.

189 -233 failed 3 sample test cases
at least 3 things are not good:
code smells? different abstraction level mixes in one function.

A good function:
17th submission:  pass sample test cases - 3 test cases
https://gist.github.com/jianminchen/4245cb1d9c4a7c625ffe1d96f7e88bb5

function line 190 -217 fiboSmart2


3. Back to book reading: 

Study Notes: 
http://www3.cs.stonybrook.edu/~algorith/

http://www.algorist.com/


Page 14 - 1/ Introduction to Algorithm Design

Hunting for counter-examples techniques:

Think small
Think exhaustively
Hunt for the weakness
Go for a tie
Seek extremes

Page 15 - mathematical induction vs  programming technique of recursion

A saying "a computer scientist is a mathematician who only knows how to prove things by induction."

Algorithms are recursive or incremental

Insertion sort explanation using induction proof - go over the page again.

Chapter 2 - Algorithm Analysis

2.3 Growth Rates and Dominance Relations

Julia works on hackerRank contest - 3 seconds - time limit

Need to find a public link about Growth rates of common functions measured in nanoseconds

Similar to page 38:

2.3.1 Dominance relations:  (Page 39, 51/739)

Constant functions
Logarithmic functions
Linear functions
Superlinear functions
Quadratic functions
Cubic functions
Exponential functions
Factorial functions

Chapter 10 

How to design algorithm?
Do I really understand the problem?  (page 357 - 358)

Julia's notes for iteration through quickly:
Q1: input
Q2: output
Q3: small example to solve by hand first
Q4: optimal solution/ settle for close to optimal solution?
Q5: ask about a scalability question? 10 item, 1000 items, 1 million items?
Q6: ask about time spent, 1 second, 1 minute, 1 hour
Q7: Time to invest in implementation ( 1 day or more freedom )
Q8: problem classification: numerical/ graph algorithm/ geometric/ string/ set

Extended study "Growth rates of common functions measured in nanoseconds" through Google search:
Google search:
keyword:
Growth rates of common functions measured in nanoseconds

Growth rate - which one has best presentation?
This is the best one! (Spent 10 minutes to read, and then, memorize something on the presentation)

https://www.cs.princeton.edu/courses/archive/spr10/cos226/lectures/02-14Analysis-2x2.pdf

Follow up

March 9, 2018

It is so much fun to read the blog again. Google search result is kind of random. I clicked the link and lead to the blog.

What I did is to make the blog better, created a gist for one of the submission mentioned in the blog, and then add the link.