File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Scala and the fly likes Scala Coursera - Week 4 Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Languages » Scala
Bookmark "Scala Coursera - Week 4" Watch "Scala Coursera - Week 4" New topic
Author

Scala Coursera - Week 4

chris webster
Bartender

Joined: Mar 01, 2009
Posts: 1477
    
  11

Here we go again. At least we will do when the videos come online...


No more Blub for me, thank you, Vicar.
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9243
    
    1

This week's assignment is going to be about Huffman Coding. Interesting to learn these stuff.


SCJP 1.4, SCWCD 1.4 - Hints for you, SCBCD Hints - Demnachst, SCDJWS - Auch Demnachst
Did a rm -R / to find out that I lost my entire Linux installation!
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9243
    
    1

Isn't Week4 supposed to be about Collections as per the Syllabus below?

https://www.coursera.org/course/progfun

The Week4 video lectures says that it is about Types and Pattern matching. I'm a bit surprised about this.
chris webster
Bartender

Joined: Mar 01, 2009
Posts: 1477
    
  11

Joe Harry wrote:Isn't Week4 supposed to be about Collections as per the Syllabus below?

https://www.coursera.org/course/progfun

The Week4 video lectures says that it is about Types and Pattern matching. I'm a bit surprised about this.

Yes - it looks like we've skipped to the topic for Week 5 instead.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

Maybe there's just some overlap. I'm watching the first video at the moment and it's about linked lists, so collections are definitely on the menu as well. But it's a new course, and it wouldn't surprise me if they've decided to move things round a bit since the syllabus was announced.

Edit: OK, that may be overstated, the linked list is just a demonstration of polymorphism and generics. Looks like they've swapped weeks as Chris said.
chris webster
Bartender

Joined: Mar 01, 2009
Posts: 1477
    
  11

The assignment has now appeared online and as Joe says, it's about Huffman coding. In case (like me), this is new to you, there's a handy 10 minute video introduction to Huffman coding here.

Also, despite the fact we've skipped the Collections lectures, there are loads of methods in the Scala List class that will come in handy here.

Incidentally, you may have received a mail from Coursera about cheating - apparently some people have been putting the assignment answers on Github - so we'll need to maintain our customary discretion about any hints we publish here: we don't want any unfortunate misunderstandings.
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9243
    
    1

Looks like for this week, I might have to consult the Scala API documentation many times to find out the right methods that I could use to implement the assignments. I understood the theory behind Huffman coding. I also managed to get the weight and chars done as well. Part 1 is done. 2 lines each for weight and chars.

Would start with Part2 tomorrow.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

Got the decoding working, though I did resort to decoding it manually as a debugging aid! The encoding can wait .
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9243
    
    1

Matthew Brown wrote:Got the decoding working, though I did resort to decoding it manually as a debugging aid! The encoding can wait .


Sounds great. So that would mean you are done with Part1, Part2? But I'm sure most of the solutions this time aren't one liners as before.
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9243
    
    1

What is meant by Singleton? I do not get this comment on the singleton method.

Checks whether the list `trees` contains only one single code tree
chris webster
Bartender

Joined: Mar 01, 2009
Posts: 1477
    
  11

Joe Harry wrote:What is meant by Singleton? I do not get this comment on the singleton method.

Yes, I thought that was a bit unclear, but I understood it as meaning simply that we should check if there is only one tree left in the list. We use the singleton() function later on in the until() function, which is supposed to stop when you have a "list containing only a single tree".

About to start looking at decoding...
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9243
    
    1

I'm trying out the times method and I'm surprised that eclipse complains about the following line:



It says that chars.head is not a member of List[Char]. My accu is of type List[(Char, Int)] and the chars is a List[Char]. So chars.head should result in a Char. Is there something fundamentally wrong with my understanding?

Later I tried to print it and to my surprise, chars.head evaluates to an Int

Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

I'm not sure exactly what you're trying to do there, but that syntax looks a bit strange to me:

(* not tested - I have a vague memory of having trouble creating tuples like that, but intuitively it seems right)

Edit - posted before you added the second bit of the message
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

This line
evaluates to

Note that isn't creating a List of Tuples. It's creating a list containing two items. One is a Char, the second is an Int, but it's probably inferring List[Int] (because Char can be automatically converted to an Int).
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9243
    
    1

Matthew Brown wrote:This line
evaluates to

Note that isn't creating a List of Tuples. It's creating a list containing two items. One is a Char, the second is an Int, but it's probably inferring List[Int] (because Char can be automatically converted to an Int).


Got that now. It takes a bit of time for me to get used to the syntax style in Scala.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

By the way, there's a shorthand for anonymous functions that you can use when it's a relatively simple function. Your code:
can be reduced to
because of type inference, but that can be simplified further to:

Obviously, only use it if you think it makes things clearer. Sometimes it does, sometimes it doesn't.
chris webster
Bartender

Joined: Mar 01, 2009
Posts: 1477
    
  11

I just finished implementing the encoding using the Huffman tree and I'm looking at the stuff for building a code table, merging sub-tables and so on. Is it just me, or is this needlessly complicated?

We already know what characters are held in the tree because there's a list of them stored at each node, including the root, and we already know how to encode an arbitrary message e.g. of a single character. So it would seem simpler (to me at least) if we just worked through the characters, fetched the encoding for each one, and added each char/code pair to the code table. I reckon that's probably just a couple of lines of code, instead of all this table-merging stuff.

I suppose they want us to practice recursion up and down trees and merging lists/trees, but I'm getting a wee bit tired of all this academic CS101 stuff that I doubt I'll ever need to know again in whatever remains of my career.

OK, rant over. I'm off to the pub for lunch before I start on the code table: Cheers!

Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9243
    
    1

Did you guys had to sort anything for the combine implementation?

I tried to sort my resulting List using the sortWith method as below:



But seems like the sorting won't happen!
chris webster
Bartender

Joined: Mar 01, 2009
Posts: 1477
    
  11

Joe Harry wrote:Did you guys had to sort anything for the combine implementation?
I tried to sort my resulting List using the sortWith method as below:

But seems like the sorting won't happen!

The comment for the combine function says:
* The parameter `trees` of this function is a list of code trees ordered by ascending weights.

I didn't need to sort the list(s) here because the incoming list is already sorted. You just need to put the new Fork node, containing the first 2 elements of the original list, into the correct position in the rest of the original list. There are some useful methods on the Scala List class API that will help you do this.


Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

I sorted it using sortBy() because it was easy, but after sleeping on it realised that it's not necessary, as Chris says, so I'm planning to change it when I'm next working on it.
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9243
    
    1

Matthew Brown wrote:I sorted it using sortBy() because it was easy, but after sleeping on it realised that it's not necessary, as Chris says, so I'm planning to change it when I'm next working on it.


The Javadoc of the combine method also says the following:

This node is then added back into the remaining elements of `trees` at a position such that the ordering by weights is preserved.


What happens if you test your combine method with the following test case?



Mine fails even though I do a sortWith by passing the head and tail as I've mentioned in my post above!
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

May be a silly question, but you are remembering to use the return value of sortWith, aren't you, because the list you call it on is unaffected?

Mine passed a comparable test. What I'm not 100% sure of (because it depends on the sort algorithm) is whether it might possibly reorder nodes that have the same weight. And also, I'm not sure if that's actually a problem. But I'm going to change it anyway.
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9243
    
    1

Matthew Brown wrote:May be a silly question, but you are remembering to use the return value of sortWith, aren't you, because the list you call it on is unaffected?


I did not quite understand your statement here?

You are right. The List is unaffected by the sortWith and that us exactly my concern.

What I get as a restult of the call to the combine method is as below:

Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

What I mean is - List is immutable. The method returns a new List with the required order. If that's where you're going wrong, it's the equivalent mistake to:
chris webster
Bartender

Joined: Mar 01, 2009
Posts: 1477
    
  11

Joe Harry wrote:Mine fails even though I do a sortWith by passing the head and tail as I've mentioned in my post above!

I don't know if this will help (and we don't want to be accused of cheating of course ), but here is one way to put a new item in an ordered list without having to re-sort it.

  • Say you have an ordered list: [1, 7 , 12, 15, 21]
  • You now want to add an extra element (13) in the correct position.
  • One way to do this is by breaking your original list in two at the appropriate point e.g. where the element values are < your new element (13).
  • This would give you two new lists: [1, 7 , 12] and [15, 21]
  • You could now build a new list by combining these two lists with your new element: [1, 7 , 12] and [13] and [15, 21] ---> [1, 7 , 12, 13, 15, 21]

  • The Scala List API provides methods to do each of these steps.

    Mind you, the submission tests have just informed me that I have a separate bug in my combine() method! Doh!

    Edit: Bug fixed - forgot to handle an empty list of Trees in combine() and singleton(). Also FYI, you will lose points if you don't call mergeCodeTables() from the convert() function.

    Joe Harry
    Ranch Hand

    Joined: Sep 26, 2006
    Posts: 9243
        
        1

    Matthew Brown wrote:What I mean is - List is immutable. The method returns a new List with the required order. If that's where you're going wrong, it's the equivalent mistake to:


    My logic has somethihng like this:



    Joe Harry
    Ranch Hand

    Joined: Sep 26, 2006
    Posts: 9243
        
        1

    Could you guys help me visualize how the Tree would look like for the following CodeTree:

    Matthew Brown
    Bartender

    Joined: Apr 06, 2010
    Posts: 4240
        
        7

    Fair enough. As I said, might be a silly question, but it would have explained the symptoms.

    Here's your tree for that structure...

    so 'a' -> 00, 'b' -> 01, 'c' -> 1

    (I actually sketched the whole French alphabet tree while I was debugging!)

    Someone's actually posted some code to the Coursera forums that will draw any tree for you, though I haven't tried it.
    Joe Harry
    Ranch Hand

    Joined: Sep 26, 2006
    Posts: 9243
        
        1

    I just managed to draw that myself. The SICP book helped me with that.
    Joe Harry
    Ranch Hand

    Joined: Sep 26, 2006
    Posts: 9243
        
        1

    Done with the decode and encode. It was easier than I originally thought.

    Coming back to combine. What did you guys get for the following test case?

    Matthew Brown
    Bartender

    Joined: Apr 06, 2010
    Posts: 4240
        
        7

    Since you're only supposed to call combine() with a list already sorted by weight, I don't think the behaviour is defined. My implementation would produce the second of those.
    chris webster
    Bartender

    Joined: Mar 01, 2009
    Posts: 1477
        
      11

    Matthew Brown wrote:Since you're only supposed to call combine() with a list already sorted by weight, I don't think the behaviour is defined. My implementation would produce the second of those.

    Same result here: submitting Joe's list to my combine() function passes the second test but not the first.

    combine() expects the input list to be ordered beforehand anyway, so why are you doing this?
    Joe Harry
    Ranch Hand

    Joined: Sep 26, 2006
    Posts: 9243
        
        1

    I got confused on the scaladoc comments given for this method where it says:

    Joe Harry
    Ranch Hand

    Joined: Sep 26, 2006
    Posts: 9243
        
        1

    I still have untill, createCodeTree and decodedSecret pending. Could you guys throw some light on untill and decodedSecret?
    Mark Udstrand
    Greenhorn

    Joined: Nov 06, 2007
    Posts: 4
    Joe Harry wrote:I still have untill, createCodeTree and decodedSecret pending. Could you guys throw some light on untill and decodedSecret?


    until is pretty simple, just focus on function passing and recursion. The result can/should be a concise effective method.
    Joe Harry
    Ranch Hand

    Joined: Sep 26, 2006
    Posts: 9243
        
        1

    Yes, until was simple and so is makeCodeTree. decodedSecret is pending!
    Joe Harry
    Ranch Hand

    Joined: Sep 26, 2006
    Posts: 9243
        
        1

    decodedSecret was the easiest of all.

    Just wanted to check with you guys as to what you got for the following test case when you print out the method calls?



    Do you guys also get what I got above?

    Wen Tong Lin
    Greenhorn

    Joined: Sep 29, 2012
    Posts: 24
    HI everyone,
    I was wondering if you guys use recursion, pattern matching in implementing times() method? Because my solution is (again) very imperative.
    Joe Harry
    Ranch Hand

    Joined: Sep 26, 2006
    Posts: 9243
        
        1

    Wen Tong Lin wrote:HI everyone,
    I was wondering if you guys use recursion, pattern matching in implementing times() method? Because my solution is (again) very imperative.


    You are supposed to use pattern matching and recursion and so is the purpose of doing this course. If you think your solution is imperative, take a look at the videos again and understand the concepts and ideas behind recursion and pattern matching. Take a look at how accumulator pattern works in recursion and you will be better at writing recursive algorithms.
    chris webster
    Bartender

    Joined: Mar 01, 2009
    Posts: 1477
        
      11

    Wen Tong Lin wrote:HI everyone,
    I was wondering if you guys use recursion, pattern matching in implementing times() method? Because my solution is (again) very imperative.

    My implementation of the times() method is half a line of code, and it uses several functions that are provided by the Scala List API to map the input list via some transformations into the output list. This seems to be a fairly functional approach - it passes the tests, anyway!

    I did use recursion and pattern matching for some of the other methods, though.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Scala Coursera - Week 4
     
    Similar Threads
    Developing our own Exam Simulator?
    ejb-jar file 's content
    chatting option
    Outgrowing our server(s)!
    DO GOD STILL EXIST IN THE WORLD