LEAD 2011 Curriculum - University of Virginia

LEAD 2011 Curriculum - University of Virginia

Instructors:

Ryan M. Layer,

Mark S. Sherriff,

Paul Reynolds,

Michael Skalak,

Luther A. Tychonievich,

Westly Weimer,

The goals of the 2011 LEAD Computer Science Institute at the University of Virginia were to instill excitement in students about computer science and to provide students with a solid foundation in a production-level programming language, Python.

We believe the best way to excite students about computer science is to help them make the connection between real world problems and the software they can write to solve those problems. To make this connection, we developed a curriculum that pairs active learning with programming topics. Rather than tell students about the problems software can solve, we wanted them to experience situations where the problems were important and feel the need for a better solution. For example, we used cryptography to teach the programming concept of strings. In the first lesson, students learn about the evolution of cryptography from Roman battlefields to Internet privacy. Next, students completed in a campus-wide scavenger hunt that required them to crack ciphers by hand. Finally, students were taught how to use Python strings as a tool to help encode and decode messages programatically.

We selected the Python programming language because we believed it balanced accessibility and power. The interactive command shell allowed students to dive directly into programming without the added complexities of editors, interpreters, and environment setup. The students easily moved from typing short commands in the shell to writing programs in text files as the commands became too long for comfortable shell use. One cause for confusion we continually found with our class with Python is the use of tabs as block delimiters. While a good editor can make this issue more manageable, it was a constant source of syntax errors.

Our 2011 class had 25 rising high school sophomores and juniors from seven states. A large majority of the students identified themselves as having no or very little programming experience, a small portion had experience with HTML, and two students had a working knowledge of at least one programing language. For three weeks, our students lived in on-campus dorms, attended classes, went on field trips, and completed nightly homework assignments. Their typical day consisted of two three-hour classes and a two-hour study hall session. In total, students attended 21 classes, which had a comparable number of contact hours to a two credit hour college course. Students worked in small groups on a final project and presented their work to a representative from Google on the last day of the program.

A summary of our lesson plan is given below with programming topics in parentheses.

1. Problem solving and Python basics (Integers, decimals, variable, memory model)
2. More Python basics (importing, turtle graphics, functions, loops, logical operators)
3. History of Encryption
4. Cryptography scavenger hung
5. Cryptography programming (characters, strings, string methods, cipher/de-cipher methods)
6. History of GPS
7. GPS coordinate gathering (file reading, parsing, coordinate graphing)
8. Internet history and networks (sockets, network chat)
9. Introduction to Artificial Intelligence (random numbers)
10. High performance computing and parallel programming
11. Traveling salesman problem
12. Package delivery chase (lists, lists of lists)
13. Accessing Online APIs (dictionaries, GET HTTP requres, web API)
14. Fundamentals of Game Programming I (pygame, infinite loops, events, dictionaries)
15. Fundamentals of Game Programming II
16. Mathematical Game Theory
17. Simulation and scientific exploration
18. Human-Computer Interaction
19. Graphs and Search (iterators, multilevel dictionaries)
20. Project/presentation help
21. Presentation dry run

Individual Lesson Descriptions

1. Problem solving and Python basics (Integers, decimals, variables, memory model)

We began with a lesson on problem solving by posing the question, “In a room of 25 people, how many handshakes occur if everyone shakes hands once?” In this case the first guest, that 25 people give 24 hand shakes, double counts each handshake. We explain how to simplify the problem, and propose a number of solutions. For each solution, we talk about how many steps it would take if there were 1, 10, and 10000 people. Next we installed Python and started using the interactive shell. We introduced them to integers and decimals, and the different operators for each type. Then we introduced variables, with a heavy emphasis on the memory model: variables are names for memory locations where values are stored.

2. More Python basics (importing, turtle graphics, functions, loops, logical operators)

We introduced the idea of importing modules, methods, and arguments with the turtle package. Students were asked to draw squares of different sizes. Once they realized that each square consisted of the same commands with a different value, we taught them to write methods. At this point we moved away from the interactive shell and into a simple development environment. Next we asked them to write methods for a triangle, pentagon, etc. Again, we taught loops once it became clear that the same commands were used, just different numbers of them. With the loops, the students were able to write a general polygon drawing method. We introduced logical operators so that polygons could be drawn in different colors depending on the number of sides.

3. History of Encryption

The lesson began with a history of encryption from Caesar through modern public/private key schemes. We explained in detail how ciphers work, and worked as a class on several ciphers by hand (Caesar, Vigenere, Pigpen, etc). Students were then asked to creating their own encryption scheme using a deck of playing cards. Each group encoded a message in a deck, and had to decode another group’s message from that group’s deck.

4. Cryptography scavenger hung

Students participated in a campus-wide scavenger hunt using what they learned about ciphers in the previous encryption lesson. Small groups of students were asked to solve a series of clues that were encrypted using a number of different simple ciphers. Each cipher provided a clue to the final puzzle.

5. Cryptography programming (characters, strings, methods, cipher/de-cipher methods)

After breaking a number of ciphers by hand in class and in the scavenger hunt, we taught students how perform the a similar task with a simple computer program. Students learned about characters, ASCII, strings, and string methods. Those topics were combined with loops to write a simple transposition cipher method. To make their programs more interactive, we introduced keyboard input methods.

6. History of GPS

Similar to cryptography, the lesson began with the history of global positioning through the use of astral bodies and the algorithm for using sextant. We moved forward to the use of GPS and compared and contrasted the two. We discussed the various uses for GPS and how GPS technology has changed our lives. To demonstrate modern GPS, we distribute GPS devices and toke students around the nearby area taking coordinates and doing a short exercise in calculating the distance between points.

7. GPS coordinate gathering (file reading, parsing, coordinate graphing)

Students used Android-powered smart phones to collect coordinates from around campus. Each group was given a set of buildings and found the coordinates of the buildings’ corners. From the Android phones, students used email to transfer the coordinates to their computers. We used the coordinate files to teach Python file reading and parsing, and points were graphed using turtle graphics. We collected the files from all the groups to show how a basic map could be constructed.

8. Internet history and networks (sockets, network chat)

We gave an overview of the architecture and structure of the Internet, it's history, and evolution. We then we discussed the basics network communication including packet switching, protocols, IP addresses, and ports, and demonstrated these ideas using packet sniffing, ping, and trace route. Using Python sockets, we wrote a small program where a server displayed a message sent from a client. This we expanded to chat program using keyboard input.

9. Introduction to Artificial Intelligence (random numbers)

We discussed what AI means as a computer science field. Then we introduced the students to random number generation, and wrote simple pattern finding program to determine randomness. We discussed explore/exploit trade offs in a 2-arm bandit problem.

10. High Performance Computing and Parallel Programming

Students were introduced to high performance computing: what it is, what it is used for, and how fast it is. We also discussed the TOP 500, the parts of a supercomputer, and took students on a tour of the university research cluster. Students participated in a basic overview of parallel programming and queuing system submission

11. Traveling salesman problem

The traveling salesman problem is introduced as both a historical problem, and one that we must solve everyday. We discussed how it is easy for humans to look at a simple problem and find an optimal solution, but developing an algorithm is difficult. Graphs were introduced, where nodes are cities and edges are distances, and we worked through several possible solutions. Students were divided into groups to develop their own algorithms. As a class, we tested a few solutions on examples different from the ones used in development.

12. Package delivery chase (lists, lists of lists)

Students competed to find the optimal delivery route for a dynamic scheduling problem. Students were split into small groups and each group was given an initial set of deliveries. At each delivery location, they were given an additional set of deliveries to make, and had to adjust their route accordingly. Teams used Android-powered smart phones to track their route. After the chase ,we analyzed each groups coordinate file to find which group had the shortest route. We used Python lists to represent latitude and longitude coordinates and lists of lists to represent paths.

13. Accessing Online APIs (dictionaries, GET HTTP requests, web API)

To demonstrate how existing resource can be used in their own programs, we taught the students how GET HTTP requests work, and how to read web API descriptions. Students used these to access Google's static maps, walking directions, and distance APIs using both GPS and address data. Students were introduced to Python's dict datatype, and the json and urllib standard libraries. They used these, together with their existing GPS files from previous lessons, to overlay their previous path on top of Google maps.

14. Fundamentals of Game Programming

We introduced the core ideas of interactive games using the example of the 1982 Joust video game. After installing the pygame library, we worked out way up using extreme programming from a very simple window through a full interactive game, with sprite animation, collision detection, event loops, and keyboard and timer events. We discussed gravity, drag, scoring, and the use of functions to simplify existing code. We modeled extreme programming in the classroom, always keeping a working program built. After each new topic was discussed, we first refactored our old program, re-tested it, and then added in the new element. The end result was a working two-player version of the Joust game.

15. Fundamentals of Game Programming II

A continuation of lesson 14.

16. Mathematical Game Theory

We started with a lesson on mathematical game theory, binary numbers, and abstract reasoning. The focus was on two-player impartial games of perfect information, such as Nim. Students then learned about binary numbers, binary XOR, and used them to compute the value of an impartial game and the winning strategy. Students completed worksheets on two's complement binary encoding as well as binary XOR (which is used to compute the Nim-sum of an impartial game and thus to find the winning strategy). Students also performed demos of finding the winning strategy for a given game using techniques learned.

17. Simulation and scientific exploration

We started with a background on simulation, what it is, and its exponentially growing use. We used queuing systems as a working example to motivate and to demonstrate the risks associated with using intuition alone. Practical examples for simulations included: planning for storage of America's nuclear wastes, replacement of clinical trials, and war planning. We explained fundamentals of discrete event simulation, and engaged students in an active participation contest relating to efficient queuing methods. To demonstrate these topics students used the Java Modeling Tool (JMT) and SimPy.

18. Human-Computer Interaction

We gave an overview in how we as humans interact with machines, and discussed various HCI design patterns and what the idea of a pattern is. We reviewed rules of good HCI design, and demonstrated many different interface devices. Students used DroidDraw to create a user interface for a particular application, such as a parking finder or to-do list. In preparation for their final projects, students storyboarded a design for their projects.

19. Graphs and Search (iterators, multilevel dictionaries)

Our final lesson was on advanced algorithms including graphs, traveling salesman, and permutations. We wrote a brute force TSP algorithm for complete graph, and discussed heuristics verses exact algorithms. As a class, we developed and tested several different heuristics for TSP, then applied the pathfinding techniques used in GPS systems.

20. Project/presentation help

Students had a free period to work on their projects and prepare for their presentations.

21. Presentation dry run

All student teams were given feedback by the group during practice runs of their presentations.