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,
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
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
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
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
computation slide show
basic architecture slide show
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
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
). Some other historical notes on John Backus, Fortran
and the history of programming
languages can be found at the following sites:
Backus biographical note
References for history of programming languages
Timeline for programming languages
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
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
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.
The code for binary search .
The code for binary search as in the assignment .
Example for assignment 4