Class 21: Aliignment

 4 Apr 2024 

Schedule

This weeks computing news discussion is now posted, and due before class on Thursday, 4 April for even ids, and by Monday, 8 April for odd ids.

There will be an Exam in class on Thursday, 11 April.

Slides

Class 21: Aliignment

  • Edit distance
  • Genome alignment

Code

Here’s the code for editdistance.html:

function edit_distance(s, t) {
    // Returns the minimum number of edits (single character insert,
    // delete, or replace operations) needed to transform s into t.

    if (!s || s.length == 0) {
        return !t ? 0 : t.length;
    } else if (!t || t.length == 0) {
        return s.length;
    } else {
        match = s[0] == t[0] ? 0 : 1; 
        return Math.min(match + edit_distance(s.substr(1), t.substr(1)), // replace
                    1 + edit_distance(s.substr(1), t), // delete first from s (insert first in t)
                    1 + edit_distance(s, t.substr(1))); // delete first from t (insert first in s)
    }
    console.assert(False, "Should not ever reach here!");
}

The version from class is editdistance1.html.

Class 19: Repeating

 28 Mar 2024 

Schedule

Project 3 is due at 7:59pm on Friday, 29 March.

There will be an Exam in class on Thursday, 11 April.

Slides

Class 19: Repetition

  • Questions about BNF grammar and derivations
  • Florida’s Social Media ban
  • JavaScript for loops

Class 18: Functions

 26 Mar 2024 

Schedule

Project 3 is due at 7:59pm on Friday, 29 March.

Beenish has office hours on Wednesday, 3-4pm in Rice 442.

There will be an Exam in class on Thursday, 11 April.

Slides

Class 18: Functions in JavaScript

Code

The code we ended up with in class today is jsboom-class18.html.

We also started playing with jsfunctions.html (which we’ll look at more on Thursday, but feel free to try and look at before then).


Evaluation procedure from Wai Keen Vong, Wentao Wang, A. Emin Orhan, and Brenden M. Lake. Grounded language acquisition through the eyes and ears of a single child. Science, 1 February 2024.

Class 17: Programming in JavaScript

 21 Mar 2024 

Schedule

Project 3 is due on Friday, 29 March.

Slides

Class 17: JavaScript Programming

  • Recapping and Extending BNF Grammars
  • News Highlights: Poisoning, Tim Berners-Lee, and the Reddit IPO!
  • Programming in JavaScript

Code

The code we ended up with in class today is below jsboom-class17.html:

<html>
<body>
    <h1>Exploring the DOM</h1>

    <script>
        function updateCount() {
            i = i - 1; // single "=" means assignment (":=") 

            countobj = document.getElementById("count");
            console.log("Updating i: " + i);
            countobj.innerHTML = "<b>" + i + "</b>";

            if (i <= 0) { // double "==" is equality comparison
                countobj.innerHTML = "<b><font size='+5'>BOOM!</b>";
            }

        }
    </script>

    <script>
        var i = 5;
    </script>

    <h2>Count Down: <span id="count"><script>document.write(i)</script></span></h2>
    <button onclick="updateCount()">Next</button>

</body>
</html>

We didn’t get to actually changing the color of the background. To do this, you can set a DOM attribute directly:

        document.body.style.backgroundColor = color;

The value of color could be a string the describes a color for a web browser - for example "red" or "#FF0000 (the hexadecimal color encoding with maximum Red, no Green, and no Blue).

Class 15: Programming!

 14 Mar 2024 

Schedule

There is a new News Discussion, with a bit more structure than the previous one. For students with an odd number in your UVA ID, the article post should be done before Tuesday’s class (March 19).

These two chapters from my book, Introduction to Computing: Explorations in Language, Logic, and Machines, are recommended readings that align closely with what we did in class:

Note that the Scheme language used in Chapter 3 is syntactically quite different from JavaScript, so don’t get confused by the examples there. In other ways, JavaScript is very similar to the Scheme language used in the book — indeed, Brendan Eich’s was hired by Netscape to design “Scheme for the web”, which ended up being branded for marketing reasons as JavaScript.

Code Examples

The code examples from class are:

Slides

Class 15: Programming

  • What is Language?
  • Components of Language: Primitives, Means of Combination, Means of Abstraction
  • JavaScript and the DOM

Questions and Answers

 10 Mar 2024 

Here are my responses to your responses to the question “What do you want to know about me or the course?” on the “Beginning of Course Survey”. If you think of any new questions you would like answered, or follow-ups on these, feel free to ask them in the Canvas discussion or by email!

In SIS it's called Foundations of IT, so is it the same course with a different name? Or is the SIS description not relevant to this class at all?

Since I had to look it up, the SIS description is here:

How computers create, preserve, manipulate and communicate information and the concepts and tools used to that end. Units include how computers work, web technologies, creating web pages, algorithms and logic, basic programming, and solving problems with spreadsheets. Students will learn to recognize computational problems and develop basic skill sets to solve future problems in their discipline of study. No prior programming experience required. Cannot be taken for credit by students in SEAS.
It is actually quite a good description, and overlaps around 80% with what we will do in this course.
Will these course cover any of the technology used in blockchains/cryptocurrencies?

We’ll definitely talk about the underlying technologies used in blockchains. I expect we’ll also have a class on how cryptocurrencies work and fail (and asking this question increases the likelihood!). In 2015, I taught a full course on cryptocurrencies, and there are many very interesting technical ideas involve in blockchain and cryptocurrency. I’m mostly disappointed, though, in how things have evolved since then.

why did you choose to teach this class?
What made you want to teach a course like this?
Why did you decide to instruct the course?

My first general answer is that I like to teach courses where I learn new things, so always try to find opportunities to teach courses in new areas (which this course does qualify for in many ways!). Over recent years, I’ve taught classes in Computational Biology, Computing and Economics, Ethics, and Generative AI and Large Language Models (as well as Theory of Computation, which I’ve taught several times, but still learn new things each time I teach it). Although you might be surprised by this, this course gives me lots of opportunities to learn new things — as a broad course covering aspects of computing most essential for non-computer scientists, it includes many topics I haven’t had much chance to learn about in previous courses.

The more specific answer for this course is that I do think it is increasingly more important that people embarking on careers in other fields understand computing, than it is for us to produce more computer science majors. (Arguably, we are already producing too many computer scientists, although still not enough ones with deep understanding and relevant expertise in key areas.)

As a first offering (for me, although cs1010 has been around forever), its great that we can have a relatively small class. I think there are also some pretty strong structural hurdles to this class becoming large at UVA (mostly that it doesn’t count for any useful requirements, and doesn’t even count as credit for SEAS students). But, I think we should eventually get to a place where every student who isn’t majoring in computing would take a course like this one. My hope is that if this course goes well and grows within the current structure, it would lead to opportunities to develop a more widespread computing course for non-majors as well as materials (like a textbook) that could be useful elsewhere.

What to you is the most interesting thing we will learn this semester?
The honest answer is I don't know yet, and it will probably be different for different people. For me, the most interesting thing I've learned about so far is [how unicode works](/post/class6), but I hope that isn't the most interesting thing you have learned!
What do you find fulfilling about learning/teaching CS?

Computer Science is the only subject I know of that offers both the joy of discovery of fundamental truths (e.g., learning about the difference between countable and uncountable infinities, and the nature of universal computation) and the empowerment of being able to build amazing tools using nothing more than your imagination (which I hope you’ll experience at least some in this class).

Will we be doing any coding or is the course more conceptual?
What interesting things are we going to do with coding in this class?

The plans for this are still a bit in flux, but you will be doing some concrete programming in Project 3 to explore dynamic web sites. The connection between concepts and coding is strong in the sense that deeply understanding a concept usually required being able to program it, but there are many ways to understand concepts that are still valuable and more easily reached that do not require programming.

Maybe a little bit about your background like where you are from and how you got to UVA.

I grew up in suburban Detroit, Michigan, and went to a good public school in a pleasant, but very boring, area. I will probably not come as a great surprised to you that I was considered somewhat nerdy growing up.

I had my first experience with computers around first grade. At that time, my elementary school had a teletype terminal that you would use a phone coupler to call into a central machine, and you could play games like “Football” and “Oregon Trail”. When I was in second grade, my elementary school got Apple II computers, and we could earn time to use them by reading books. I did this as much as I could, and learned to program by looking at the source code for the games on the computer, which was BASIC code that you could easily read and change.

I came to UVA after finishing my PhD at MIT (actually a little bit before finishing, which is another story). I got here by car, driving down from Boston area.

I would just like to get to know you as a professor and genuinely learn the information in the course. I find the curriculum of this course much more interesting than most courses I have taken at college.
Great! Hope it lives up to your expectations.
hobbies and why you teach cs

(I answered about teaching CS above, so will just talk about hobbies here.)

Today, my hobbies are mostly revolve around what my kids are doing (which, perhaps oddly or prehaps unsurprisingly, ends up not that different from what my own hobbies were earlier). My daughter (age 11) is mostly into soccer and especially playing goalkeeper, so most of my weekends is about taking her to travel soccer games and tournaments. I never played above a recreational level (which regrettably ended for me with Covid), but go to world cups when possible, including New Zealand/Australia last summer. My son (almost 9) is not so much into sports, but loves chess and video games. When I was younger, I was also into music, mostly writing songs on piano and guitar.

Are the lectures solid?
I guess you'll form your own opinion on this as the semester goes on, but my answer would be that they are more liquid than solid. I definitely start with some structure in mind and try to design lectures that follow a coherent story, while covering the ideas I think are more worthwhile and interesting, but am also flexible in going off on tangents based on student questions or things that come up, and not worried if I don't finish everything that was planned for a class.

Class 13: TLS Everywhere!

 29 Feb 2024 

Schedule

Enjoy Spring Break!

Our next class will be Tuesday, 12 March, and will be an “Ask Anything” day. Think of any questions you want to ask, and I’ll try to answer them.

Slides

Class 13: TLS Everywhere!

  • Happy Leap Day! [leapday.xlsx]
  • Project 2: Responding to Search Requests
  • Desining Transport Layer Security
  • Certificates
  • How TLS became used everyhwere

TLS Worksheet

Computer Science Grad Stands Watch for Users of Google’s Popular Browser. UVA Today, 7 December 2015.

Google’s Chrome Hackers Are About to Upend Your Idea of Web. Wired, 3 November 2016.

Let’s Encrypt Statistics

Update: Make sure you fill up your tank before leap day: Self-pay gas station pumps break across NZ as software can’t handle Leap Day, Ars Technica, 29 February 2024.