Computer Laboratory – Course material 2008–09: Additional Topics Skip over navigation | Access key help ||| Computer Laboratory Course material 2008–09 Computer Laboratory > Teaching > Course material 2008–09 > Additional Topics Additional Topics Advanced Graphics Advanced Systems Topics Algorithms I Algorithms II Artificial Intelligence I Artificial Intelligence II Bioinformatics Business Studies Comparative Architectures Compiler Construction Complexity Theory Computation Theory Computer Design Computer Graphics and Image Processing Computer Systems Modelling Computer Vision Concepts in Programming Languages Concurrent Systems and Applications Databases Denotational Semantics Digital Communication I Digital Communication II Digital Electronics Digital Signal Processing Discrete Mathematics I Discrete Mathematics II Distributed Systems E-Commerce ECAD ECAD Labs » Economics and Law Floating-Point Computation Foundations of Computer Science Foundations of Functional Programming Group Project Group Project Briefing Hardware Practical Classes How to Study Computer Science Human-Computer Interaction Information Retrieval Information Theory and Coding Introduction to Security Logic and Proof Long Vacation Java course Mathematical Methods for Computer Science Natural Language Processing Operating Systems I Optimising Compilers Part IB Assessed Exercise Briefing Probability Professional Practice and Ethics Programming Methods Programming in C and C++ Programming in Java Prolog Quantum Computing Registration Regular Languages and Finite Automata Security Semantics of Programming Languages Software Design Software Engineering Specification and Verification I Specification and Verification II System-on-Chip: Design and Modelling Topics in Concurrency Types Unix Tools Additional Topics 2008–09 Principal lecturer: Prof Andy Hopper Taken by: Part II Syllabus Past exam questions Course Details The lectures this year are 12:00-13:00 in Lecture Theatre 2 of the CL. Note that time of 10:00-11:00 as advertised in the reporter is incorrect (it had to be moved due to a clash of lecturers!). The schedule is as follows: Friday 24/04 Ubiquitous Computing (Robert Harle) Monday 27/04 RFID (Robert Harle) Wednesday 29/04 GPS (Alan Jones) Friday 01/05 Location Determination Part I (Robert Harle) Monday 04/05 Location Determination Part II (Robert Harle) Wednesday 06/05 Cryptography (Frank Stajano) Friday 08/05 Security for UbiComp (Frank Stajano) Monday 11/05 Security for RFID (Frank Stajano) Wednesday 13/05 Thin Client Computing Part I (Andy Harter) Friday 15/05 Computing for the Future of the Planet (Andy Hopper) Monday 18/05 Sustainable Energy (David Mackay) Wednesday 20/05 Thin Client Computing Part II (Andy Harter) Electronic copies of notes, links and other material will appear here as the lectures are completed. Lecture 1: Ubiquitous Computing What you need to know: The ubicomp vision in 1988; Context-aware computing; Example projects and lessons learnt (active badge, PARC, Intel Personal Server, Wearable Computing, Sentient Computing); Ubicomp today. Lecture Notes: PDF Reading: Yesterday’s tomorrows: notes on ubiquitous computing’s dominant vision. Bell and Dourish. PDF The Computer for the 21st Century. Weiser. PDF A distributed Location System for the Active Office. Harter and Hopper. PDF The Anatomy of a Context-Aware Application. Harter, Hopper, Steggles, Ward and Webster. PDF The Royal Society Clifford Paterson Lecture, 1999 - Sentient Computing. Andy Hopper. PDF The PARCTAB Ubiquitous Computing Experiment. Want, Schilit, Adams, Gold, Petersen, Goldberg, Ellis and Weiser. Link. Questions: 1A. Contrast mobile computing with ubiquitous computing. [5] 1B. It has been suggested that the Apple iPhone was the first major ubicomp device. What are the properties of the iPhone that resulted in this description? Discuss how well the iPhone fits the original vision for Ubicomp. [10] 1C. Describe the "programming with space" metaphor that enabled location-aware computing in the Sentient Computing platform. [5] 1D. The Intel Personal Server project proposed a wireless device that would connect to public infrastructure to provide input and output. Discuss the technical, commercial and social issues associated with such a device. [10] 1E. Weiser's original vision for ubicomp has not been met within the timescale he suggested (20 years). Suggest why not. [8] Lecture 2: RFID What you need to know: Types of RFID; Active vs Passive; Properties and applications for close-coupled, remote-coupled and long range RFID; Principles of back-scattering; Basics of EPC; Anti-collision protocols for LR tags; Technical, real-world issues with LR tags Lecture Notes: PDF Reading: RFID Handbook. Klaus Finkenzeller Available in libraries. Some chapters online Questions: 2A. Give two example applications for long range RFID tags. One application should be suitable for active LR tags, the other for passive. [4] 2B. The media regularly attack the security and privacy associated with RFID tags. And yet the banks are all turning to RFID-based contactless payment cards. Why do they not share the same security issues? 2C. Why are longer range passive RFID tags associated with higher frequencies of operation? 2D. Why have we yet to see automatic checkouts where we push our trolley through the doors and have everything charged correctly? (It is not because products don't have RFID tags at the moment - these could be added very quickly to products, if desired). 2E. How do probabilistic anti-collision schemes work? Suggest applications where they might be more suitable than deterministic schemes. 2F. Write out the rounds required to identify the following tags using a binary search: {11010, 01010, 00101, 11000} 2G. An RFID system contains N tags and uses a simple ALOHA anti-collision protocol. Tags are constrained only to transmit a packet with a probability of p within each time period T. (a) Write down the expected number of transmissions in time T and hence an expression for P(k), the probability that there will be k transmissions in time T (b) Give an expression in terms of T for the vulnerable period (this is the length of time during which a transmitting packet will collide with a specific packet). What would this period be for slotted ALOHA? (c) From these answers, compute the probability that a given tag transmission will not collide and hence the expected throughput (number of tags per time T). Lecture 3: GPS What you need to know: GPS components; Basic operating principles; Error sources; DGPS; Selective availability; The notion of Gold codes and how they are used. Reading: Recommended Site: Here More detailed information (including offical docs): Here Questions: 3A. Why do GPS satellites require atomic clocks? Why doesn't it matter that GPS handsets don't have an accurate absolute time estimate? [6] 3B. Explain the principles of D-GPS. [5] 3C. What are the important properties of Gold codes that make them useful for GPS? How is it that a GPS signal so weak it is below the noise threshold at the receiver is still useful? 3D. Although intended for positioning, GPS is commonly used to accurately synchronise clocks to a global reference time. Explain how a handset on the surface of the Earth can compute an accurate absolute time from a GPS satellite. Estimate the timing error that might be expected at the handset immediately after synchronization to a satellite. Lectures 4 and 5: Location, Location, Location What you need to know: The principles of AoA, ToA and TDOA location; Examples systems of each; Basics of Inertial navigation; Fingerprinting. Lecture Notes: PDF Questions: 4A. Briefly explain why the Bluetooth inquiry (a.k.a. discovery) process takes so long (10.24s) and why this limits its use as a proximity-based tracking system. 4B. Compare and contrast location systems that position a mobile transmitter (e.g. the Bat system, U-TDOA) with those that position a mobile receiver (e.g. GPS, Cricket). [6] 4C. Explain why UWB systems can achieve better positioning accuracy than more traditional radio location systems. [5] 4D. A transmitter located at (15,20) is surrounded by synchronised receivers: A at (0,50), B at (5,0), C at (30,30). For this setup, give the equations of the vectors, circles or hyperbolae associated with the i) AoA ii) TOA and iii) TDOA location techniques. Assume all measurements have no noise (and are therefore perfect) and receivers are perfectly synchronized. [8] 4E. Imagine that your GPS signal is being jammed by an enemy transmitter. In order to unjam it, you need to first locate the source. Describe how you would do this. [Remember that you can't use GPS to position your receivers!] 4F. Explain why the Ubisense system makes use of UWB radio rather than, say, the usual 2.4GHz ISM radio band. Why do we not need to use UWB signals when positioning outdoors? 4G. What factors might you need to take into account if you were creating a WiFi radio map? 4H. Discuss the advantages and disadvantages of using radio fingerprints for positioning. 4I. The Nintendo Wiimote was apparently intended to be based purely on inertial sensors. Explain why inertial sensors alone were insufficient and describe briefly the solution implemented by Nintendo. 4J. What do you need to specify in order to create a useful tracking system from an inertial measurement unit? 4K. Imagine that you are tasked with designing an iPhone-like device that must be able to position itself at all times. Discuss the solutions you would use and the accuracies you might expect indoors and out. Lecture 6: Cryptography What you need to know: basics of visual cryptography; Cocaine auction; Romantic cryptography Lecture Notes: Here Questions: Exercises can be found in the notes Lecture 7: Security for Ubiquitous Computing What you need to know: basics of visual cryptography; Cocaine auction; Romantic cryptography Lecture Notes: Here Questions: Exercises can be found in the notes Lecture 8: Security for RFID What you need to know: Limitations of RFID as a secure ID mechanism; Schemes to improve RFID security and privacy Lecture Notes: Here Lecture 9: Thin Client Systems Part I What you need to know: Definition of thin client Lecture Notes: Here Questions: 9A. Give three advantages and three disadvantags of thin client systems. 9B. How did advances in memory technology lead to better graphics on computer screens in the 1980s? 9C. Describe the different roaches used to remote bitmap graphics by VNC, X and RDP. Lecture 10: Computing for the Future of the Planet What you need to know: Ways in which technology might create a sustainable future. Lecture Notes: Coming soon Questions: 10A. The lectures identified four ways in which computing might be applied to sustainability issues. Describe them. 10B. Discuss three technical and three political/social challenges to "googling space-time". 10C. Is the vision for ubicomp (many devices, always on, interacting) fundamentally incompatible with a sustainable future? Illustrate your answer with examples. Lecture 11: Sustainable Energy What you need to know: The scale of the energy crisis; Sustainable sources of energy Lecture Notes: You can find Professor Mackay's entire book online: WithoutHotAir.com. The talks section also contains the slides used in the lecture. Questions: 11A. Discuss the extent to which modern computing technology is responsible for the current power demands of the UK. Lecture 12: Thin Client Systems Part II What you need to know: Lecture Notes: Here Questions: 12A. In the lecture about Ubiquitous computing, a scenario involving a user walking up to a public display and 'comandeeringing' it as an output device was presented. Discuss how remote bitmap graphics software (such as RDP and VNC) might act as an enabler for this application. 12B. Compare and contrast the RDP and VNC protocols. [6] 12C. A student implements a simple remote graphics protocol by regularly snapshotting the screen image and transmitting it over the network. Identify four optimisations that would significantly boost the performance of this protocol. 12D. Compare RDP, VNC and X for remote graphics over i) a LAN ii) a typical ADSL connection iii) a 3G connection. 12E. What is meant by 'cloud computing'? [4] © 2009 Computer Laboratory, University of Cambridge Please send any comments on this page to Prof Andy Hopper Last modified 2009-05-21 17:23 by Robert Harle
