Go Back   Freethought Forum > The Marketplace > Study Hall

Reply
 
Thread Tools Display Modes
  #26  
Old 11-06-2014, 06:43 AM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

First programming assignment on the Algs II course was to use a subset of the 'Watson' program's vocabulary to find odd-one-out words.

So your program has to look at lists of words like: rabbit, dog, chipmunk, carp, albatross, leopard, cricket, salamander, tarantula; and pick the odd-one-out.

We were given some text files containing about a quarter of a million nouns with lists of links between groups of nouns that allowed our programs to build a directed graph. The digraph could then be used to run efficient searches for how closely two groups of words are semantically related.

I could have probably done it in a few hours by using all the available classes provided, but it was more interesting to write my own optimized algorithms for the necessary searches - so it took me a couple of days to get all the bugs out.
__________________
Reply With Quote
Thanks, from:
Ensign Steve (11-06-2014)
  #27  
Old 11-06-2014, 10:21 AM
JoeP's Avatar
JoeP JoeP is offline
Solipsist
 
Join Date: Jul 2004
Location: Kolmannessa kerroksessa
Gender: Male
Posts: XXXVMMXI
Images: 18
Default Re: Yet another free university....

What was the answer?
__________________

:roadrun:
Free thought! Please take one!

:unitedkingdom:   :southafrica:   :unitedkingdom::finland:   :finland:
Reply With Quote
  #28  
Old 11-06-2014, 04:06 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

Well, I made that one up as I posted but I just tried it on my program and it chose 'carp' as the greatest outcast.

We used the noun part of the WordNet database which is a freely downloadable 'dictionary' with relations between words - and it's available in languages besides English.

There's an on-line tool here that lets you measure the 'distance' between any two words. What my program does is compare all pairs of words in the list and sum the differences. So it's saying that the sum of all the distances from 'carp' to each other word in the list is greater than the sum of distances when you start with any other word.

Many of the test examples we used to test our programs do have an 'obvious' odd-one-out: water, soda, bed, orange_juice, milk, apple_juice, tea, coffee; and the program does always seem to choose the 'correct' answer.
__________________
Reply With Quote
Thanks, from:
Crumb (11-06-2014), Dragar (11-06-2014)
  #29  
Old 11-06-2014, 05:13 PM
JoeP's Avatar
JoeP JoeP is offline
Solipsist
 
Join Date: Jul 2004
Location: Kolmannessa kerroksessa
Gender: Male
Posts: XXXVMMXI
Images: 18
Default Re: Yet another free university....

Try it on
ceptimus, dragar, JoeP, Leesifer, Crumb
__________________

:roadrun:
Free thought! Please take one!

:unitedkingdom:   :southafrica:   :unitedkingdom::finland:   :finland:
Reply With Quote
Thanks, from:
Crumb (11-06-2014)
  #30  
Old 11-06-2014, 06:00 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

Those nouns aren't in the dictionary. Crumb is there though not capitalized. There are entries for Joe-Pye_weed and Quintus_Septimius_Florens_Tertullianus though so it's a pretty wide-ranging set of nouns!

crumb drag have distance 10 with the common ancestor: whole unit.
lee crumb have distance 13 with the common ancestor: physical_entity
Joe-Pye_weed Quintus_Septimius_Florens_Tertullianus have distance 9 with the common ancestor: organism being
__________________
Reply With Quote
Thanks, from:
Ensign Steve (11-06-2014)
  #31  
Old 11-06-2014, 06:56 PM
JoeP's Avatar
JoeP JoeP is offline
Solipsist
 
Join Date: Jul 2004
Location: Kolmannessa kerroksessa
Gender: Male
Posts: XXXVMMXI
Images: 18
Default Re: Yet another free university....

The dictionary is defective.
__________________

:roadrun:
Free thought! Please take one!

:unitedkingdom:   :southafrica:   :unitedkingdom::finland:   :finland:
Reply With Quote
  #32  
Old 11-06-2014, 06:56 PM
JoeP's Avatar
JoeP JoeP is offline
Solipsist
 
Join Date: Jul 2004
Location: Kolmannessa kerroksessa
Gender: Male
Posts: XXXVMMXI
Images: 18
Default Re: Yet another free university....

Although there are some custom user title options there ...
__________________

:roadrun:
Free thought! Please take one!

:unitedkingdom:   :southafrica:   :unitedkingdom::finland:   :finland:
Reply With Quote
  #33  
Old 11-06-2014, 09:52 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is online now
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXXI
Images: 66
Default Re: Yet another free university....

I'm still doing the programming assignments and problem sets for this class, and consistently getting 5/5 on programming and < 5/5 on problem sets. They are just so annoying and stupid and who cares!

I'm also about a week behind, as I didn't notice when the course started, so I got a late start. I'm advancing at a rate of one week per week, so I'm getting the assignments in under the two-week deadlines, but I will always be a week behind unless I can figure out how to accelerate my progress. (There's some deep maths for ya!)

I'm thinking of taking a compilers course next. That's one class that I never, ever took in school, though I find the concept fascinating in the abstract. I like doing parse trees, like in natural language processing, and I figure it's got to be even easier with unnatural programming languages. The optimization stuff is probably challenging, though. Who knows?

:larrybounce:
__________________
:kiwf::smurf:
Reply With Quote
Thanks, from:
ceptimus (11-06-2014)
  #34  
Old 11-06-2014, 09:55 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is online now
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXXI
Images: 66
Default Re: Yet another free university....

Looks like the one compilers course doesn't have any future sessions lined up. I can watch the video lectures, but there aren't any links to programming assignments. :sadcheer:
__________________
:kiwf::smurf:
Reply With Quote
Thanks, from:
ceptimus (11-06-2014)
  #35  
Old 11-06-2014, 11:38 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

__________________
Reply With Quote
Thanks, from:
Crumb (11-07-2014), Dingfod (11-07-2014), Ensign Steve (11-06-2014), JoeP (11-07-2014), mickthinks (11-10-2014)
  #36  
Old 11-08-2014, 02:21 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

This week we're implementing seam carving which is an algorithm for resizing images without scaling or cropping and with minimal distortion. Although it's actually a fairly simple algorithm based on finding shortest paths through graphs, it was only discovered (invented?) in 2007.

We're having to implement it using Java, but there is an on-line JavaScript version you can play with here to get a feel for what the algorithm is capable of. It is so useful that it's now been incorporated into most paint programs and even operating systems and browsers so that images can be resized to fit displays with the minimum of distortion or loss of important detail.
__________________
Reply With Quote
Thanks, from:
Crumb (11-09-2014), JoeP (11-08-2014)
  #37  
Old 11-18-2014, 12:30 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

This week's assignment was baseball elimination.

Quote:
Originally Posted by the assignment
It is sometimes not so easy for a sports writer to explain why a particular team is mathematically eliminated. Consider the following scenario from the American League East on August 30, 1996:

w[i] l[i] r[i] g[i][j]
i team wins loss left NY Bal Bos Tor Det
---------------------------------------------------
0 New York 75 59 28 - 3 8 7 3
1 Baltimore 71 63 28 3 - 2 7 4
2 Boston 69 66 27 8 2 - 0 0
3 Toronto 63 72 27 7 7 0 - 0
4 Detroit 49 86 27 3 4 0 0 -

It might appear that Detroit has a remote chance of catching New York and winning the division because Detroit can finish with as many as 76 wins if they go on a 27-game winning steak, which is one more than New York would have if they go on a 28-game losing streak. Try to convince yourself that Detroit is already mathematically eliminated.
We were instructed to use a flow network to express the problem (and many similar problems with much larger divisions) and the Ford-Fulkerson algorithm to determine the maximum flow/minimum cut which then tells you which teams (if any) are eliminated and what combination of other teams' results cause the elimination.

It's not obvious at first how flow in a network relates to game score tables, but it does get the work done quickly and correctly.
__________________
Reply With Quote
  #38  
Old 11-22-2014, 02:36 AM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is online now
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXXI
Images: 66
Default Re: Yet another free university....

Wait. I don't recognize any of that. Did you start your next class? I'm so confused.

During my convalescence, I got a little bit caught up in the Stanford class, so I'm only a half a week behind instead of a whole week. Just in time for the class to be over. I still have 5/5 on all the programs, but my problem sets are anywhere from 3 to (rarely) 5 points, so I may be looking at a B in this class. :egad: I guess it will depend on the final. Double :egad:

But it doesn't count for anythig so the point is did I have fun? Absolutely! :thumbup:

I loved getting into the graph problems. I only took a graph theory course in school, no programming, so I was implementing this stuff for the first time. The project that was supposed to be the most difficult in the course (minimum cut problem) took me about 15 minutes and made me feel like I was finally getting the hang of programming after all these years. But the one after it (shortest paths) took two days of frustration and rage and knocked my ego right back down. :doh:

It goes to show you never can tell.
__________________
:kiwf::smurf:
Reply With Quote
Thanks, from:
ceptimus (11-22-2014)
  #39  
Old 11-22-2014, 10:28 AM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

Quote:
Originally Posted by Ensign Steve View Post
Wait. I don't recognize any of that. Did you start your next class? I'm so confused.
I said upthread I'd decided to flunk the Roughgarden course so I could concentrate on the Sedgewick part II course.

The Sedgewick course is light on proofs (which don't really interest me) and heavy on coding (which does). Our next assignment is the "Boggle" game where your algorithm has to find all possible words that can be traced out in a jumbled grid of letters. We'll be using trie data structures (pronounced 'try') which are special forms of tree networks that are perfect for storing (and retrieving) strings in a fast and memory-efficient way.
__________________
Reply With Quote
Thanks, from:
Ensign Steve (11-22-2014), slimshady2357 (11-22-2014)
  #40  
Old 12-07-2014, 12:07 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

On my seven-year-old computer, my Java Boggle solver solves ten thousand random Boggle boards per second (rolling simulated official Hasbro dice). It uses a dictionary with over a quarter of a million words and finds all possible words every time. It sometimes scores over 3000 points even though there are no 'circles' on any of the dice that double the score of any words containing the circled letter. :shocked:

Pretty humbling and has made me not want to play Boggle any more. :(
__________________
Reply With Quote
Thanks, from:
Ensign Steve (12-08-2014)
  #41  
Old 12-08-2014, 09:24 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is online now
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXXI
Images: 66
Default Re: Yet another free university....

I completely forgot to take the final before the deadline, so I kind of feel like a flake even though it wasn't for anything. :derp:

Oh well, on to the next thing, as soon as I figure out what.
__________________
:kiwf::smurf:
Reply With Quote
Thanks, from:
ceptimus (12-08-2014), JoeP (12-08-2014)
  #42  
Old 12-08-2014, 09:47 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

If you're still in the mood for on-line courses, I recommend the Sedgewick Algorithms course - parts I and II. You could look at part II now as it's still open, but to get the continuation you're probably better to wait for part I to roll around again. Even though it will be easy for you after the Roughgarden course, the programming assignments are still fun and interesting. AND NO PROOFS!!!!11

The final assignment for part II is for us to implement the Burrows Wheeler data compression algorithm - this is the one used in Linux bzip2 - it generally outperforms zip and other similar data compression algorithms

Princeton don't offer any sort of certificate, and not even a record that you took the courses! So you can drop out of the Algs courses at any time without feeling guilty!
__________________
Reply With Quote
Thanks, from:
Ensign Steve (12-09-2014)
  #43  
Old 12-15-2014, 05:41 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

The Algorithms II course is now in its last week and I've completed all the programming assignments.

I was looking for another course to try next and I see Stanford has a self-paced course on compilers. I remember E.S. said she was looking for a compiler course so I thought I'd mention it here.

They recommend you to use C++ or Java though you can use any other language if you wish. The course teaches about compilers helping you towards implementing your own compiler for the COOL language (Classroom Object Oriented Language).
__________________
Reply With Quote
  #44  
Old 12-15-2014, 08:22 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is online now
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXXI
Images: 66
Default Re: Yet another free university....

A self-paced compiler class sounds cool. I will definitely look into it.
__________________
:kiwf::smurf:
Reply With Quote
  #45  
Old 12-15-2014, 10:47 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

If you enroll for the course you get to see all the lectures and assignments - but the video lectures are hosted on YouTube so you can peek at them without even enrolling

__________________
Reply With Quote
Thanks, from:
Ensign Steve (12-15-2014)
  #46  
Old 12-29-2014, 10:11 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is online now
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXXI
Images: 66
Default Re: Yet another free university....

:doh: Is it this one? That's the same one that I had on my watchlist, but it never even occurred to me that I could register for a session in the past.

I'm on this! Watching week 1 videos now. :weirdtv:
__________________
:kiwf::smurf:
Reply With Quote
  #47  
Old 12-29-2014, 11:26 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCXC
Images: 28
Default Re: Yet another free university....

Yes that's it. I've watched the week one vids and I've set up the VM to do the coursework in. I've not written any code yet though as I've been working on another project.

Are you planning to use Java or C++ ? I've not decided yet - I could use the same as you so we can share code if you like.
__________________
Reply With Quote
Thanks, from:
Ensign Steve (12-29-2014)
  #48  
Old 12-29-2014, 11:54 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is online now
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXXI
Images: 66
Default Re: Yet another free university....

And because I don't already have a hard enough time separating fantasy from reality :shiftier:, I signed up for this one starting on Jan 7.

Visual Perception and the Brain
__________________
:kiwf::smurf:
Reply With Quote
Thanks, from:
ceptimus (12-30-2014)
  #49  
Old 12-29-2014, 11:56 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is online now
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXXI
Images: 66
Default Re: Yet another free university....

Quote:
Originally Posted by ceptimus View Post
Yes that's it. I've watched the week one vids and I've set up the VM to do the coursework in. I've not written any code yet though as I've been working on another project.

Are you planning to use Java or C++ ? I've not decided yet - I could use the same as you so we can share code if you like.
I haven't started yet, so it's not carved in stone, but I'm leaning toward C++. I've been doing too much Java lately with work and my graphics stuff, and I want to flex my lower-level muscles. :flex:
__________________
:kiwf::smurf:
Reply With Quote
  #50  
Old 12-31-2014, 08:17 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is online now
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXXI
Images: 66
Default Re: Yet another free university....

I can't use the VM at work so I have just been binge-watching the videos. I'm into week 5 or 6, bottom-up parsing. It's everything I dreamed it would be and more. I'm looking forward to the unit on optimization.
__________________
:kiwf::smurf:
Reply With Quote
Reply

  Freethought Forum > The Marketplace > Study Hall


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

 

All times are GMT +1. The time now is 06:51 AM.


Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Page generated in 1.34634 seconds with 13 queries