Skip to content

Latest commit

 

History

History
189 lines (94 loc) · 13.3 KB

README.md

File metadata and controls

189 lines (94 loc) · 13.3 KB

CS476 HW Solutions

Don't forget to drop a star on this repository.

Previous years questions

Spring 2019 - If the halting problem were decidable, which major theorem in mathematics would be impacted, and how?

Charles Babbage

  • 26 December 1791 – 18 October 1871
Along with Ada Lovelace, designed the first mechanical computer. Had more complex designs that did not work with the technology of then. However, his designs have been implemented in the present day and has been shown that his work was flawless. His designs and the implementations of his designs are on display in various museums in England.

Ada Lovelace

  • 10 December 1815 – 27 November 1852
A brilliant woman as she was, she became genuinely interested in the mechanical computer. She wrote an algorithm specifically for Babbage's machine and this is the first algorithm ever written with the intention of running on a machine so some say she is the first computer programmer.

Alan Turing

  • 23 June 1912 – 7 June 1954
He formalized the concepts of algorithm and computation with the Turing Machine, which is a model of a general purposed computer. He is the father of theoretical computer science and the mother of artificial intelligence. During the second world war, his work on cracking the German code helped the Allies in many engagements against the Nazis and shortened the war in Europe from 2 to 4 years according to various estimates. Although he does not have a Turing Award under his name, the Turing Award itself was named after him.

Noam Chomsky

  • 7 December 1928 -
A bad-ass in many a field of science. His work in linguistics, namely universal grammar theory, the generative grammar theory and the Chomsky Hierarchy led to breakthroughs in computer science. Also to say his critical work of B.F. Skinner's work also caused a decline in behaviorism in psychology and philosophy of mind.

Stephen Cook

  • 14 December 1939 -
He is known for his work in complexity theory and proof complexity in the field of computer science. Cook formalized the notions of polynomial-time reduction and NP-completeness and proved the existence of an NP-complete problem by showing that the Boolean satisfiability theorem was NP-complete.

Leonid Levin

  • 2 November 1948 -
He is known for his work in complexity theory and average case complexity and randomness in computing. He independently discovered the existence of NP-complete problems. He was awarded the Knuth Prize in 2012.

Donald Knuth

  • 10 January 1938 -
His major work is in algorithms analysis. He worked on the rigorous analysis of the computational complexity of algorithms and systematized formal mathematical techniques for it. He popularized the asymptotic notation. He is the creator of many academics' beloved, TeX, the computer typesetting system.

Dennis Ritchie

  • 9 September 1941 – 12 October 2011
American computer scientist. He created the C programming language. And with Ken Thompson he created the Unix operating system. He caused a stir when his death did not attact nearly one percent of the attention of Steve Jobs' death.

Leslie Lamport

  • 7 February 1941 -
Lamport is best known for his seminal work in distributed systems and as the initial developer of the document preparation system LaTeX. Leslie Lamport was the winner of the 2013 Turing Award for imposing clear, well-defined coherence on the seemingly chaotic behavior of distributed computing systems, in which several autonomous computers communicate with each other by passing messages.

Grace Hopper

  • 9 December 1906 – 1 January 1992
She invented the first compiler for a computer programming language, and was one of those who popularized the idea of machine-independent programming languages which led to the development of COBOL, one of the first high-level programming languages.

Richard Karp

  • 3 January 1935 -
He has made many other important discoveries in computer science and operations research in the area of combinatorial algorithms. His major current research interests include bioinformatics.
In 1971 he co-developed with Jack Edmonds the Edmonds–Karp algorithm for solving the max-flow problem on networks, and in 1972 he published a landmark paper in complexity theory, "Reducibility Among Combinatorial Problems", in which he proved 21 Problems to be NP-complete.
In 1973 he and John Hopcroft published the Hopcroft–Karp algorithm, still the fastest known method for finding maximum cardinality matchings in bipartite graphs.
In 1980, along with Richard J. Lipton, Karp proved the Karp-Lipton theorem (which proves that, if SAT can be solved by Boolean circuits with a polynomial number of logic gates, then the polynomial hierarchy collapses to its second level).
In 1987 he co-developed with Michael O. Rabin the Rabin-Karp string search algorithm.

Ken Thompson

  • 4 February 1943 -
With Dennis Ritchie, Thompson designed and implemented the original Unix operating system. He also invented the B programming language, the direct predecessor to the C programming language, and was one of the creators and early developers of the Plan 9 operating systems. Since 2006, Thompson has worked at Google, where he co-invented the Go programming language.

Alonzo Church

  • 14 June 1903 – 11 August 1995
His proof that the Entscheidungsproblem, which asks for a decision procedure to determine the truth of arbitrary propositions in a mathematical theory, is undecidable for the theory of Peano arithmetic. This is known as Church's theorem.
His articulation of what has come to be known as the Church–Turing thesis.
He was the founding editor of the Journal of Symbolic Logic, editing its reviews section until 1979.
His creation of the lambda calculus.

Kurt Gödel

  • 28 April 1906 – 14 January 1978
He was an Austrian, and later American, logician, mathematician, and philosopher. Considered with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel made an immense impact upon scientific and philosophical thinking in the 20th century. Gödel published his two incompleteness theorems. The first incompleteness theorem states that for any self-consistent recursive axiomatic system powerful enough to describe the arithmetic of the natural numbers (for example Peano arithmetic), there are true propositions about the naturals that cannot be proved from the axioms. To prove this theorem, Gödel developed a technique now known as Gödel numbering, which codes formal expressions as natural numbers.

George Boole

  • 2 November 1815 – 8 December 1864
He worked in the fields of differential equations and algebraic logic, and is best known as the author of The Laws of Thought (1854) which contains Boolean algebra. So that we can say 1 or 0 is 1 and 0 and 1 is 0.

Niklaus Wirth

  • 15 February 1934 -

  • He is a Swiss computer scientist, best known for designing several programming languages, including Pascal, and for pioneering several classic topics in software engineering. In 1984 he won the Turing Award, generally recognized as the highest distinction in computer science, for developing a sequence of innovative computer languages.

  • Wirth was the chief designer of the programming languages Euler, Algol W, Pascal, Modula, Modula-2, Oberon, Oberon-2, and Oberon-07. He was also a major part of the design and implementation team for the Lilith and Oberon operating systems, and for the Lola digital hardware design and simulation system. He received the ACM Turing Award for the development of these languages in 1984 and in 1994 he was inducted as a Fellow of the ACM. He designed the simple programming language PL/0 to illustrate compiler design. It has formed the basis for many university compiler design classes.

Blaise Pascal

  • 19 June 1623 – 19 August 1662
French mathematician and physicist. He is known for his Pascal triangle and early work in probability theory after which the notion of expected value has been invented.

Claude Shannon

  • 30 April 1916 - 24 February 2001
Known as the father of information theory. Shannon is noted for having founded information theory with a landmark paper that he published in 1948. He is perhaps equally well known for founding digital circuit design theory in 1937, when, as a 21-year-old master's degree student at the Massachusetts Institute of Technology (MIT), he wrote his thesis demonstrating that electrical applications of Boolean algebra could construct any logical, numerical relationship. Shannon contributed to the field of cryptanalysis for national defense during World War II, including his basic work on codebreaking and secure telecommunications.

John McCarthy

  • 4 September 1927 – 24 October 2011
McCarthy was one of the founders of the discipline of artificial intelligence. He coined the term "artificial intelligence" (AI), developed the Lisp programming language family, significantly influenced the design of the ALGOL programming language, popularized timesharing, and was very influential in the early development of AI.

C.A.R. Hoare

  • 11 January 1934 -
He developed the sorting algorithm quicksort in 1959/1960. He also developed Hoare logic for verifying program correctness, and the formal language Communicating Sequential Processes (CSP) to specify the interactions of concurrent processes (including the dining philosophers problem) and the inspiration for the occam programming language.

Tim Berners-Lee

  • 8 June 1955 -
He is best known as the inventor of the World Wide Web. He made a proposal for an information management system in March 1989, and he implemented the first successful communication between a Hypertext Transfer Protocol (HTTP) client and server via the Internet sometime around mid-November of that same year.

al-Khwarizmi

  • 780 - 850
In the 12th century, Latin translations of his work on the Indian numerals introduced the decimal positional number system to the Western world. Al-Khwārizmī's The Compendious Book on Calculation by Completion and Balancing presented the first systematic solution of linear and quadratic equations in Arabic. He is often considered one of the fathers of algebra. He revised Ptolemy's Geography and wrote on astronomy and astrology.
Some words reflect the importance of al-Khwārizmī's contributions to mathematics. "Algebra" is derived from al-jabr, one of the two operations he used to solve quadratic equations. Algorism and algorithm stem from Algoritmi, the Latin form of his name. His name is also the origin of (Spanish) guarismo and of (Portuguese) algarismo, both meaning digit.

Richard Hamming

  • 11 February 1915 - 7 January 1998
He was an American mathematician whose work had many implications for computer engineering and telecommunications. His contributions include the Hamming code (which makes use of a Hamming matrix), the Hamming window, Hamming numbers, sphere-packing (or Hamming bound), and the Hamming distance.

Vladimir Levenshtein

  • 1935 -
He is a Russian scientist who has done research in information theory, error-correcting codes, and combinatorial design. Among other contributions, he is known for the Levenshtein distance and a Levenshtein algorithm, which he developed in 1965.

Edsger W. Dijkstra

  • 11 May 1930 – 6 August 2002
Dijkstra was an early theoretical pioneer in many research areas of computing science, including algorithm design, programming methodology, and software architecture. The academic study of concurrent computing and concurrent programming started in the 1960s, with Dijkstra (1965) credited with being the first paper in this field, identifying and solving the mutual exclusion problem. He was also one of the early pioneers of the research on principles of distributed computing. His foundational work on concurrency, semaphores, mutual exclusion (mutex), deadlock (deadly embrace), finding shortest paths in graphs, fault-tolerance, self-stabilization, among many other contributions comprises many of the pillars upon which the field of distributed computing is built. Shortly before his death in 2002, he received the ACM PODC Influential-Paper Award in distributed computing for his work on self-stabilization of program computation. This annual award was renamed the Dijkstra Prize (Edsger W. Dijkstra Prize in Distributed Computing) the following year, in his honor.

John von Neumann

  • 28 December 1903 - 8 February 1957
He was a pioneer of the application of operator theory to quantum mechanics, in the development of functional analysis, a principal member of the Manhattan Project and the Institute for Advanced Study in Princeton (as one of the few originally appointed), and a key figure in the development of game theory and the concepts of cellular automata, the universal constructor and the digital computer. He published 150 papers in his life; 60 in pure mathematics, 20 in physics, and 60 in applied mathematics. His last work, an unfinished manuscript written while in the hospital, was later published in book form as The Computer and the Brain.

Paul Erdös

  • 26 March 1913 - 20 September 1996
Known for his work combinatorics, graph theory, number theory, mathematical analysis, approximation theory, set theory, and probability theory, all of which are applicable to computer science. He is also somewhat famous for his productivity, see Erdős number.