Lead 2011 Curriculum University of Virginia Instructors

Ryan M. Layer, rl6sf@virginia.edu

Mark S. Sherriff, sherriff@virginia.edu

Paul Reynolds, reynolds@virginia.edu

Michael Skalak, mss6s@cs.virginia.edu

Luther A. Tychonievich, lat7h@virginia.edu

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
    

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

A continuation of lesson 14.

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.

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.

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.

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.

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