CS 240: Lecture 32 – Hashing, Part 1
Dear students: This course is really a marathon of one-upping. We introduce a data structure only to knock it down with the next one. And then we knock that one down when we introduce a third. Let’s do it again. Consider the problem of searching for something in a collection. With a plain array, we […]
CS 240: Lecture 31 – Huffman Coding
Dear students: Imagine you speak a language whose alphabet consists of just these five characters: F G O – ! With this alphabet, you say things like FOOO!, GOOO-FOO!, and FOGOFOGO-OOOOO! Your scientific and literary communities have used this alphabet to generate zettabytes of documents, and you have been hired to digitize all of these […]
CS 240: Lecture 30 – Heaps
Dear students: One of the most challenging things about this course is that you are asked to learn about things before you feel that you need them. I wish I knew how to fix that. We have so very little time in which to make learning happen. That said, we have a new abstract data […]
CS 347: Lab 18 – Acrostic
Dear students: Welcome to lab. Now’s your chance to apply the ideas you read about. Find a partner and complete as much of the task below as you can. At the end of our time together, paste your files into Crowdsource in order to receive credit. Task 1 Reverse engineer the following app using React: […]
CS 240: Lecture 29 – Red-black Trees
Dear students: AVL trees are one solution to the problem of balancing binary search trees. They do an excellent job of minimizing the height. Humans have continued to invent other self-balancing trees that occasionally beat out AVL trees. The red-black tree, for instance, tends to have cheaper insertions because it is not as sensitive to […]
CS 240: Lecture 28 – Binary Search Tree Lab
Dear students: Today we will devote our entire time together to a lab on binary search trees. Follow these guidelines: You may work with one other person. If there’s an odd number of people, one group of three is permitted. Upload the required files to Autolab. Run the Autolab tests as often as you’d like. […]
CS 240: Lecture 27 – AVL Trees
Dear students: Last time we introduced a special case of binary trees in which the left descendents are all less than their root and all the right descendents are greater. Such a tree holds the binary search in its bones. The binary search is fast, right? We like that. To get that speed, we need […]
CS 347: Lab 17 – Follownet Client
Dear students: Welcome to lab. Now’s your chance to apply the ideas you read about. Find a partner and complete as much of the task below as you can. Actually, today’s lab is entirely optional. We’ll make it a workday for your project. But here’s an exercise in case you really want one. Task 1 […]
CS 347: Lab 16 – Follownet
Dear students: Welcome to lab. Now’s your chance to apply the ideas you read about. Find a partner and complete as much of the task below as you can. At the end of our time together, paste your files into Crowdsource in order to receive credit. Task 1 Create a database with two tables. The […]
CS 240: Lecture 26 – Binary Search Trees
Dear students: Fall break is over. Just four more weeks to the next one. And then two more weeks of the semester after that. Then finals. Then whew. In the weeks that we have left we’ll be talking about trees, dictionaries, hashing, and graphs. The good news is that these are all useful tools. The […]