SCI199 Home Page (Septemeber 2002 - April 2003)

This version of SCI199 will be similar to previous versions taught during the 1999-2000 and 2001-2002 academic years

We will once again pursue the general (and very debateable) theme of GREAT IDEAS in COMPUTING (including some intersting algorithms). The ambitious goal is to try to identify the great ideas that have signifciantly influenced the field. 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 2002, the tentative list of topics include the following: Sorting algorithms and their analysis, The von neumann architecture, Source level vs machine level programming, Search engines and other aspects of information retrieval, Data bases, Computer networks and the internet. During the spring 2003 term, the tentative topics include: Complexity theory and compelxity based cryptography, Operating systems, GUIs, the mouse and other aspects of HCI, Ray tracing in graphics, Data compression, coding theory; Shannon's theory of information, Machine learning.

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 links above. Please send any comments or questions to the instructor or the teaching assitant:

The course information sheet has been distributed in class.

We begin the course by discussing some simple sorting and searching algorithms. The goal here is to informally introduce the idea of an algorithm so as to motivate mathematically well defined concepts of what it means to be "computable". The discussion of these basic algorithms also allows us to introduce the idea of analyzing the complexity of an algorithm. A description of some simple sorting algorithms expressed both informally and also written in some known programming language (like C) can be found common sorting algorithms here. One great idea that we see in some sorting algorithms is the concept of recursive definitons and algorithms . Another great idea relevant to search (and also cryptography) is the idea of hashing .

To understand how a computer executes a program such as the searching and sorting programs we have been considering, we need to understand the basic von Neumann architecture . Further discussion of the von Neumann architecture can be found at these sites:
  • Riley article
  • parallel computation slide show
  • basic architecture slide show
  • Risley definition
  • It is also interesting to look at the discussion concerning the forgotten Zuse machine .

    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. To get some appreciation of some attitudes about the use of high level languages, consider the following von Neumann anecdote taken from the University of Virginia History of Computing : In the 1950's von Neumann was employed as a consultant to IBM to review proposed and ongoing advanced technology projects. One day a week, von Neumann "held court" at 590 Madison Avenue, New York. On one of these occasions in 1954 he was confronted with the FORTRAN concept; John Backus remembered von Neumann being unimpressed and that he asked "why would you want more than machine language?" Frank Beckman, who was also present, recalled that von Neumann dismissed the whole development as "but an application of the idea of Turing's `short code'." Donald Gillies, one of von Neumann's students at Princeton, and later a faculty member at the University of Illinois, recalled in the mid-1970's that the graduates students were being "used" to hand assemble programs into binary for their early machine (probably the IAS machine). He took time out to build an assembler, but when von Neumann found out about he was very angry, saying (paraphrased), "It is a waste of a valuable scientific computing instrument to use it to do clerical work." An excellent recounting of the development of Fortran is given by Backus (see citation ). Some other historical notes on John Backus, Fortran and the history of programming languages can be found at the following sites:
  • Nebel article
  • Backus biographical note
  • Brief programming language history
  • References for history of programming languages
  • Fortran history
  • One of the programming language features included in FORTRAN was the use of subprograms. The implemention of FORTRAN did not permit recursion. We briefly discuss the use of a STACK to implement subprograms (recursive or not). We note that STACKS and DICTIONARIES are examples of an abstract data type and like subprograms, the use of these abstract data types allows us to separate functionality from implementation. We consider a number of diifferent implementations (data structures) for a dynamic dictionary, namely unsorted and sorted arrays, linked lists, (balanced) search trees and a hash table (see hashing above).

    Our next topic will concern the field of information retrieval and in particular web-based search engines. Information retrieval has been a field of study long before the advent of the internet and the web. But the emergence of the web has enabled (and has been driven by) this ``killer application''. One can easily spend an entire course discussing search engines (see, for example, the Stanford University information retrieval graduate course .) We will consider the basic operation of a search engine and why they (usually) seem to work so well. After search engines we will consider a high level view of how the internet works and what are the great ideas that have been it work so well and be so pervasive. In particular, we will discuss the distributed network design and packet routing, the TCP/IP standard, hypertext and the web. See the very informal but easy to read internet explanation. I also strongly recommend reading the prophetic Vannevar Bush article.

    For our last topic this term (until the New Year), we will discuss what in my biased view might be the greatest idea in computing, namely the Church-Turing Thesis, the idea that there is a well motivated and convincing mathematical definition of what it means to be computable. We will consider Turing's simple computational model and some of the related great ideas.

    Lateness Policy: The course grade will depend significantly on the assignments and the project. Assignments and the project are expected to be handed in on time, at the beginining of the lecture/tutorial in which they are due. Any assignment which is submitted late will be penalized 25%, no assignment will be consdiered if more than one week late and we will accept at most two late assignments during the year.

    Here are
  • Assignment 1
  • Assignment 2
  • The code for binary search .
  • The code for binary search as in the assignment .
  • Assignment 3
  • Assignment 4
  • Example for assignment 4
  • Assignment 5
  • Assignment 6
  • Assignment 7
  • Assignment 8
  • Assignment 9