Jose M Vidal

Learning Java Videos

2010-02-23T18:02:00.003-05:00

Last semester I taught CSCE 145, our introduction to Java programming class. For that class I created a set of videos that teach the basics of Java programming using Eclipse as an IDE. The videos were very popular with students, especially those really new to programming. So, if you are a student interested in learning to program, go check them out.

CSCE 145: Chapter 1: Introduction to Java from Jose Vidal on Vimeo.

Current Research Talk

2010-02-17T13:14:00.000-05:00

This Friday at 2:30pm in 300 S. Main B102 I will be given an informal talk about our current research projects for our CSCE 791 class. This is open to anyone else who is interested. It will be a long rambling and highly disorganized version of my previous 7 minute talk.

Ongoing Research Projects

2009-11-13T14:30:00.083-05:00

Every year our department has 7-minute madness presentations in which we faculty present our ongoing research. It is a great opportunity to hear about all the innovative research going on in our department (especially in the area of multiagent systems, of course :-). The slides from my 7-minute talk are below.

For those of you who could not make it, and since I ran out of time after just a couple of slides, I write a bit about each project below.

We have a lot of papers published on distributed combinatorial auctions, especially on bidding algorithms for the PAUSE auction. This work was done with Benito Mendoza who received his PhD in May and is now working at Exxon on multiagent simulations. I continue to work on this topic but with a slightly different focus: viewing these distributed auctions as negotiation networks.

The iCoach project is with prof. Sara Wilcox from the department of exercise science. Chuck Burris, and undergraduate, has been developing on the Google App Engine a webapp that will send customized SMS messages to users by first gathering information from the user's phone, pedometer, and online information (where he is, via GPS, how much he has moved, via pedomenter or accelerometer, what his plans are, via his google calendar, etc.). There is a lot of information about us on the net, and the new smartphones will give us even more. However, aside from collecting and displaying this information back to the user in a pretty graph, there has been very little research done in to how to use this information to improve our lives. That is what we study. Our initial system is being designed to monitor, educate, and coach first-time pregnant women.

The wikitheoria is another Google App Engine webapp we are building, and by "we" I mean Jon Mayhak and Jason Rikard. The project is with prof. Barry Markovsky from the Sociology department and can be summarized as "wikepdia meets stackoverflow for sociologists, with added semantic structure". Our goal is to build a site that will enable and encourage sociologists to post their models using a common ontology (set of terms with agreed-upon definitions). The common ontology will also be developed on the site. The current site is currently being tested by forcing a graduate class of sociologists to use it.

The port simulation project is very new and its joint work with prof. Nathan Huynh from the department of Civil Engineering. Nathan is an expert in ports and trucking problems. In our initial collaboration we are looking at the problem of how the crane operators in a port should act or cooperate. The job of a crane operator is to pick up those big containers, one at a time, and put them on the trucks as the trucks arrive. The containers can be stacked up so sometimes the crane operators have to do some re-stacking of the containers, which wastes a lot of time. We are building an agent-based simulation of this problem and trying to find best strategies for the operators.

Andrew Smith is a new PhD student who has already written a paper on supply chain resiliency. Using standard models of supply-chain formation we generated sample chains and then tested these topologies for resiliency to single-point attacks. That is, if one node goes down how does that affect the network as a whole. In the paper (not yet published) we present a numerical measure of resiliency and our test results show how it varies given the number of relationship resources (a measure of sociability) and size.

Andrew is also continuing his work with Karim Mahrous from Sandia National Labs on media dispersion and influence as part of his PhD thesis. This is another agent-based modeling project, albeit a much larger one for which we only have to develop small parts of the code, which aims to model how news travels in a social network. The project will cover everything from broadcast media, to multicast media (twitter), to one-on-one via electronic (SMS) or good ol fashioned conversations over lunch.

So, if you are a graduate student and find these ideas interesting, you can sign up for my Multiagent Systems class in the Spring which will cover the basic background knowledge needed to build, and understand, multiagent systems. If you are from a funding agency or company with a few bucks to spare for research, I would love to hear from you!

Capstone Projects

2009-10-26T20:44:00.002-04:00

A blog post by Joel Spolsky on Capstone projects complains about how many of the top CS departments do not teach their students how to write large programs or how to work in large teams. Perhaps.

Here at the University of South Carolina, I created our CSCE 492 back in 2000 to address these problems. 492 is our capstone software project whose main goals, as I see them, are to:

Give the students the experience of working in a large (100 pages of code or more) software project.
Give them the experience of working in a group.

Our 492 projects are definitely not the type of project that can be finished in one or two days. They are much more significant than that. Still, on my first few years teaching it I learned that students do tend to postpone work until the last month. Thus, I have established certain guidelines.

Each group has a weekly meeting with me. In these meetings they give me their progress report and I keep track of of how much has and has not been achieved. We also set priorities for the next few weeks. Lack of progress is duly reprimanded, as any manager would do.

At the midterm there is an integration demo. Modern programs include several number of third-party libraries, from web frameworks to 3D engines, depending on the type of program being built. Students tend to underestimate how long it will take to install apache, mysql, mod_perl, library-X, put it all into svn, and get all that mess of code to say "Hello world" reliably. The integration demo is a proof-of-concept milestone which assures all of us that yes, this can work. After the demo all that is left to do is add all the features.

Finally, there is the shared code repository (I use code.google.com). Not only is this a tool that all professionals use, but it also helps me keep track of what is really going on, or not going on, in the project. Of course, it also helps the group coordinate their activities, as it was designed to.

So, yes, capstone projects should be an integral part of every Computer department's required curriculum, if the department is interested in creating graduates who can write software.

Still, I have to admit, it takes a lot of time to manage, advise, and code review 3 to 5 different projects at the same time. That might be the reason other universities either don't do this or leave their students on their own.

All Applications will be Web Applications

2009-08-14T14:02:00.002-04:00

I often mention this in my classes and other talks: it is clear that the majority of new applications will be web applications (not all of them, of course, that is just standard headline hyperbole).

Jeff Atwood gives some more reasons as to why this is happening. Basically, people like web applications because they don't have to install them or worry about what happens when they get a new computer, business like web applications because they don't have to worry about installing their custom software on every PC. We can see old desktop applications, Quicken, being replaced by web versions Mint which are better in many ways.

But the real draw of web applications lies in the interconnectedness they allow (see the photo above for an example). These applications are also services and provide REST API's for other applications to plug into them. In this way each application is also a programming library (remember DLL's and .so files?) and a database with up to date information. Thus, even the so-called desktop applications of the future will also be web applications in that they will suck down data from the web, like Google Earth. I am still trying to figure out what the proliferation of all these REST APIs and microformats will mean for multiagent systems, but I can't help but feel that this is good news for the field.

So, what does this mean for a new student? First of all, it is still programming. While you might be using a slightly higher-level language, you will still be writing for-loops, recursive functions, and lots of if-then statements. No one has invented a language that can eliminate those. Thus, nothing much changes. One still needs to have solid programming experience and knowledge of algorithms.

On the other hand, the architecture for web applications is different from the standard desktop. In a standard desktop application you write event handlers that run whenever the user clicks on a button. In web applications this becomes more complicated. You can write your JavaScript to handle events from the user, just like in a desktop application, but you also have to deal with the client-server communication (AJAX magic). This raises all sorts of very interesting questions about what activities should be handled in the server versus the client. For many of the current set of applications the decision seems easy (gmail) but it is not as clear for others: should mint.com generate their pie charts server-side or client-side? The decision depends on the user experience you are after as well as the capabilities of the client and server devices and the network that joins them (wired, wireless, reliable, spotty).

It is very exciting to realize that allowing others to use your software is as easy as emailing them the URL, and that they can use your software on their PC, netbook, smartphone, set-top box, kindle, etc. etc.

Best Way to Bid in a Distributed Combinatorial Auction?

2009-07-03T10:05:00.002-04:00

During the last year Benito Mendoza examined how different bidding strategies (really, algorithms) fare under the PAUSE auction. I would like to go over these results but first, some background.

A combinatorial auction is one where there are many items for sale at the same time and bidders can place bids on multiple items. For example, a bid might be "I'll pay $10 for items A,B, and X." These bids are then sent to the auctioneer which must find the set of winning bids that maximize revenue—– problem that is NP-complete. Check out this visualization of a combinatorial auction that I developed for class.

In the PAUSE auction there is no centralized auctioneer. The auction instead proceeds in steps. At the first step we hold parallel English auctions for each item. That is, everyone bids on every item individually. Thus, at the end we will have a (temporary) winning bid for each item. At the second set there is one auction but now all bidders must place bid-sets that cover all items in the auction, but they can use bids that the other agents placed before. Also, they can place bids that cover two items. For example, an agent might place a bid-set that includes a bid from itself for items A, and B, as well as bids, from other agents, for items C, D, and F. By restricting the agents to place complete bid-sets we are, in effect, forcing the bidding agents to solve the winner-determination problem using the existing public bids.

Well, sort of, because bidders are selfish they will want to place the bid that wins them the most items, for the least money (the bid-set that maximizes their utility). Two years ago we developed the PAUSEBID algorithm which a bidder can use to find the myopically-optimal bid-set: the bid-set that, if the auction were to end at that moment, maximizes the bidders's utility. The problem is that since this is an NP-complete problem PAUSEBID cannot be used in auction with more than about a dozen items. Thus, the next year we developed approximate bidding algorithms which have linear running time (way faster). This was good.

But, it raised another question: if the other bidders are using PAUSEBID, should I also use PAUSEBID, and spend all time computing, or should I use GREEDYPAUSEBID and save all that computational time at the risk of getting a lower utility? That is, should I think a lot about my next bid or just kinda wing it? The surprising results, which have to yet been published except on Benito's thesis, are that it is better for all bidders to use GREEDYPAUSEBID. That is, if all the other agents are using PAUSEBID, thus picking their bids optimally, then I can actually expect slightly higher utility by bidding with a simple greedy algorithm (GREEDYPAUSEBID). Also, in the world where all the agents are using GREEDYPAUSEBID the bidders get higher utility than in the world where they are all using PAUSEBID. What happens is that prices drop down a bit and thus all the bidders (buyers) win a bit, of course, the sellers lose.

Even more interesting, we also found that in the world where all the other bidders are using GREEDYPAUSEBID, my best strategy is to also use GREEDYPAUSEBID. Again, I would actually lose utility by trying to myopically-optimize my bidding strategy. Putting all these together we find that the population where all bidders use GREEDYPAUSEBID is stable (is a Nash equilbrium).

These results go against our initial intuitions. But, we must remember that an auction with lazy bidders will result in a lower sale price which benefits, on average, all bidders. Also, a myopically-optimal bidder will reveal utility gains to the other lazy bidders which they will then exploit, thus raising the final price.

Mendoza PhD in Bidding Algorithms

2009-06-16T10:26:00.004-04:00

Last month Benito Mendoza successfully defended his thesis. His research looks at the problems in establishing a distributed combinatorial auction, without the use of a central auctioneer, where the bidders have an incentive to participate and help find the best bidset.

I believe this work lays the foundation for future distributed resource allocation protocols. That is, currently companies and consumers engage in rather simple one-to-one sequential negotiations with each other: you negotiate with one car dealer, then another, then make a decision. These lead to sub-optimal allocations (translation: there was another solution where everyone in the world is happier than in the solution we ended up at). Now that all business is done on the Internet we can build sophisticated negotiation agents that will arrive at better global solutions by using the distributed resource allocation protocols that we are working on. But first, we must ensure that these protocols do find better solutions and are incentive-compatible and fair, and people want to use them (people are not always rational).

Read his thesis for more details:

Benito Mendoza Garcia. Economic and Computationally Efficient Algorithms for Bidding in a Distributed Combinatorial Auction.PhD Thesis. University of South Carolina, 2009.

Benito has accepted a position at Exxon doing agent-based modelling.

How to Email Rows from a Google Spreadsheet

2009-06-09T20:20:00.005-04:00

I have been keeping the grades from the various classes I teach in a google spreadsheet for almost two years now. It works great because I can share them with the TA or grader (back when we had TAs, before the budget cuts) while google docs maintains all the past revisions so I can always revert back if any one of us makes a mistake (always me, it turns out).

The only problem arises when I have to give the students their grades. Since the University has banned us from posting the grades outside our door, as my professors used to do, I have to email each row of the spreadsheet individually to each student. Luckily, google provides a spreadsheet API so I could write a short script that does just that.

The script below will email each row to the person whose email appears on the column named 'email', as shown in this sample spreadsheet. You will need python as well as the python gdata libraries installed for this to work. Installing them is just a matter of downloading and unzipping them in the same directory as the email-rows program below. Before you use it you will also need to change the sender and spreadSheetName to be your gmail username and the name of the spreadsheet you are using, respectively.

#!/usr/bin/python
# email-rows
#by
#jmvidal
#
#Emails every row from a google spreadsheet to the email address in that row.
#The spreadsheet must have a first row with a cell with 'email' in it.

import gdata.spreadsheet.text_db
import getpass
import atom
import smtplib
import time

def smtpLogin(password):
    """Login to the SMTP server. I'm assuming the smtp server is gmail"""
    global smtpServer
    smtpServer = smtplib.SMTP("smtp.gmail.com",587)
    smtpServer.ehlo()
    smtpServer.starttls()
    smtpServer.ehlo()
    smtpServer.login(sender, password)

def sendMessage(to,subject,body):
    headers = "From: %s\r\nTo: %s\r\nSubject: %s\r\n\r\n" % (sender, to, subject)
    message = headers + body
    print message + "\n===================================\n"
    if not testing:
        smtpServer.sendmail(sender, to, message)
    time.sleep(1) #so gmail won't ban me as a spammer

def emailRows(spreadSheetName, workSheetName):
    password = getpass.getpass()
    smtpLogin(password)
    client = gdata.spreadsheet.text_db.DatabaseClient(sender,password)
    db = client.GetDatabases(name=spreadSheetName)
    table = db[0].GetTables(name=workSheetName)[0]
    rows = table.GetRecords(1,1000)
    subject = spreadSheetName + ' grades'
    table.LookupFields() #populate table.fields

    for s in rows:
        if s.content['email']  and s.content['email'] != '':
            body = 'Your grades are:\n\n'
            for key in table.fields:
                if key == 'email' or key == 'name' or not s.content[key]:
                    continue
                body += key + '\t' + s.content[key] + '\n' 
            body += '\nJose\n'
            sendMessage(s.content['email'],subject,body)

testing = False #if testing is true then we don't send the emails, just print them.
sender = "username@gmail.com" #your gmail address

emailRows(spreadSheetName='Gdata 101', workSheetName='Sheet1')

If you like the idea but don't feel like running your own code then wait around here for a bit. I am working on turning this script into a web application so anyone can run it from the web.

Screencasting is Better than Lecturing

2009-05-12T08:31:00.000-04:00

Many years ago when I was an undergraduate, in the late 80's, I watched many of my lectures on the TV in our dorm room. Like many other schools at the time, MIT had its own cable channels that it delivered to the dorms. For several of the large classes there would be the standard lecture one could attend in person, but also a second lecture, by a second professor, that was designed solely for the camera. This TV lecture was filmed by a camera that was fixed to the ceiling pointing down to a pad of paper on which the prof. wrote. All we could see was his hand writing on the piece of paper, with occasional cuts to a head shot of him. The TV lectures then played on a continuous loop, 24/7, on the various cable channels. They were very popular with students. I even vaguely remember some drinking games constructed around them. They were the original version of the MIT Open Courseware.

Flash forward to the present and now we all can afford the technology to do even better. Thus, this last semester I decided to use online screencasts instead of real world lectures in my 242 (web applications) class, you can see the screencasts here. I followed a now somewhat established model of having the students see the lectures at home and then class consisted of hands-on exercises. I was then able to provide each student with one-on-one help in doing the exercises (these exercises were not quizes and I provided as much help as needed to get it done). This model works very well. Of course, it probably only works with small classes. I had 9 students in the class.

The feedback I received from the students was positive. Some of the main lessons I learned are

Students that already know most of the material did not watch the videos, instead they read the slides and other material I provided. These are probably the same students who would show up to class and spend all their time facebooking or somesuch. So, I think I saved them some time.
The rest of the students do watch the videos and find them useful. Students new to the material will go back and re-watch parts. They all really love the fact that they can watch at any time.
Having in-class exercises is critical as they tell me exactly how much each student knows and they drive home the message that you cannot learn how to program by watching a lecture: you have to practice. Without these exercises it is likely some students would have waited until the last day before a homework is due to practice, at which point it is impossible to get the homework done so they would have copied it. This would just increase the number of students who cannot program.
On the technical side, I used Camtasia ($299, free trial) to record the lectures and posted them to vimeo. I learned that (a) I have to eliminate the background buzzzz noise one always gets when recording as it gets really annoying (Camtasia lets me do this by pressing a button) (b) programming screencasts have to be in HD (1280x720) as regular resolution makes it really hard to see the text, only vimeo let me host HD videos at a reasonable price ($60/year).
I also bought the Bamboo Pen Tablet so I could freestyle draw on the slides. This worked fairly well, but my handwriting is even worse on the videos than in real life because I have not gotten used to writing on the pad while looking at the screen. Still, I think it helped for explaining some ideas.

Screencasting is better than lectures in that it allows students to proceed at their own pace. This is a significant advantage in CSE where we have such a large variance in the skillset of students. Still, it should be paired with even more one-on-one student contact. In effect, the teacher (or TAs, if you have them) becomes a tutor for every student in class.

The Functional Web

2009-03-06T08:44:00.005-05:00

REST triangle of nouns, verbs, and content types.

There is a new short article by Steve Vinosky introducing his new (really, re-named) column: Welcome to the Functional Web. The new column acknowledges the domination of the new distributed (web) programming paradigms. As as note of background, I have been reading Steve for many years and I can attest that he knows what he is talking about. He is not one the many architecture astronauts that so often publish on academic journals. Steve actually builds systems. He knows what the real problems are, and often provides realistic solutions.

In this article he tells how after years of building distributed applications using Java, C++, and middleware technologies (SOAP, WSDL, CORBA, etc.) he has decided that a much better approach is to use functional programming languages (Erlang, Ruby, JavaScript) and RESTful services:

After pondering this problem for years, I finally concluded that our efforts were ultimately most impeded by the programming languages we chose. C++ and Java affected how we thought about problems, as well as the shapes of the solutions we came up with, far more deeply than I believe any of us realized. Add to that the verbosity and ceremony of these languages, and the net result is that we wrote, debugged, maintained, and extended a significant amount of code that wasn’t directly helping us get to our ultimate goal. We were fundamentally blocked by our inability to change our chosen programming languages into vehicles for application distribution

This is a very exciting time for those of us who are interested in multiagent and distributed programming. We are now seeing an explosion of REST services. You can barely browse the web without tripping on yet another REST API. There is a lot of data, there is a lot of functionality, there is a lot of possibility: how do we discover and create mashups automatically? how do we make it easy for programmers to integrate these various we services? how do we use this distributed data about individuals to create new services? emergent services?

In any case, I look forward to his upcoming columns, and his blog posts.

Update: Here are his presentation slides from a talk he gave on the history of RPC and why industry has moved on.

Multiagent Security

2008-12-20T08:14:00.003-05:00

I was recently intervied by Mark Ingebretsen from IEEE Intelligent Systems about multiagent security, on which I did some work a few years ago. I don't know if my questions will appear on a future issue or not so I am posting my answers here.

Before I answer these questions I want to explain what I mean by a multiagent system and how I envision the future of security using multiagent systems.

When designing a multiagent system what we actually build is an interaction protocol which then dictates the agents' strategies. For example, I consider bittorrent to be the most successful multiagent system currently deployed. Bittorrent consists of an interaction protocol and a number of clients written anyone who wants to. Of course, the agents in bittorrent (the clients) are human/machine hybrids. The users get to make many decisions such as which files to upload and download, how long to seed a connection, how to limit bandwidth, etc. In a pure machine-only multiagent system all those decisions would be made by the software. I don't think we will want many machine-only multiagent systems, most will be hybrids.

In the case of a security multiagent system, I envision an open system where agents act like sensors in a distributed sensor network and publish or relay important information to each other. That is the first deployment step will be sensing. Once we get that working we can start thinking about having the agents act on that information: shutting down rogue PCs, dropping packets, filtering certain protocols, applying patches, etc. That is, the second deployment step will be acting. Of course, as we give the agents more and more capabilities we need to prepare for the possibility that some agents might start taking actions against the system.

Are multi-agent systems best used within a single organization's computer network or can they function as effectively if they reside on multiple connected networks? Similarly, should multi-agent systems be allowed to spread freely throughout the Internet (e.g. via voluntary downloads) or is it important that their propagation be strictly controlled?

The best way for multiagent security to be effective is by having one world-wide multiagent security protocol. Organizations would be free to choose to participate or not and there would be many different levels of participation. For example, at its simplest a company could offer a REST page with data on the security status of its internal network. The data on this page could be more detailed for a local connection than for outside connections, in case the owners are concerned about privacy. The data would be used by agents on each machine, whether local or remote, to detect and stop security threats. The same REST interface might then be extended to allow outside parties to make reports or requests. For example, an outside agent might ask another one to shut down a particular connection coming from its domain because it believes it to be a DoS attack.

Thus, I don't see agents “spreading” throughout the Internet. Instead, the protocol will be freely available and organizations will decide which parts of it to implement. Each organization must decide what information to make public, how to use information from others, and how to handle outside requests. The growth of the system is dictated by the individual desires of the participants.

Have multi-agent systems evolved to the extent that they can take collective action to actually halt a network threat? If the answer is yes, what sort of actions do they take? If no, is this a viable goal that we can expect to see implemented at some point.

I am unaware of any deployed systems that take autonomous action based on aggregate data, but there is no technical reason why these cannot exist. One problem obtaining the system administrators' trust. However, I do expect that as technology matures and research prototypes demonstrate their capabilities we will see more autonomous security systems.

What are the dangers and possible consequences that might occur if the agents were to misidentify a legitimate communication as a threat? Could the result be a serious slowing of network traffic?

That is exactly the type of problem one must keep in mind when designing an interaction protocol. The simplest way to minimize the threat of error is to minimize the agents' capabilities: if they can't do much then they can't do much damage. As we start giving them more capabilities, such as shutting down computers and networks, the threat of misuse becomes real. At this point we start looking at human management of the multiagent system. That is, the agents should present the system administrator with their case for why they want to perform a given action but only the administrator's password would allow the system to take the action. Note that this administrator only has control over his organization's agents.

Are there provisions built in allowing some sort of universal over-ride of the agents' collective actions? If so, who should have the authority to halt actions by the agents?

A universal override is a bad idea as it becomes a target for abuse. Notice that there is no universal override for the Internet or the web. I consider this a feature. In open multiagent systems we strive to distribute power, that is, to minimize the power of the most powerful agent in the system. In this way we also minimize the possibility of a catastrophe, either planned or accidental. A universal over-ride goes against these design guidelines.

Is there any danger that the agents themselves might be co-opted by a clever hacker and used to undermine a network?

Yes, individual agents can always be co-opted, that is the reality for every engineered product. But, a correctly designed protocol would have taken into account the possibility of rogue agents so their impact should be minimal. Also, a good system minimizes the power of the most powerful agent so a few compromised agents should not present too much of a problem.

Are the agents trained? If so, how? Through simulations of network activity incorporating known past threats? Or is it better to allow the agents to monitor actual network activity?

There is ongoing work on applying machine learning techniques to network activity in order to detect what is normal versus what is abnormal behavior: like an immune system. I believe that work shows a lot of promise, especially once we let these agents communicate with each other since they could then share local information in order to get a global view of an ongoing threat. For example, if an agent detects an abnormally high set of packets coming from another domain it could tell an agent on that domain, thereby possibly alerting him to a security problem within its network.

What are some of the new developments in this area that you see as particularly important?

The growth of semantic web technologies—semantic markup languages, inference engines, and web services—will greatly help speedup the adoption of open multiagent systems, such as the envisioned world-wide multiagent security protocol.

Simple Programming Questions Reveal a Lot

2008-12-04T15:19:00.009-05:00

This semester I am again teaching our Software Engineering Lab class. This is a senior-level class where we form groups of 4-5 students and develop a large software project. This semester I asked the students to write short programs on the whiteboard. I added this requirement because, after talking to our recent graduates and scouring the blogs, it is clear that nearly all employers are now using these questions to weed out possible candidates. It is not just Microsoft and Google anymore, it is also the small local insurance processing companies, etc. Everyone is asking programming questions, and I can see why.

I wanted to use really simple questions that real employers use, so I went to stackoverflow.com and asked them to give me some questions. They pointed out some simple popular questions like, among others, implementing the following:

int strstr(String a, String b): return the first location of string a within string b, or -1 if it does not appear.
String trim(String a): return a string that is like a but eliminates any spaces before and after a.
String strtok(Stream a): each time it is called it returns the next token in a, where a tokens are separated by spaces.
boolean isprime(int a): return true if a is a prime number, false otherwise.

I also came across the fizzbuzz question, repeatedly. The question is:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

The author claims that more than half of the people he interviews for programming position are unable to write this program, other commenters report seeing similar numbers. I also used this question for some students.

Luckily, my students performed better than that. However, not everyone was able to tackle these programs with complete ease, as I would have wanted. I found that surprising, especially since we require large amounts of programming in our undergraduate curriculum. Note that I do not require a perfect bug-free implementation. For these questions a solid answer simply has to implement most of the logic needed to solve the problem, even if the final program breaks for some boundary cases.

On the other hand, I also noted that all the students know the basic programming constructs. They know about strings, arrays, for loops, etc. The difficulty was always in the transformation from the English description to code. That is, the problem lies in algorithm generation.

At this point some might look to studies, such as The camel has two humps and assume that there is some gene that gives some people the ability to program. I don't believe that is correct. Current research in psychology and neuroscience shows that the vast majority of abilities are learned, not inherited (what a surprise!). That is, I believe people who are good at programming become so because they practice. My hypothesis is that some students manage to take all the classes but end up doing little programming. This is easy to do since most programming experience comes from homework problems which are extremely easy to copy.

I remember that when I was an undergraduate a study revealed that about 37% of MIT's undergraduate students taking a certain introductory-level programming class had copied some of their homework programs. Copying homework programs, or doing no programming in a group project, is an unfortunately common occurrence even in the best schools.

Beside being an honor code violation, the problem with copying someone else's program is that it leads to a vicious cycle. A student that copies one program misses out on some practice so the next program is much harder for him to write, so he has even more incentive to copy the next one, and so on. This accumulates not just over one class but over the whole undergraduate experience: programming is a skill that takes years to build. Thus, it is possible that by graduation some students have had 10 times as much programming experience as others, which we know will make them 1000 times faster programmers.

To summarize, from this experiment I have derived a couple of conclusions. For students I recommend to

Remember to practice the craft of programming. It is easy in a CSE degree, with all the high-level talk about hashing functions, AVL trees, NP-Completeness, multiple inheritance, etc., to forget to practice the basics. Every practising programmer will tell you that most of the programming they do is of the simple kind, the kind reflected by the simple questions above. Complex algorithms, theory, and language structures will help you become a great programmer, but first you have to master the basic craft: writing small programs.
Don't fall into the trap of believing that because you can read and understand a program that you can write code. That is like me saying that I can write a good novel because I can read and understand novels. Yes, you have to be able to read programs, but you also need to practice writing them: turning an English description of the problem into code. I think some students justify copying someone else's code by thinking that it is enough to read and understand what others wrote. It is not.
Practice writing small programs on the whiteboard, or on paper, especially if you are going to be looking for a job in the near future. It is a different experience from typing with Intellisense on.
In an inteview, first make sure you understand the question by repeating it back to the interviewer. Write a few sample input-output pairs on the board. Then implement the simplest solution you can think of. If you are worried that the interviewer might be looking for a better answer simply check with him. Say, “Well, a brute-force way of doing that is yada yada yada.” He will either ask you implement that or ask you for a faster solution.
Don't copy that program. It might take you all night to write it but next time you will be able to do it 10 times faster, and the next time after that you will be another 10 times faster. If at first it seems like it takes you for-fscking-ever to write a simple program it is because it does, and that is normal! Everyone is slow to start. We only get faster with practice. Oh, and that kid in your class that can write code at ninja speed, he started programming in middle school. Don't worry though, one can only get so fast with practice and after a handful of years you will reach that limit.

I also have a few suggestions for employers:

Students are easily intimidated by the whiteboard because most have never used one. Some will be too nervous to perform. Pencil and paper might be a better way.
It is important to give feedback and hints during this process. I've found that several students erroneously (probably, my fault) assumed the problem was a different and much harder one than the one I was actually asking them solve. Other students immediately tried to find a, sometimes non-existent, super clever solution instead of starting with a brute-force approach.
Ask programming questions. It is an amazingly simple and quick way to determine if someone can program. It will save your company a lot of money. But, ask several different questions of each applicant.

In any case, I will continue to use whiteboard questions as they provide valuable experience for the students. I am also planning on using more of this "face to face" type of quizing in my other classes. It is a good and quick way of getting a lot of information on a person's technical capabilities.

PS. If you want more programming practice check out my Programming Questions blog for some more examples.

CSCE 242 Sign Up Now, Please!

2008-11-13T14:31:00.003-05:00

As of this writing exactly two students have signed up for my CSCE 242: Client Server Computing class. With so few students signed up we will have to cancel the class, and I will be bummed.

I find it strange that there is so little interest when nearly all programming jobs nowadays require at least some web development, whether it is using a REST API, developing a web front-end, a mobile web front-end, or actually building a complete web application. Plus, javascript is a boatload of fun! Where else can you modify the inheritance hierarchy at runtime?

Maybe someone can comment and explain this lack of interest to me?

Mobile posting

2008-11-12T20:01:00.002-05:00

I am posting this from my iphone using an app that connects to blogger using their REST API. One service in the cloud, multiple frontends: I think we shall see this a lot more often. If you want to learn how to build these services , sign up for 242!

Master and Undergraduate Projects

2008-08-27T15:46:00.002-04:00

I have posted a list of MS thesis and undergraduate projects that I am interested in working on. If you are an undergraduate or graduate student interested in doing some research please check them out.

NSF Award for Negotiation Networks Research

2008-08-09T00:30:00.001-04:00

I am honored to have just received NSF award 0829580 to continue my research into negotiation networks. The total award is for $234K over the next 3 years. This research is under the Theoretical Foundations program, and the Scientific Foundations of the Internet's Next Generation (SING) sub-topic.

We hope that our research will lay the scientific foundations for the Internet's next generation of protocols and deployment strategies. The project summary of theproposal explains our goals:

We propose to develop automated negotiation protocols for autonomous agents in negotiation networks, which we define as a type of bargaining problem where every agent must negotiate with a fixed set of other agents in order to arrive at a unique deal. Negotiation networks are, in effect, a natural re-formulation of a winner determination in combinatorial auctions problem as a negotiation problem. They thereby distribute the costly winner determination computation among the agents and avoid the need for unnecessary exchange of currency or trusting of third parties.

Intellectual merit: Since the problem of negotiation networks combines features of characteristic form games and bargaining games from game theory, combinatorial auctions and distributed mechanism design from Economics, network exchange theory from Sociology, and distributed algorithm design from computer science, its solution should be a significant contribution to all these fields. While several parts of the proposed problem have been studied in the various disciplines, we will bring these disparate parts within one framework and provide solutions for this very important problem. Our approach is fresh in that we focus on algorithmic solutions for the dynamic, distributed problem of resource allocation among self-interested parties, in contrast with game theory and Economics' solutions which are typically steady-state axiomatic solutions. Success in this research is potentially transformative as it will provide the foundation for the engineering of protocols and efficient algorithms for distributed resource allocation, which is a pervasive problem in our ever-growing highly-interconnected society.

Broader impacts: The negotiation networks problem is not only significant from a research perspective, it also has some very immediate applications. One such application is the multiagent enactment of workflows for the growing SOAP and REST-based (Web Services) service Internet where complex tasks are dynamically and automatically bid for and allocated among arbitrarily large number of agents. Such systems would revolutionize just-in-time manufacturing and purchasing practices by automating not only the paperwork but also the allocation of resources and contract negotiation. Another near-term application lies in the development of incentive-compatible routing mechanism for the new Internet which would provide the proper incentives for companies to deploy more bandwidth and to make their existing bandwidth available to others without having to worry about freeloaders. Further down the road, negotiation networks could even eliminate the need for predefined workflows and lead to much more efficient and dynamic allocation of resources in our economy. These adaptive supply chains would be resilient to local failures and attacks as they dynamically re-negotiate deals in response to environmental changes. In fact, with slight modifications these distributed resource allocation algorithms could be used to coordinate first-responders in an emergency situation, to program distributed environmental sensor networks, and to instruct automated robotic swarms.

Marriage Problem

2008-04-30T21:26:00.003-04:00

In the marriage problem we have an equal number of men and women who we want to pair up (it is presumed they are all heterosexual). Each one has an ordered list of their prefered mates. The goal is to find the set of marriages such that no two people would rather get divorced and marry each other. That is, not two prefer each other over their assigned mates.

This problem can be solved with a simple algorithm where all the men propose to the women. Then, each woman with more than one proposal rejects all but her most preferred which she temporarily accepts. The bachelors then repeat the process by asking their most favorite woman who has not rejected them. The process continues until all women have a partner. I have a NetLogo implementation of the marriage problem that illustrates this process.

It is interesting to notice that while the women are the ones that get to turn down the men, the men do overwhelmingly better than the women. I mentioned this to my wife and she said that is why she proposed to me. Of course, in the end it is always the women who propose to us.

I am interested in finding distributed algorithms that arrive at stable solutions, that is, those where no two people would rather be married to each other than to their partner. Here is a link to a set of slides that goes into more detail on the marriage problem, in case you want to learn a bit more.

Trading Houses

2008-04-28T12:39:00.000-04:00

Imagine that all students are assigned dorm rooms in some ad-hoc way. After each one has a room, two students might find that they both prefer the room the other one has, thus they could switch rooms and both be happier. Similarly, three students (A,B, and C) might find that A prefer's B's room, B prefers C's room, and C prefers A's room. These three students might also trade rooms in a cycle. This can go on for even larger cycles. But, how do we find these cycles?

A very simple algorithm, proposed back in the seventies, is to have each agent point to its most preferred choice. If the resulting graph has any loops (it will) then all the agents in the loops exchange rooms and drop out of the game. The remaining agents then point to their most preferred room and we repeat the process until there are no more agents left.

I have implemented a simple demonstration of this top trading cycle algorithm using a simple distributed cycle detection protocol. Its fun to watch!

My Programming Languages History

2008-04-24T11:35:00.003-04:00

As faculty members in Computer Science and Engineering we often discuss the pros and cons of languages and which ones we should teach. The Tiobe software index shows us how the popularity of certain languages ebbs and flows. I think it is clear that it does not really matter which specific language you learn first or second, what matters is that you learn how to think clearly. And that you learn how to learn new languages.

As a demonstration, I thought I'd take a trip back memory lane and list the languages I learned (and forgotten) while still in school:

BASIC - Freshman year in high school I took a summer class on Basic programming using the old Tandy PET (I also had the Atari 2600 basic programming cartridge, but it kinda sucked). Next year, my new Apple IIe had basic built in. I should also mention that back then it was common for high schools to teach Basic programming, Power Point and Excel did not yet exist.
6052 Assembly language - Of course, I wanted to write games and the only way to get any kind of animation in the Apple IIe was to progran in assembly.
APL - I only worked with this extremely strange language for two weeks.
Pascal - Somehow I got a hold of a copy of a Pascal compiler for the Apple IIe. I was surprised to learn that you could write programs without line numbers and GOTO/jmp statements.
Scheme - I used it in my freshman year at college. Scheme is the simplest language I have seen. It is beautiful.
CLU - In college we had to do our software projects using CLU. It is a pre-cursor to object-oriented languages.
Emacs Lisp - I learned it for a summer job. This rss feed will be turned into HTML automatically by an Emacs Lisp function I wrote.
C - Learned it for an OS class in graduate school.
Lisp - thesis work.
Tcl/tk - thesis work.
C++ - thesis work.
Java - I wanted to write some applets, for fun.

Those are just the major programming languages I encountered while still a student (pre 1998), I also learned bits and pieces of countless scripting languages (awk, sed, bash) or special purpose languages (latex, um-prs, sql). The point is, my experience is not uncommon. A good computer scientist or software engineer will learn at least one new language every year or so. After a while, one notices how they are all not that different but how each one teaches us something about the way we think, the way we solve problems. Writing software is about how we think, and how we translate these thoughts to meet the capabilities of the machine at our fingertips.

Thus, there is no need to get too hung up on which programming language you should learn first. If you choose software as a career, you will likely learn over 100 languages over your lifetime. I can only imagine what we will be using 10 years from today!

If you also have fun writing programs then maybe you would like to try to solve some of my programming questions.

Fast Bidding in a Distributed Combinatorial Auction

2008-02-09T23:32:00.000-05:00

Walmart needs stuff moved from point A to B, for many A's and Bs. Also, these deliveries have other possible requirements: one might need a refigerated truck, one might be a night drop off, one might be a rush order, etc. Similarly, trucking companies have complex requirements about where and when they can deliver. Put these millions of orders together and you have a complex resource allocation problem. If you are willing to have everyone send their requirements to a centralized auctioneer then, maybe, you can solve this problem.

However, what it you don't want to trust, or can't afford to pay a centralized auctioneer? We are studying automated incentive-compabile negotiation protocols for distributed resource allocations. I know this is a mouthfull but all it is saying is that we are developing algorithms that automated agents can use to negotiate with each other and solve these type of problems. Think of it as moving all buy/sell transaction to the web (we are nearly there) and then using software to decide who to buy what from and at what price. We can show that this will lead to more efficient solutions, that is, everybody wins.

Anyway, our latest paper detailing our efforts is

Benito Mendoza and José M. Vidal. Approximate Bidding Algorithms for a Distributed Combinatorial Auction (Short Paper). Padgham and Parkes and Müller and Parsons ed.In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, May; 2008.
Distributed allocation and multiagent coordination problems can be solved through combinatorial auctions (CAs). However, most of the existing winner determination algorithms (WDAs) for CAs are centralized. The PAUSE auction is one of a few efforts to release the auctioneer from having to do all the work. The pausebid bidding algorithm generates myopically-optimal bids for agents in a PAUSE auction but its running time is exponential on the number of bids. We present new approximate bidding algorithms that not only run in linear time but also increase the utility of the bidders as result of small decrement in revenue.

Check it out, approximation mechanism let ut achieve 1000-fold speedups at only a small cost in utility.

A NetLogo Introduction

2008-01-08T14:35:00.000-05:00

I will be speaking tomorrow Thursday January 10 6:30pm at the Columbia Linux User's Group about NetLogo. It will be an informal introduction. I will try to show why it is a great language for both learning to program and for building simulations that can be used to engage students in active learning of other subjects: such as physics, chemistry, economics, sociology, etc. The meeting is open to all.

The Internet, Growth, and Students

2007-11-19T20:56:00.000-05:00

Today I gave a 1-hour talk to our freshmen on the history an future of the Internet. Obviously an impossible task but I did my best. I hope I conveyed to them the endless possibiblities that the Internet has opened up.

In preparation for this talk I have been asking our students: how much do you think the .com bubble affected the growth of the Internet? The general belief is overwhelmingly clear. Students believe the bubble had a large impact on the Internet growth. Of course, this is completely wrong. Check out my chart:

The bubble had absolutely no impact on the growth of the Internet which continues to grow exponentially, doubling every three years. The number of websites is doubling at least every two years. The implications of these facts are mindboggling! But, the general public, even our students, still seems to feel that software is done. Oh well, it just means more money for those of us who can program!

Combinatorial Auction Model

2007-10-23T20:04:00.000-04:00

One can visualize a combinatorial auction (with OR bids only) as a graph with two types of nodes: bids and items. Each bid node is labelled with the price of the bid and connected to all the items it is over. This is the visualization I have implemented in my combinatorial auction NetLogo model. It implements the branch-and-bounds algorithm on the branch-on-bids tree as found in my textbook.

Iterated Equiresistance Model

2007-10-11T12:49:00.000-04:00

A couple of years ago I built this simple NetLogo model that implements the iterated equiresistance algorithm in randomly generated exchange networks, as used by network exchange theory in Sociology. It now looks kinda dated and needs to be cleaned up but I thought I'd post it nonetheless. I'm using it in class as a demo.

Pareto Learning Model

2007-10-10T13:32:00.001-04:00

I have posted a new netlogo model on pareto learning which implements the algorithms from this paper. This is a quick and dirty implementation for an in class demo. As nearly always happens when I do these, I found a slight problem in the paper. They specify two different ways in which the agents choose an action. Namely, first they say that the agents choose actions stochastically based on their expected utilities, then they say that they choose their best action and with probability epsilon choose a random action. After implementing both strategies it became clear that the second one is the one they actually used. Clearly, this was just a problem of the prose being a bit confusing (at least, for me).

It is also interesting to note how such a small change in the action choice method can have such large effects on the system's behavior. Because of this I have to say that the results from this model are not stable, thus they are not of deep significance.