Where Dreams and Reality Intersect!
Bushra Anjum, HLF13 participant: The admission season for the university has arrived, and with that comes newly printed crisp university prospectus. B lazily grabbed a copy of the new prospectus of the university where she teaches as an Assistant Professor in the Department of Computer Science. As she was sifting through the pages of the prospectus, the particular page depicting the map of the required and elective courses for the undergraduate CS program caught her attention. B looked at the course map for a few seconds and then closed her eyes. Different names, references, events surfaced in her mind from the 12 years of her education in the CS field and started playing like a movie.
Introduction to Computer Science: Of course everything starts from here. The first computer system that we would recognize today as a personal computer was ALTO (made in 1973) with only 2.5Mbit disk and 6 MHz processor! ALTO computer, envisioned by Butler Lampson and designed by Charles P. Thacker, needed a method for interacting with it. To help with this, Alan Kay and the members of his lab created graphical interfaces and the Smalltalk programming language. SmallTalk was the first dynamic object-oriented programming language.
Algorithms: John Hopcroft and Robert Tarjan recognized that as computers became faster and worked on larger problems, the most important part to understand was the growth rate of the running time as the input gets larger. His focus on this “asymptotic complexity” set the direction for the new field of analysis of algorithms. Soon, the complexity of an algorithm was based on the number of steps required, as a function of the input size, for the algorithm to solve a problem. In 1965 Juris Hartmanis and Richard Stearns defined a complexity class as the set of all problems solvable within a specified time bound (for example, problems for which the fastest algorithm takes a time proportional to n, n log n, n2, n3, 2n, and so on)
Data Structures: Robert Tarjan realized that designing a data structure to minimize the worst case running time for each operation was unnecessarily limiting; what mattered was the total running time of the sequence of operations. Alternatively, from the point of view of the data structure, one could study the algorithm’s amortized running time, that is, its average running time per operation over a long enough sequence of inputs. Hence Tarjan devised the Fibonacci heap, in 1985, which provided significant speed-ups to several important combinatorial problems including minimum spanning tree, shortest paths, and the assignment problem.
Databases: The crucial invention, operational by 1963, was William Bachman’s Integrated Data Store (IDS). IDS maintained a single set of shared files on disk, together with the tools to structure and maintain them. IDS provided application programmers with a set of powerful commands to manipulate data, an early expression of what would soon be called a Data Manipulation Language.
Computer Architecture: Frederick Brooks lead the team at IBM to design this product line, called the System/360, which was announced in 1964. Brooks coined the term “computer architecture” for the first time, which means the structure and behavior of computer processors and associated devices, as separate from the details of any particular hardware implementation. IBM System/360 was a huge success.
Software Engineering: 1964, while the hardware architecture for the System/360 was well underway, it was clear that there was considerable risk in delivering the operating system for the new series of machines. Brooks was assigned to lead the software team in building what was perhaps the largest operating system project of its time. Brooks describes the lessons he learned in his classic text on software engineering, The Mythical Man-Month. It is from that experience that Brooks proposed “Brook’s Law”: that “adding manpower to a late software project makes it later.”
Theory of Automata: 1972, a paper by Stephen Arthur Cook marked the introduction of the theory of NP-completeness, which henceforth occupied a central place in theoretical computer science. Cook’s paper addresses the fact that many problems which are difficult to solve have solutions which are easy to verify once they are found. Cook’s paper had an immediate impact. In 1972 Richard Karp published a paper in which he showed that twenty-one problems in combinatorics, optimization and graph theory which were believed to be computationally difficult were indeed NP-complete.
Computer Networks: In the spring of 1973, Robert Kahn and Vinton Cerf considered the idea of developing a system for interconnecting networks—what would eventually be called an “internet.” Cerf and Kahn outlined the resulting Internet architecture in a seminal 1974 paper, A Protocol for Packet Network Intercommunication, thus laying foundation of the TCP/IP protocol suite.
B opened her eyes with a smile on her face. A smile hinting at accomplishment and a smile full of expectation. She knew that soon, very soon, her dreams and reality will intersect
My dear reader, all the names mentioned above are of the esteemed Turing Award winning laureates who will be in Heidelberg from 22nd to 28th September attending the first Heidelberg Laureate Forum. The Laureates will be meeting and interacting with 200 young PhDs from around the world imparting knowledge, wisdom and inspiration and B, your author, has been selected as one of those 200 attendees.
Looking forward to the most anticipated and celebrated time of my life,
* Due to space considerations, this blog mentions only some of the esteemed guests attending the forum.
Bushra Anjum was born in Lahore, Pakistan from where she received her Bachelor and Master’s degree in Computer Science. She then moved to USA on Fulbright Scholarship and completed PhD (CS) from North Carolina State University (NCSU), Raleigh in 2012. Since then she has moved back to her home country and is an Assistant Professor in the Computer Science Department at the National University of Computer & Emerging Sciences, Lahore, Pakistan. She has authored scholarly papers in the areas of performance modeling, computer networks, and quality of service provision. She enjoys photography, buying shoes and playing every social game Zynga has ever introduced!