PYI: On-Line Problems and the Amortized Analysis of              Algorithms
{'Code': '05010100', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Dana S. Richards', 'PO_EMAI': None, 'PO_PHON': None}
On-line problems are extremely common in computer science and                   operations research.  For these problems an algorithm must be                   devised to decide how to respond to a request immediately                       when the request is made, without knowledge of future                           requests.  Some familiar examples of on-line problems are:                      Controlling an elevator, controlling a disk drive,                              controlling caches, and data structures.                                                                                                                        An extremely powerful technique in the design and analysis of                   algorithms for on-line problems is that of amortization.  In                    an amortized analysis, the cost of a sequence of requests is                    considered rather than the cost of each request individually.                   Algorithms efficient in the amortized sense balance the costs                   of expensive requests by inexpensive ones.  A variety                           of new amortized-efficient algorithms and data structures                       have been devised.                                                                                                                                              For many on-line problems there are on-line algorithms with                     amortized performance that is almost as good as the                             performance of any off-line algorithm on any sequence of                        requests.  Such an on-line algorithm is said to be                              competitive.                                                                                                                                                    The PI is applying known techniques of amortization and                         competitiveness to a variety of other on-line problems, and                     developing new techniques for doing amortized analysis.                                                                                                         The PI has been judged to be an outstanding computer                            scientist by the Presidential Young Investigator panel.
{'FirstName': 'Daniel', 'LastName': 'Sleator', 'PI_MID_INIT': 'D', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Daniel D Sleator', 'EmailAddress': 'sleator@cs.cmu.edu', 'NSF_ID': '000309743', 'StartDate': '08/01/1987', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Carnegie-Mellon University', 'CityName': 'PITTSBURGH', 'ZipCode': '152133815', 'PhoneNumber': '4122688746', 'StreetAddress': '5000 FORBES AVE', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'Pennsylvania', 'StateCode': 'PA', 'CONGRESSDISTRICT': '18', 'CONGRESS_DISTRICT_ORG': 'PA18', 'ORG_UEI_NUM': 'U3NKNFLNQ613', 'ORG_LGL_BUS_NAME': 'CARNEGIE MELLON UNIVERSITY', 'ORG_PRNT_UEI_NUM': 'U3NKNFLNQ613'}
{'Name': None, 'CityName': None, 'StateCode': None, 'ZipCode': None, 'StreetAddress': None, 'CountryCode': None, 'CountryName': None, 'StateName': None, 'CountryFlag': None, 'CONGRESSDISTRICT': None, 'CONGRESS_DISTRICT_PERF': '""'}
[{'Code': '2860', 'Text': 'THEORY OF COMPUTING'}, {'Code': '9145', 'Text': 'SPECIAL PROGRAMS-RESERVE'}]
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1986&All=true', 'xml': '8658139.xml'}