Data structure lectures

CSE Home

CSE 326

Classroom Presenter

About Us

Search

Contact Info

Lectures  Hashing, Nov 12  Huffman Coding, Nov 24

Data structure lectures This term, I gave two lectures in CSE 326. Both of these lectures were designed for presentation using the Tablet PC. The lecture slides were constructed to take advantage of digital ink. I consider both lectures to have been very successful: students were engaged and interactive, and I covered the material I planned. The course text was Lewis and Denenberg. The lecture material was drawn from the text, although the material was reworked substantially to get it into presentation form. The Classroom Presenter system was used in lecture delivery. The lecture slides were prepared in PowerPoint, using Classroom Presenter instructor notes and TexPoint. Hashing lecture This lecture was delivered using Classroom Presenter connected directly to the projector. No explicit introduction was given to the tool, although early in class a student comment about using ink with PowerPoint, and I explained this was a UW developed system. My goal was to make the ink use as natural as possible. The topic of the lecture was Open Address Hashing. In the previous lecture, Martin had chaining. I began the lecture with a brief review of chaining for resolution of collisions, and then did an example where I hashed student birthdays - requesting birth dates from students. Martin had suggested this example, and it fit very will with a template. Open hashing was introduced using the parking analogy, and then another example was done. The example was used to illustrate the problem of clumping. On the slide with the lookup code, and question was answered with respect to deletion (anticipating a later point). Double hashing was then introduced, with a diagrammatic illustration, and a modification of the code for open address lookup. Finally, an example was done using birthdays again, but using the month as a secondary has function. This worked well, although the dates had fewer collisions than one might expect (so a later entry was faked to force a collision). An instructor note was used to remind me to record the months by number. The performance summary of single vs. double hashing was done using a template with the x-y axis, the students did not see that I had curves to trace as the instructor notes. The discussion on open hashing was finished using a template for collective brain storming about tradeoffs between open addressing and chaining. The remaining portion of the lecture was a very quick discussion of different methods of constructing hash functions. The discussion compressed the material on the slides, and the last couple of slides were not shown. Huffman Code lecture I designed the Huffman Code lecture to incorporate "student submissions". For Student Submissions, students have copies of the slides, and are asked to write answers to exercises on the slides, and send them back to the instructor. THe instructor receives the annotated slides, and has the ability to select and display these slides on the public screen. The goals of including student submissions are engage the students, and to give the instructor feedback on student understanding. This was my first experience using student submissions in a real class. I created lecture slides with four planned exercises. The lecture naturally broke into three sections: 1) Introduction to codes, 2) The Huffman Algorithm, and 3) An Induction Proof of correctness of the algorithm. The correctness proof is elegant, but subtle. The exercises were included in the first two sections of the lecture. One of the main goals of the lecture was to convey the algorithm to the students, so that they could apply it to construct codes given data. Not only was this the central topic of the lecture, but proceeding to a proof of correctness without class wide understanding of the algorithm would be futile, so I wanted verify that the majority of students were comfortable with the algorithm before launching into the proof. The class was set up in CSE 305 (the distance learning classroom in the CSE building, not the regular classroom). HP TC1100 Tablets were deployed in the classroom, running the current version of Classroom Presenter (1.9.96). A wired network was used (since the tablets were also connected to power, the presence of internet cables were not noticed). Approximately 20 students participated in the class. There were no technical problems during class. The Tablets were set up in a slate mode, and the Classroom Presenter application was running with the lecture slides when the students arrived. Students began to arrive about 10 minutes before class, and started playing with the Tablets. Almost all students were present at the start of class. A brief introduction was given about student submissions (and previously, email had been sent to class describing what was planned). A first submission exercise was done as an introduction - "write your name on a slide and submit it". I then started talking about binary codes, and on the second slide gave two decoding problems, one to test understanding of basic decoding, and the other to show an ambiguous code. This led into a discussion of prefix codes and a student exercise where students built the tree representation of a code. The lecture material fit very well with an ink based presentation style - for example, the lecture slide to show the correspondence between codes and trees had an unlabeled tree for the code, and the code words were added with ink. The tree construction submission was an ideal one to do with ink - it would have been difficult to express the tree just using the keyboard. The next idea was computing the average length of a code - an exercise had been planned - but it seemed too mechanical, and class was a little behind schedule, so I just worked it myself, and did not have students do it. I then introduced the main algorithm, this was done by motivating the key idea, then working an example, and finally showing the code. The example was drawn on a slide, building subtrees from the bottom of the slide, and marking off a list of items that had been used. It was helpful to have done this example in advance - to know where to draw the subtrees. Quite a bit of discussion was generated by working the example. An example was then given to students, who worked it along similar lines, and submitted it. The majority of students seemed to get the construction correct, with a positive, and a negative example being shown to the class. The final portion of the class was to give the main induction proof. This was based upon the proof in the text. I did not come up with a good assessement exercise to relate to the proof, so it was done "presentation only". My assessment is that the class was successful. The technology worked well, and students were engaged in the lecture. The student submission exercises got essentially full participation. I did not see much evidence of students being distracted because of the tablets - there was some exploration and playing with them - but it was not a serious problem. Students were able to figure out how to use the tablets with limited instructions (issues such as locating the pen were quickly solved with help of other students). Three submission exercises was a good number for the hour - the type and timing of the exercises were appropriate. On the instructor sides, there are a number of UI issues to resolve in working with student submissions - some of these are just fixes to the Presenter interface, and others relate to summarization and visualization of the incoming results.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to anderson@cs.washington.edu]