| Time |
S |
Nick |
Message |
| 00:33 |
|
|
aditsu joined ##friendlyjava |
| 03:54 |
|
|
nanoz joined ##friendlyjava |
| 03:56 |
|
|
nanozz joined ##friendlyjava |
| 03:59 |
|
nanozz |
i'm more interested on solving problems often leetcode these days and few courses have taken on princeton |
| 04:01 |
|
|
nanoz joined ##friendlyjava |
| 04:02 |
|
nanoz |
lately have seen a new algo called shell sort , i'm trying analyze and derive its time and space complexity |
| 04:03 |
|
nanoz |
but not able to do so, i'm h as n - length of items and often h gets new value dividing by 2 |
| 04:04 |
|
nanoz |
i;m planning for logical discussion so can derive with equation , if i'm missing something on analyzing the algo |
| 04:07 |
|
nanoz |
and also pdurbin aditsu i'm completing grokking algorithm book this weekend what are my future studies should be on , along with practise in leetcode+hackerrank |
| 04:12 |
|
|
nanozz joined ##friendlyjava |
| 04:15 |
|
|
nanoz joined ##friendlyjava |
| 06:21 |
|
|
nanoz joined ##friendlyjava |
| 06:28 |
|
nanoz |
palindrome takes n/2 time complexity on worst case and space complexity is 2N+object overhead+array references |
| 06:43 |
|
nanoz |
k will do a game on pacman using BFS---- Dijkstra |
| 10:13 |
|
|
nanoz joined ##friendlyjava |
| 10:29 |
|
pdurbin |
A friend of mine teaches algorithms at Northeastern in Boston. I bumped into one of his students last week and the student said my friend was the best teacher ever. A while back he recommended some books on algorithms to me. I can dig them up if you want. |
| 12:36 |
|
|
Jantz joined ##friendlyjava |
| 13:07 |
|
|
Jantz joined ##friendlyjava |
| 13:14 |
|
|
nanozz joined ##friendlyjava |
| 13:55 |
|
|
nanoz joined ##friendlyjava |
| 14:03 |
|
|
Jantz_ joined ##friendlyjava |
| 14:07 |
|
nanoz |
sure thanks pdurbin |
| 14:09 |
|
pdurbin |
I believe the most commonly used books for an undergraduate algorithms course are the following. |
| 14:09 |
|
pdurbin |
Cormen-Leiserson-Rivest-Stein (CLRS) |
| 14:09 |
|
pdurbin |
Kleinberg-Tardos (KT) |
| 14:09 |
|
pdurbin |
Dasgupta-Papadimitriou-Vazirani (DPV) |
| 14:09 |
|
pdurbin |
CLRS is a classic, too thick and detailed for general reading. KT is also quite hefty, but has a lot of nice "real-world" examples (especially, in its exercises). |
| 14:09 |
|
pdurbin |
DPV is quite thin and does manage to cover a lot of ground. |
| 14:10 |
|
pdurbin |
nanoz: hope that helps ^^ |
| 14:14 |
|
nanoz |
800+ pages :) thats alot more hefty |
| 14:17 |
|
nanoz |
DPV is very nice -- just so the content |
| 14:17 |
|
nanoz |
will start with DPV |
| 14:19 |
|
nanoz |
CLRS felt the book is not for me :| |
| 14:20 |
|
nanoz |
KT is reference book -- if want detailed subject learning |
| 14:25 |
|
nanoz |
on youtube found mycodeschool is good |
| 14:25 |
|
nanoz |
mycodeschool , the channel name |
| 14:26 |
|
nanoz |
grokking Algorithms are good you get the senes of fun |
| 14:26 |
|
nanoz |
aka book |
| 14:26 |
|
nanoz |
spend time on leetcode and Hackerrank ~ solve atleast 5 problems |
| 14:27 |
|
aditsu |
I know of CLR, it's good, another one is Aho & Ullman, and there was yet another one I forgot |
| 14:36 |
|
aditsu |
ah, Udi Manber |
| 14:37 |
|
nanoz |
this is an awesome book https://www.amazon.com/Grokking-Algorithms-illustrated-programmers-curious/dp/1617292230/ref=sr_1_1?keywords=algorithm+and+data+structure&qid=1566398183&s=books&sr=1-1 |
| 14:37 |
|
aditsu |
I think those are the ones I studied, almost 20 years ago :p |
| 14:37 |
|
nanoz |
20 years ago O.O |
| 14:38 |
|
aditsu |
yep, that sounds to me like the 80's, but it's actually around the year 2000 |
| 14:39 |
|
aditsu |
time flies.. |
| 14:40 |
|
aditsu |
I also got a couple of Knuth books, but those are more theoretical and low-level in nature |
| 14:46 |
|
nanoz |
you guys are not human |
| 14:46 |
|
aditsu |
o_O? |
| 14:46 |
|
nanoz |
if book is longer than 400 pages , often i sleep |
| 14:47 |
|
aditsu |
I didn't read it like a novel, just learned some things piece by piece |
| 14:47 |
|
aditsu |
maybe skipped some parts |
| 15:28 |
|
nanoz |
pdurbin, you're there on gitter called computerscience |
| 15:28 |
|
nanoz |
channel |
| 15:50 |
|
pdurbin |
Oh, yes, this channel is pretty nice: https://gitter.im/open-source-society/computer-science |
| 16:28 |
|
Jantz |
hello anyone awake? |
| 16:41 |
|
mr_lou |
Define "awake". |
| 16:44 |
|
Jantz |
does this make sense, stringarr = {"a","w","a","k","e"} |
| 16:46 |
|
pdurbin |
heh |
| 16:46 |
|
aditsu |
I'm asleep |
| 16:46 |
|
Jantz |
or shall i say anyone up for a bit o chat, about life, programming Java, machine code, byte code?? |
| 16:47 |
|
aditsu |
don't ask to ask :p |
| 16:51 |
|
Jantz |
was just wondering if to be a good Java programmer should you learn how the JVM/compiler works as well as the workings of bytecode and machine code? |
| 16:51 |
|
aditsu |
I don't think that's necessary |
| 16:51 |
|
Jantz |
oh ok |
| 16:57 |
|
aditsu |
the most complicated low-level stuff you probably need is the "java memory model", but if you're really interested, you can look into the jvm/bytecode stuff too |
| 16:59 |
|
pdurbin |
I mean, it isn't going to hurt to learn that stuff, if you have the time. :) |
| 17:00 |
|
pdurbin |
Sometimes the advice is to understand "one level down" from whatever level you're programming in. |
| 17:02 |
|
Jantz |
yeah sounds like good advice, time is on my side too so i think i probably will |
| 17:02 |
|
|
nanoz joined ##friendlyjava |
| 17:02 |
|
pdurbin |
nice |
| 17:03 |
|
nanoz |
nice |
| 17:09 |
|
nanoz |
yea! if you have time you can do this |
| 17:13 |
|
aditsu |
I know javap can disassemble classes for you |
| 17:36 |
|
nanoz |
what is the difference b/w bubble sort and selection sort |
| 17:36 |
|
nanoz |
for me both are just same |
| 17:37 |
|
nanoz |
as average case and worst case are O(n^2) |
| 17:39 |
|
aditsu |
https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html |
| 17:40 |
|
nanoz |
if people solve easy problems they get 30 point , its the expert problem they 2300 points |
| 17:42 |
|
nanoz |
if you consider swap is constant time |
| 17:43 |
|
nanoz |
so bubble sort is equivalent to selection sort |
| 17:43 |
|
nanoz |
do you agree or not |
| 17:43 |
|
aditsu |
nope |
| 17:44 |
|
nanoz |
if the elements is already sorted in best case both are O(n^2) too with no swaps involved |
| 17:45 |
|
aditsu |
actually bubble sort is O(n) in that case |
| 17:45 |
|
nanoz |
how come? |
| 17:45 |
|
aditsu |
it only does n-1 comparisons |
| 17:47 |
|
nanoz |
for every iteration it has to do right when elements already sorted |
| 17:48 |
|
aditsu |
what? |
| 17:50 |
|
nanoz |
on best case when the elements are already sorted it has to do comparision in inner loop right? |
| 17:50 |
|
nanoz |
still it would take 2 for loop isnt so? |
| 17:51 |
|
nanoz |
the only thing is it wont have swap |
| 17:52 |
|
nanoz |
the SO says have a swap indicator to make it to O(n) |
| 17:52 |
|
nanoz |
that makes sense |
| 17:52 |
|
nanoz |
https://stackoverflow.com/questions/12505832/why-is-the-time-complexity-of-bubble-sorts-best-case-being-on |
| 17:52 |
|
aditsu |
even the first implementation from wikipedia is O(n) best case: https://en.wikipedia.org/wiki/Bubble_sort#Pseudocode_implementation |
| 17:53 |
|
aditsu |
swapped remains false, so the "repeat" only gets executed once |
| 17:54 |
|
aditsu |
I was thinking of a different implementation |
| 17:55 |
|
nanoz |
me too without indicator swapped |
| 17:57 |
|
aditsu |
my implementation has only one loop: compare a[i] with a[i+1], if greater then swap and i--, else i++ |
| 17:57 |
|
aditsu |
now I'm wondering if that's still bubble sort |
| 18:00 |
|
nanoz |
nope |
| 18:00 |
|
nanoz |
it does one pass only |
| 18:00 |
|
nanoz |
if you consider test case as follows 3,5,7,1 |
| 18:01 |
|
nanoz |
after the pass it would be 3,5,1,7 |
| 18:01 |
|
nanoz |
the correctness is wrong |
| 18:02 |
|
aditsu |
i=0, 3<5, i++ / i=1, 5<7, i++ / i=2, 7>1, swap (3,5,1,7), i-- / i=1, 5>1, swap (3,1,5,7), i-- / i=0, 3>1, swap (1,3,5,7), i-- -> actually when i=0 it should do i++ instead |
| 18:02 |
|
aditsu |
next i=1, 3<5, i++ / i=2, 5<7, i++ / i=3, stop |
| 18:03 |
|
aditsu |
you missed the i-- part |
| 18:03 |
|
nanoz |
:( |
| 18:04 |
|
nanoz |
if its 7,1,3 for example |
| 18:04 |
|
nanoz |
7>1 |
| 18:04 |
|
nanoz |
swap |
| 18:04 |
|
nanoz |
i=-1 |
| 18:04 |
|
aditsu |
as I wrote above: "actually when i=0 it should do i++ instead" |
| 18:06 |
|
nanoz |
7,1,3 |
| 18:06 |
|
nanoz |
1,7 , i points to 0 still |
| 18:06 |
|
nanoz |
1,7,3 i points to 1 |
| 18:07 |
|
nanoz |
1,3,7 i points to 1 still |
| 18:07 |
|
nanoz |
nope |
| 18:07 |
|
aditsu |
i never points to the same item after an iteration |
| 18:07 |
|
nanoz |
i turns to 0 isnt so |
| 18:07 |
|
aditsu |
yeah, decrement after a swap |
| 18:08 |
|
nanoz |
it sounds more like a insertion sort |
| 18:09 |
|
nanoz |
let me take one more test case |
| 18:09 |
|
nanoz |
a random one |
| 18:10 |
|
aditsu |
insertion sort is different |
| 18:11 |
|
aditsu |
but I guess I can see some similarity |
| 18:11 |
|
nanoz |
:P |
| 18:12 |
|
aditsu |
yeah.. I think mine is something in between buuble and insertion, and insertion sort would be its optimized version |
| 18:13 |
|
nanoz |
it doesnt have a one loop as you're manipulating position |
| 18:13 |
|
nanoz |
a recursion way |
| 18:14 |
|
nanoz |
but not recursion |
| 18:15 |
|
nanoz |
what is you're worst case complexity :P |
| 18:17 |
|
aditsu |
O(n^2) |
| 18:20 |
|
nanoz |
the similarity b/w insertion sort is too much |
| 18:21 |
|
nanoz |
how do you say something as bubble sort or not |
| 18:23 |
|
nanoz |
if you optimize further its insertion sort :) |
| 18:24 |
|
nanoz |
cooooool! |
| 18:26 |
|
aditsu |
that's what I said |
| 18:27 |
|
nanoz |
cooo! |
| 19:08 |
|
|
nanoz joined ##friendlyjava |
| 21:28 |
|
|
Jantz joined ##friendlyjava |
