CMU trivia

CMU trivia

Jul 7, 2018. | By: Sophie

To prepare myself for next year’s SCS trivia and to demonstrate my school pride, I set up a one trivia a day challenge for myself. My plan is to continue this until I leave CMU. All the trivias will be related to CMU or Computer Science in general. This year’s SCS trivia night made me realize how little I know about female computer scientist, so I will focus more on this part.

I learned many of Computer Science related trivia from “Great Moments in Computing”, a great course offered at Princeton University taught by Professor Maragret Martonosi. Many CMU related trivias are learned by wandering in campus during work breaks. If you spot any mistakes in this post, please email me: hsqq at cmu dot edu

Hello, world!

March 23, 2018

Let the first trivia be our most familiar program, hello world.

Dr. Dennis Ritchie developed the language C, which he used to implement the operating system Unix with Ken Thompson. To educate people how to use C, Dr. Brian Kernighan wrote the textbook The C Programming Language and used the program hello world as an introductory example. This was the first apperance of the hello world program. Ever since then, most beginners’ first program in many languages have been some variation of:

main()

{

  printf("hello, world\n");

}

Dr. Brian Kernighan is now a professor at Princeton University.

MULTICS

March 24, 2018

Now I want to talk about Unix, the operating system developed with C. But before I can get to Unix itself, I want to briefly introduce its predecessor, MULTICS.

Before Unix, there was an operating system called MULTICS(Multiplexed Information and Computing Service), developed by MIT, GE, and Bell Lab and released in 1969. You can read the original paper here: Virtual Memory, Processes, and Sharing in MULTICS by Robert C. Daley and Jack B. Dennis. The main concepts introduced with MULTICS are Proccess and Address space. Quoting from the paper:

Processes stand in one-to-one correspondence with virtual memories. Each process runs in its own address space, which is established independently of other address spaces. Processes are run on a processor at the discretion of the traffic controller module of the supervisor.

These concepts are still prevalent today.

UNIX

March 25, 2018

Finally, UNIX.

The name UNIX stands for Uniplexed Infromation and Computing Service and it was suggested by Dr. Brian Kernighan in 1970. It was developed by Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas Mcllroy, and Joe Ossanna at Bell Labs. The design of UNIX is summarized in The UNIX Time-Sharing System and published in 1974, 6 years after MULTICS. I highly recommend reading this paper for it is a well-written paper and you will be able to understand how clever the system was designed so that its essence has not varied too much since its birth.

The 1974 version of UNIX contained only 11K lines of code for the kernel (for your reference, 2017 Linux kernel 4.1.38 contains ~5.4M lines of code). One of the biggest difference between MULTICS and UNIX is that data on MULTICS are stored in address, which allows random access, whereas in UNIX, data are stored in file, which is an abstraction that allows user to handle hardware, directories, and normal files in the same way be it random or sequential access.

Dr. Dennis Ritchie and Ken Thompson won Turing Award in 1983.

Alan Turing

March 26, 2018

Starting from today, I would like to talk about Turing Award, the most prestigious award in the field of Computer Science. But before I introduce any of Turing Award Winner, let me first talk about Alan M. Turing.

Dr. Turing received his Ph.D. from Princeton, where he spent only two years. Unlike some people who drop out from grad college after two years, Dr. Turing had earned his Ph.D. within those two years. One of Turing’s most famous contributions should be his Turing test, which he originally called “the imitation game” introduced in his paper MIND a quarterly review of psychology and philosophy in 1950, only 4 years after the birth of ENIAC. Turing is also known for his lambda calculus, co-developed with his Ph.D. advisor Alonzo Church, and Turing Machine.

Turing Award at CMU

A quick trivia.

05-25-18-turing

Alan Perlis, 1966.

March 27, 2018

I was going to say that before I introduce Turing Award winners from the earliest to the most recent, I would like to priotize those were or still are related to CMU. However, I just learned that the first Turing Award winner was the first head of our Computer Science Department at CMU, Alan Perlis!

Dr. Perlis made incredible amount of contribution to the field of computer science. He participated in the designing and building of some of the earliest electrical computers. He also helped design IBM 650. Together with Simon and Newell, he defined the term “computer science” to be “the theory and design of computers.” In 1961, he taught the first freshman-level computer science course in the nation at Carnegie Tech, which later merged with Mellon Institute to form CMU. In 1965, Computer Science Department was esablished and he became the first head.

Allen Newell and Herbert Simon, 1975.

March 28, 2018

Herbert Alexander Simon was a professor in Political Science. His insight of human decision making lead to his development of heuristic programming. Dr. Simon’s research interests are AI, simulation, software design, and HCI, all of which are still CMU’s strongest fields. Dr. Simon also won the Nobel Prize in Economics.

Dr. Newell earned his Ph.D. degree at CMU Tepper School advised by Dr. Simon. Together with his advisor Dr. Simon, they worked on heuristic programming and created the first AI program, Logic Theorist. He spent a year at Princeton where he worked on game theory which influenced his later work.

Newell, Simon, and Perlis created Computer Science Department together in 1965. The building, Newell Simon Hall, for Human Computer Interaction Institute and Robotics Institute is named after Dr. Newell and Dr. Simon.

Dana Stewart Scott and Michael O. Rabin, 1976.

March 29, 2018

Dr. Scott and Dr. Rabin jointly developed the idea of nondeterministic machines in the paper “Finite Automata and Their Decision Problem”.

Dr. Scott earned his BA at Berkeley and his Ph.D. at Princeton. After jumping around multiple top universities, in 1981, he came to CMU and became a professor of Computer Science, Mathematical Logic, and Philosophy. He took the position of Hillman Professor of Computer Science. Dr. Scott is also famous for his contribution to computer programming language analysis.

Dr. Rabin also earned his Ph.D. at Princeton in Mathematics. He is famous for his idea of adding randomness to algorithm. His later work concerns cryptographic problems and helped develop a zero-knowledge proof.

Robert Floyd, 1978.

March 30, 2018

Floyd received his Turing Award “for having a clear influence on methodologies for the creation of efficient and reliable software, and for helping to found the following important subfields of computer science: the theory of parsing, the semantics of programming languages, automatic program verification, automatic program synthesis, and analysis of algorithms.” Floyd did not get a Ph.D. However, he was appointed an associated professor at CMU when he was at the age of 27 and, six years later, became a full professor at Stanford University.

Ivan Sutherland, 1988.

March 31, 2018

Ivan Sutherland earned his Bachelors of Science Degree from CMU, which was Carnegie Institute of Technology back then. After he earned his Master of Science Degree from California Institute of Technology in 1960, he went to MIT where he worked with Dr. Claude Shannon and earned his Ph.D. within 3 years. His Ph.D. thesis “Sketchpad: A Man-machine Graphical Communications System” introduced Sketchpad, the first computer graphics software. Sketchpad was developed on the TX-2, which was one of the first transistor-based computers with core memory. To use the Sketchpad, one needs to hold a lightpen, which, instead of emitting lights as our mouses today, senses lights from the screen and determine the pointing location. The shapes drawn are stored like objects as in the notion of object-oriented programming with the capability of creating multiple identical but distinct copies and modifying each one of them separately. A demo by Dr. Sutherland can be found here: https://www.youtube.com/watch?v=57wj8diYpgY His work is considered to be the

Fun fact: Dr. Claude Shannon was the advisor of Ivan Sutherland and his older brother, Bert Sutherland.

D. Waitzman

April 1, 2018

D. Waitzman won some award (whatever it is) for his contribution in IP over Avian Carriers (IPoAC). It is originally described in A Standard for the Transimission of IP Datagrams on Avian Carriers. This system can in theory achieve 145.6Gbit/s transfer rate but the packet loss can be as high as 55%. Security is another weakness of IPoAC. Therefore, if you are concerned about packet loss and security issues, don’t use this method. Otherwise, it can be one of the fastest way of getting a huge amount of data transferred.

A friend of mine at Princeton once implemented a method that could transfer 1TB data within half an hour with 0 packet loss. He is not a student in computer science. He studies physics and mainly writes code in FORTRAN. His system is also highly secure with 0 information leekage - he drove to his lab and retrieved his hard drive.

Edward Feigenbaum and Raj Reddy, 1994

April 2, 2018

They won Turing Award for their contribution in building large scale AI systems.

Dr. Edward Feigenbaum is known as the father of Expert Systems. Dr. Feigenbaum earned is B.S. in Electrical Engineering at CMU where he took Dr. Simon’s course on Mathematical Models in the Social Sciences and got his first taste of computer science by studying Simon’s manual for IBM 701. After he earned his B.S., he continuted for a Ph.D. at CMU with Dr. Simon on building a model that simulates how human learn nonsense syllables. This model stores data with a decision tree, which he called Discrimiation Net. It is interesting to see how our founders research interests are still carried on by today’s CMU researchers.

Dr. Reddy earned his Ph.D. at Stanford.

Manuel Blum, 1995

April 3, 2018

Dr. Blum is currently a professor at CMU. He won his Turing Award for “his contributions to the foundations of computational complexity theory and its application to cryptography and program checking.” I just checked his website, he recently taught courses on undergraduate complexity theory and intro to cryptography. One of his great contributions is an algorithm that can find the median of a sequence of numbers in linear time. Fun fact: His wife is a distinguished professor at CMU SCS - Lenore Blum. Also, their child, Avrim Blum is also a professor at CMU SCS. What a family business!

Jonh Hennessy and David Patterson, 2018

June 4, 2018

They are introduced today because this year’s award was just announced.

Dr. John L. Hennessy used to be the President of Stanford and Dr. David A. Patterson retired from UC Berkeley. They are both rewarded the Turing Award for their contribution to a systematic, quantitative approch to the design and evaluation of computer architectures. They wrote a very influencial textbook, Computer Architecture: A Quantitative Approach, which is still used today by many computer architecture courses (and I still have a copy of it). I was lucky enough to attend Dr. Patterson’s talk on RISC V at Princeton two years ago - I’m a big fan of RISC.

Edmund Melson Clarke, Allen Emerson, and Joseph Sifakis, 2007

June 5, 2018

They won their Turing Award for “their role in developing Model-Checking into a highly effective verification technology that is widely adopted in the hardware and software industries.” Their work is built upon the idea of temporal logic, introduced by another Turing Award winner, Amir Pnueli. Using temporal logic, one can write a computer software to exhaustivly construct all possible action sequences, thus reliefing designers’ work load on proving the correctness of a system.

Dr. Clarke is a professor at CMU, and Dr. Emerson was his Ph.D. student when he was at Harvard University.

Leslie Gabriel Valiant, 2010

June 6, 2018

Dr. Valiant received his Turing Award for “transformative contributions to the theory of computation, including the theory of probably approximately correct (PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing.” The PAC is a model that considers a learning algorithm that can create a hypothesis from the past experience and use it to make decision in the future with controlled error.

Dr. Valiant was a Visiting Assistant Professor at CMU in 1973-74. He discovered that counting problems can be hard even when the decision problem is simple. This discovery is important to computer science because

Shafi Goldwasser and Silvio Micali, 2012

June 7, 2018

They won the Turing Award for “transformative work that laid the complexity-theoretic foundations for the science of cryptography, and in the process pioneered new methods for efficient verification of mathematical proofs in complexity theory.” They have introduced some very interesting mathematical structures for cryptography, such as pseudorandomness and interactive proofs. One of my favourites is zero-knowledge proof. I always think about it has the story of Ali Baba and the fourty theives. It is all about how Ali Baba can prove that he knows the password to the vault without revealing it (because if the thieves know the password, they don’t need to preserve Ali Baba’s life).

Dr. Goldwasser was an undergrad at CMU. One of the courses that introduced her into the field o theoretical computer science was taught by Dr. Manuel Blum, another Turing Award recipient currently teaching at CMU. She’s the first female Turing Award recipient I have introduced here, but she’s not the first female recipient.

Frances Elizabeth Allen, 2006.

June 8, 2018

She is the first female Turing Award recipient!

She received the Turing Award for her “pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel execution.” She joined IBM soon after the release of FORTRAN. By teaching FORTRAN, she became interested in how to build compilers. A key advance by her was that instead of representing programs as a sequence of statements in the compiler, they are represented as a mathematical graph that can be used to analyze the hidden properties of the code, so that computed values can be re-used.

Barbara Liskov, 2008.

June 9, 2018

She is the second female Turing Award recipient, who was acknowledged by her “contributions to practical and theoretical foundations of programming language and system design, especially related to data abstraction, fault tolerance, and distributed computing.”

She designed and implemented the CLU programming language, which laid the foundation of object-oriented programming (OOP). One of her major contributions was her Liskov Substitution Principle. Later, she moved on to study distributed systems, including the Byzantine fault tolerance algorithms.

When she applied for Ph.D., she applied to Princeton as well. But Princeton did not admit female student at that time and therefore unfortunately lost an outstanding alumna.

I believe these are all three female Turing Award recipients - Dr. Allen, Dr. Liskov, and Dr. Goldwasser.

Subscribe

Subscribe to this blog via RSS.

Categories

Blog 4

Web-design 1

Reu 1

Announcement 6

Circular statistics 1

Github 1

Cmu 2

Reading-group 1

Recent Posts

Popular Tags

Blog (4) Web-design (1) Reu (1) Announcement (6) Circular statistics (1) Github (1) Cmu (2) Reading-group (1)

Our Pastry Shop

Wean Hall 5115, Institute for Software Research
School of Computer Science, Carnegie Mellon University
5000 Forbes Ave
Pittsburgh, PA, 15213 USA