SCI199 Home Page (September 2003 - April 2004)
News!
Instead of a newsgroup, there will be a web forum for this class. Visit it
here. (Or here: http://www.sci199.tk).
There is also a link to it at the top of the page, you can use that once this
news section is removed.
The tutorial notes
are updated, including a Turing machine example and possible topics for project.
NOTICE OF CHANGE OF ROOM: For the spring term we meet Mondays 3-5 in UC376 and Thursdays 4-5
in UC253.
On Thursday, March 18, there will be a demonstration of
the 3D graphics display device. Please meet in Bahen BA5177 at 4:10
promptly. Tovi Grossman will give the demonstration and answer questions.
Finally, the assignments
section includes some preliminary information about the project.
Previous Offerings
This version of SCI199 will be similar to previous versions taught during the
1999-2000, 2001-2002, and 2002-2003 academic years
Course Overview
We will once again pursue the general (and very debatable) theme of GREAT
IDEAS in COMPUTING (including some interesting algorithms). The ambitious goal
is to try to identify the great ideas that have significantly 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 list of topics included the following: Sorting and searching algorithms and
their analysis, The von Neumann architecture, The Church/Turing thesis and the
Turing model of computation, 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 topics included:
Complexity theory and complexity 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 assistant:
Assignments
Assignment 2 is now
available. The assignment will be clarified in the tutorial on September 25.
Here is a solution
for A2 submitted by one of the students.
Assignment 3 is now
available. The assignment will be clarified in the tutorial on October 16. Here
is the list of submitted
search questions . You can use any of these question if both questions you
randomly selected turned out to be too easy.
Assignment 5 is now
available. The assignment was already discussed in lecture
and the tutorial.
Assignment 4 is now
available. The assignment will be clarified in the seminar November 17 and/or
in the tutorial on November 20.
Assignment 6 is now
available. The new due sate is Monday, March 8.
Project description
is now available. This may still change, but not substantially.
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 beginning of the lecture/tutorial in which they are
due. Any assignment which is submitted late will be penalized 25%, no assignment
will be considered if more than one week late and we will accept at most two
late assignments during the year.
Tutorial Notes
Readings
We will 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 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
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 implementation 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 different
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.
I strongly recommend reading the prophetic Vannevar
Bush article.
For our next topic, we will discuss operating systems, the software the
controls the allocation of systems resources (computing cycles, memory, I/O).
The idea of having an operating system is one of those great ideas that seems so
obvious (now) that it is hard to imagine not having one. We will look at some of
the great ideas utilized in operating systems, including interupts, file systmes
and virtual memory/paging.
Allan Borodin, Oleg Ace; 2003.