SCI199 Home Page (September 2003 - April 2004)

[ Previous offerings | Contacts & Overview | Assignments | Tutorial Notes | Readings | FORUM | Syllabus: PostScript; PDF]

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.