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

**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**.

**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**(**Mult**iplexed
**I**nformation and **C**omputing **S**ervice), 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.

**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**.

**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**.

A quick trivia.

**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.

**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.

**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.

**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.

**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.

**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.

**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.

**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!

**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

**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.

**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

**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.

**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.

**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 to this blog via RSS.

Blog 4

Reu 1

Github 1

Cmu 2

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