SCI199 Home Page (Septemeber 2001 - April 2002)

This version of SCI199 will be based on a previous version taught during the 1999-2000 academic year.

We will again pursue the general (and very debateable) theme of GREAT IDEAS in COMPUTING (including some beautiful algorithms). We will concentrate on mathematical, algorithmic and software ideas with the understanding that the importance and usefulness of these ideas depends upon (and often parallels) the remarkable ideas and progress in computing and communications hardware. The list of topics we shall discuss will depend to some degree on the background and interests of the class. During the fall of 1999, the topics discussed included the following: Turing's concept of computability and the Church-Turing thesis, the von Neumann machine model, FORTRAN and the development of `high level' languages, fast sorting algorithms, recursion, an information theortic lower bound for comparison based sorting, search engines (including a visit by Andrei Broder, Altavista CTO), Shannon's development of information theory, compression algorithms, error correcting codes, the Euclidean algorithm and a brief discussion of computational number theory problems, public key crypography, and the Theory of NP-completeness. During the spring 2000 term, Arnold Rosenbloom continued the course and additional topics included networking, audio and video compression, computational geoemtry, parallel and distributed computation and relational databases. We will again visit many of these topics and we also plan to discuss some topics in HCI, operating systems, scientific computatation and other aspects of information retrieval.

This page will provide WWW access to various documents concerning SCI199. Most, if not all, of these documents are electronic versions of handouts given to the class. Some announcements will also be made on this page. See also the references given in the Fall 1999 link above. Please send any comments or questions to the instructor or the teaching assitant:

The course information sheet has been distributed in class.

We will begin the course by considering some fundamental ideas of Turing, especially his concept of a ``computable function'' as developed in his famous 1936 paper. The work and life of Alan Turing has been described in many sources, and has also been the subject of stage productions. You can begin to search some of the relevant literature by looking at the website maintained by Andrew Hodges , author of a widely acclaimed book on Turing.

As a prelude to understanding the Turing machine model, we will briefly consider the concept of a finite automaton. A discussion of finite automata can be found in many text books as well as online lecture notes such as David Matuszek's notes which includes this example .

Turing machines are taught in every undergraduate course in computer science and one can find several Turing machine simulation applets on the web. You can try TM applet 1 or TM applet 2 .

Rather than trying to become proficient Turing machine programmers, lets consider some simple sorting algorithms either expressed informally or written in some known programming language (like C). Some common sorting algorithms can be found here. We should be able to convince ourselves that these algoritms could be implemented on a Turing machine as a small piece of evidence in support of the Church-Turing Thesis. These algorithms also provide an introduction to some other great ideas (e.g. complexity bounds and optimal algorithms, recursive programs) we will be considering.

As a change of pace, we will next consider an exceptionally prophetic 1945 article by Vannevar Bush . (In particular, see sections 6 and 7 for the concept of hyperlinks.)

Motivated by Bush's article, we then discuss search engines. What kinds of queries are easily handled by current search engines and what kinds of queries are difficult for these search engines? For assignment 3, we take Bush's suggestion and see if we can find information on the advantages of the Turskish short bow over the English long bow during the Crusades.

What has caused home computing to be so pervasive? Clearly the world wide web (and search engines) has caused a dramatic increase in home computer use. But even prior to the emergence of the web, home comuter use was increasing. Clearly the significant reduction in costs was a driving (and certainly necessary) factor. But certain "killer applications" were perhaps also needed and these applications include email and word processing. We consider the functionality provided by current word processors and investigate how some of these features are implemented.

While Turing's work provided us with a mathematically appealing and unambiguous definition of the meaning of ``computable'', it did not provide an attractive model for computer architecture. Our next great idea is the von Neumann architecture. Without worrying too much about the historical credits, von Neumann's description (in 1946) of a general purpose machine architecture had an immediate and long lasting impact on the design and use of computers.

Based on the von Neumann architecture, programming languages begin to emerge by the early 1950's. While there is an interesting (and perhaps somewhat disputed history) of the early development of "high level languages", it seems fair to say that the first commercially successful high level language (and compiler) was FORTRAN developed at IBM by John Bachus and his group.

Our last topic for the the fall term will be operating systems. We will consider some of the main concepts in the development of operating systems. For a little historical perspective, one can look at John McCarthy's history of time sharing and at Dennis Ritchie's account of the development of UNIX . One of the great ideas in the development of operating systems is virtual memory .

We started the new term by discussing the "complexity thesis" or "extended computability thesis". Recall that the Church-Turing thesis equates the informal concept of "computable" with the matehmatically precise concept of "Turing machine computable". The complexity thesis equates the informal concept of "efficiently computable" with the mathematical precise concept of "computable by a Turing machine in polynomial time". The compelxity thesis is more debateable than the Church-Turing thesis but still it enables us to develop a very useful framework for studying the complexity of problems. In particular, we discussed the P vs NP question. The concept of NP completeness initiated by Cook (and independently by Levin) and then developed by Karp and many others has had a profound impact on computing, mathematics and many other related fields. For motivation (and an introduction to this concept) I suggest looking at
  • how to get rich quick.

    • You can also look at some lecture notes on

  • NP and NP Completeness
    • and some other topics that we discuss in CSC364/CSC366.

    We then began a discussion of complexity based cryptography and the public key RSA system. Karolina has located a great link for understanding the
  • RSA algorithm
    • .

    Lateness Policy: The course grade will depend significantly on the assignments. Assignments are expected to be handed in on time. Any assignment which is submitted late will be penalized 25% and we will accept at most three late assignments during the year.

    Here is Assignment 2

    Here is Assignment 4

    Here is Assignment 5

    Here is Assignment 6