Monday, December 8, 2014

Improving Computer Science Education

Recently in the news are two articles that relate to improving Computer Science Education.  It is valuable to broaden the base of students who understand the basics of computing, just as students are expected to know Chemistry or Calculus.  In fact in my biased opinion, knowing the basics of computing and programming will have greater practical benefit to students; however, it should never be at the expense of a diverse education.

The White House announced that the 7 largest school districts will be including Computer Science in their curriculum.  This will quickly lead to another problem of who will teach the Computer Science classes.  Not me, but I am interested in teaching the teachers.  I do want to see Computer Science as an actual specialty (endorsement) for Education majors.

Another aspect of broadening the base is retaining students enrolled in the major.  Being part of the majority, it is difficult for me to know the challenges faced by other groups.  Similarly, I know why I entered Computer Science, so I would like to understand why others have too.  Why are they passionate or interested in this field that I am a part of?  Here are some things minority students have to say about STEM.

Wednesday, November 26, 2014

Computer Science Diversity

I attended a top program in Computer Science, where the gender split was 60 / 40.  Then I worked for five years at a major company.  Therefore, my expectation is always that anyone regardless of their gender, race, etc can succeed in Computer Science.  Now, recently there was a short lived Barbie book about being a computer engineer.  Ignoring any semantics about Computer Science, Software Engineering, and Computer Engineering being different disciplines, the work still did not portray women in the more technical efforts.  I'd rather read a collegue's remix of the work.

In a different vein of diversity, as a white male, I have been regularly been excluded from tech events because I dislike the taste of alcohol.  Thus at the (especially) frequent events in industry settings where alcohol is served, I was not socializing with my colleagues, and instead would inevitably find myself back at my desk working.  As a consequence, I was effectively excluded from the event.  And now in academia, I find myself attending conferences, where the social events are also touted for serving alcohol.  I have no issue with serving alcohol, rather it is the near exclusivity of which the drink options trend that way.  Thus a recent article struck a chord in the continuing desirability of extending the options and respecting the decision (for whatever reason) to not drink alcohol.

Monday, October 27, 2014

Liberal Arts College Positions Mini-Seminar

In continuing my search and preparation for a faculty position, today I attended a mini-seminar by LADO faculty.  (LADO - liberal arts colleges with diversity officers)  Here are some points that were raised during the breakout and panel discussions:

- You will teach both upper-level courses, as well as "service" courses.  Service is a good term to describe the low-level / introductory courses, as the faculty are rotating through this service to the department.
- Try to setup the teaching schedule so that 1 day is free solely from research.
- Continue to revise courses so they are fresh and current, but also avoid constantly creating all new courses.
- Valuable to set aside "non-office hours" times, during which the door can be shut.
- Faculty will sit in on courses and additionally interview the students, as part of composing an evaluation of your teaching.

- Recruiting undergraduates earlier for research to have time to train them, so that they will later be able to contribute.
- You can still collaborate and have broad impact through research with faculty at other more research-focused institutions.
- Grant proposals can also be keyed "RUI" (research at undergraduate institutions)
- Regular funding for sabbatical leaves, first often after the renewal of the 3-year contract.  This leave is focused on research and may be held at R1 or other institutions.
- Startup package is present to cover the transition to grant-based funding.
- Research lab costs are significantly lower at these institutions, as funds are not required for grad students, post docs, etc.
- Schools are looking for faculty hires that add diversity to the research available.

- Service is a component, but is much smaller than teaching and scholarship.  So be cautious about accepting invitations to committees, in terms of time commitment.  The service time can provide valuable insight to the functioning of the institution, as well as possible collaboration with collegues in other departments.
- You will be chair of your department someday.

- Many liberal arts institutions are located in small towns.
- Take the time to customize the cover letter.  Do you really want and care about this job?

Wednesday, October 15, 2014

Richard Lipton - Knuth Prize (Practice) Talk

Richard J. Lipton is the 2014 winner of the Knuth Prize.  His talk today was a summary of his work, which lead to received the prize.  The talk proved to be a series of short anecdotes, which are difficult to capture, but I've copied down the highlights, as best as I can.

"Do problems have labels?"  For example, simulate a queue as two stacks, is this a theory problem or system problem?  At the time, the qualifying exams were split by problem types, so labeling it mattered for which exam contained it.  Faculty at Yale were 50/50 split on whether to mix the problem types and instead students would sit for several days of CS questions rather than a theory day, then a systems day, etc.

Finding a division, separator to a planar graph, in root time.  T(n) <= C*T(n/2)
In explaining the result to Knuth, while visiting Tarjan, who responded "You've ruined my lunch."  As the result destroyed the best known algorithms that were being written, at the time, in Vol. 4.

"Throw away comments are wrong"  Many introductions make inaccurate statements like "non-uniform cannot imply uniform".  There is the work of Karp-Lipton dealing with non-uniform circuits and the uniform nature of algorithms.  The proof was later handed out on tote-bags at CCC 2010.

"Think in High Dimensions"  Binary search in high dimensional space, still logarithmic in the number of elements.  For example, take a planar graph and split it by the intersections, each slab is linear and can be quickly searched.

"Learn New Tools"  Now, one tool is "Probabilistic method" published on June 28, 1974, which shortly thereafter was a Yale seminar.  "By an Elementary Calculation" means to Erdos to use Sterling's approximation, which in one case required taking the approximation to 7 places.  Before learning this method, had been asked about the problem of Extendible Hashing, and had no idea and put it out of mind.  Later asked about it again, and the problem solved easily (or perhaps two days of proofs).

"Guess Right" One problem in solving problems in the community is that we are guessing wrong.  "It is really hard to prove false statements."  Take the problem of detecting whether a sequence of a_nb_m has n = m?  Possible using a multi-pass scan with a probablistic FSM.  Can do with one-way (i.e., single pass)?

"Need a Trick" Solving a problem of vector addition, with fixed counters, with adding and subtracting (where cannot subtract from 0).  1 counter is decidable, 2 counters is not.  But if there is no test for whether the counter is 0.  Proved it takes EXPSPACE-hard.  Pair counters, so add is subtract and vice versa.

"My Favorite Two Results" - Proving that a a^-1 = 1, in long sequence (abaaaba^-1...) can be done in LOGSPACE.  Do so by replacing the a, b with matrices, then modulo prime.  Given the distributed law and applying in any order, prove that it always stops on any expression.

"Future" Old problems, yes.  But dream of finding proofs to math problems that use CS theory tricks.

Wednesday, September 17, 2014

Preparing for Academic Jobs

I went to a recent seminar about the preparation and practice of finding an academic job.  The following summarizes the answers given by the panelists, each of whom was giving his or her opinion.  The short version is that your letters of recommendation are key.  They are the summary of your skills and qualifications by your (future) peers.  The panelists are all research-oriented faculty, which may skew some of the opinions provided.  One quality resource on teaching jobs can be found here.

Most important things in a candidate:
- Publications (some in the right places)
- Letters (don't really lie)
- Fulfilling the needs of the department
- Put "top" school in middle of interview schedule, chance to work out mistakes but not be burned out
- Energized / excited about place
- In 1:1 with faculty, only discuss own research for half of time (~15min)
- Be formal (jacket, etc)
- Prep work with faculty letter writers (explain research, plans, etc)
- Ability to connect across areas (your own area will get you the interview, the other areas will get you the offer)
- Talent, passion, impact in research
- Have a set of questions for 1:1 time of "do you have any questions?"

Things to avoid:
- Wrong / bad job talk (did you target the right audience, and yet convey knowledge in subfield)
- Attitude (arrogance that job is yours, or desperation about finding a job)
- Two interviews in one week

Letters of Recommendations:
- Especially letters from externals
- Prepare a statement of contributions (what have you really done / achieved?)

Things to focus on:
- Take risks in your research
- Network and get your name out / aware of

Postdoc versus Second Tier:
- Find collaboration and mentoring in a postdoctoral position
- It depends

- Still except some quality research
- Your research talk is a demonstration of teaching

Deciding on schools to apply:
- Location
- Areas of Focus

- Find packages from previous applicants

Tuesday, September 16, 2014

Atomic Weapons in Programming

In parallel programming, most of the time the use of locks is good enough for the application.  And when it is not, then you may need to resort to atomic weapons.  While I can and have happily written my own lock implementations, its like the story of a lawyer redoing his kitchen himself.  It is not a good use of the lawyer's time unless he's enjoying it.

That said, I have had to use atomic weapons against a compiler.  The compiler happily reordered several memory operations in an unsafe way.  Using fence instructions, I was able to prevent this reordering, while not seeing fences in the resulting assembly.  I still wonder if there was some information I was not providing.

Regardless, the weapons are useful!  And I can thank the following presentation for illuminating me to the particular weapon that was needed, Atomic Weapons.  I have reviewed earlier work by Herb Sutter and he continues to garner my respect (not that he is aware), but nonetheless I suggest any low-level programmer be aware of the tools that are available, as well as the gremlins that lurk in these depths and might necessitate appropriate weaponry.

Monday, July 14, 2014

Book Review: The Practice of Programming

(contains Amazon affiliate link)
I recently found, The Practice of Programming (Addison-Wesley Professional Computing Series), sitting on the shelf at my local library.  I am generally skeptical when it comes to programming books, and particularly those from different decades, but I trusted the name "Brian Kernighan" so I checked the book out.

And I am so glad that I did.  From the first chapter that discussed style, I wanted to read more.  And the only reason to ever stop reading was to pull out a computer and put these things into practice.  I didn't even mind that it wasn't until chapter 7 that performance was discussed.  Still, I will readily acknowledge that I disagree with some of statements in the book.  Furthermore, there are some parts of the text that are clearly dated, like discussing current C / C++ standards.

I'd like to conclude with a brief code snippet from the work.  This code is part of a serializer / deserializer.  Such routines are always a pain to write and particularly if you have many different classes / structs that need them.  Thus the authors suggest using vargs and writing a single routine that can handle this for you.  Here is the unpack (i.e., deserialize) routine:

/* unpack: unpack packed items from buf, return length */
int unpack(uchar *buf, char *fmt, ...)
    va_list args;
    char *p;
    uchar *bp, *pc;
    ushort *ps;
    ulong *pl;

    bp = buf;
    va_start(args, fmt);
    for (p = fmt; *p != '\0'; p++) {
        switch (*p) {
        case 'c': /* char */
            pc = va_arg(args, uchar*);
            *pc = *bp++;
         case 's': /* short */
             ps = va_arg(args, ushort*);
             *ps = *bp++ << 8;
             *ps |= *bp++;
         case 'l': /* long */
             pl = va_arg(args, ulong*);
             *pl = *bp++ << 24;
             *pl |= *bp++ << 16;
             *pl |= *bp++ << 8;
             *pl |= *bp++;
         default: /* illegal type character */
             return -1;
     return bp - buf;

So now we have a little language for describing the format of the data in the buffer.  We invoke unpack with a string like "cscl" and pointers to store the char, short, char and long.  Hah!  That's it.  Anytime we add new types, we just to call the pack / unpack.

Does it matter that the variables are only sequences like "pl" or "bp"?  No.  Variable names should be meaningful and consistent.  "i" can be fine for a loop iterator.

We have given up some performance (*gasp*), but gained in the other parts that matter like readability and maintainability.  I plan on using this in my current research (but only the unpack, as my serializers are already highly optimized).  All in all, I approve of this book and may even someday require it as a textbook for students.