SCI199 Home Page (September 2008 - April 2009)

[ Previous offerings | Contacts & Overview | Assignments | Tutorial Notes | Readings | FORUM | Course Information]

Here is a list of possible topics

News!

Announcements for the week of April 27

The tentative final grades are now available. You can then email me for your grades. However, I wish to again emphasize that the grades I submit to the Faculty of Arts and Science are provisional and final grades can only be awarded by the Faculty. Mark and I read all the projects and in general we both found these projects to be informative and interesting. However, the writing (in termsi of grammar and sentence structure) in many projects could be significantly improved. But again the content was quite good. I wish you all good luck in your exams and throughout your University expereince.

I have posted the alternative project for those not doing the service learning project. Once again, you can ask in class or email me if there are questions on the project. By now you should have chosen a topic and have emailed me the topic. As stated before, I do not want more than two people doing the same topic (first come-first serve). The written component for both the service learning project and the alternative project are due April 6. During the week of April 6, each student doing an individual project will present a 10 minute oral prsentation of the project. For students working together on a service learning project, you can either do an indiviual 10 minute presentation or choose to do one group 15-20 minute presentation. For those doing the sevice project, here is a description of what is expected for service project. Please let me know you preference as to individual or group presentation. I will be scheduling the time slots fopr the oral presentations so as to try to cooridinate related topics but otherwise the ordering will be rather random. You are expected to be ready to present your oral prsentation on Monday, April 6 although most people will be presenting on Thursday, April 9, the final class.

General Announcements

I will be holding my regular office hours on Wednesdays 10:30-11:30 and 1:30-2:30. If these office hours conflict with your classes, please let me know and I will try to make alternative arrangments. In fact, it is always best to email me for an appointment and I am sure we can find mutually suitable times to meet. I encourage you to ask questions about the assignment (or any aspect of the course) in office hours or in class.

It is clear from assignment A0 that many students can benefit from the various University resources available to help students improve their writing ability. Please consider the resoureces mentioned below.

Instead of a newsgroup, there will be a web forum for this class. Visit it here. There is also a link to it at the top of the page that you can also use. We will continue to post course announcments at this site.

In case you don't know, the Faculty of Arts and Sciences sponsors a "First-year Learning Community (FLC)" to help first-year students get the most out of their University life (for more details, see FLC ). Unfortunately, enrollment seems to be full but you can still put your name on a waiting list. You should also take note of the following resources:

  • Writing at University website
  • College Writing Centres
  • Learning English as a Second Language
  • How not to plagarize

    • Previous Offerings

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

    Course Overview

    We will pursue the general (and very debatable) theme of GREAT IDEAS in COMPUTING. 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. Here you can find a list of some possible course topics . It is interesting (relevant to this course) that the Computing Community Consortium is asking the computing research community to help identify "game-changing advances from computing research conducted in the past 20 years." See the game-changing blog post .

    This page will provide WWW access to various documents concerning SCI199. Some of these documents are electronic versions of handouts given out in class. Some announcements will also be made on this page. See also the forum site given in the links above. Please send any comments or questions to the instructor Allan Borodin (bor ..funnyatsign ..cs.toronto.edu) or the teaching assistant Mark McCartin-Lim (markml..funnyatsign ..cs.toronto.edu).

    Assignments

    Assignment 0 is now available. This assignment will be a small part of the participation component of the grading scheme.

    Assignment 1 is now available. This assignment will be count as 10% of the grade. It is meant to be a relatively easy assignment.

    Assignment 2 is now available and due October 20.

    Assignment 3 is now available and due November 17 which is one week later than originally announced.

    Assignment 4 is now available and due January 12.

    Assignment 5 is now available and due January 26.

    Assignment 6 is now available and due March 16.

    Assignment 7 is now available and due April 9.

    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 20%, no assignment will be considered if more than one week late.

    Previous Tutorial Notes from 2003

    Readings

    We will begin the course by discussing the basic von Neumann architecture . Approximately 60 years after being articulated, the von Neumann architecture is still (at a high level) the basic architecture underlying modern computers. Some might argue that multi-core machines are now starting to force us to go beyond the von Neumann moidel at the moment but the model still represents our high level view of a computer. Further discussion of the von Neumann architecture and some assopciated history can be found at these sites:
  • Riley article
  • Wikipedia article on Herman Goldstine
  • Answers.com aricle
  • Wikipedia article on von Neumann architecture

    It is also interesting to look at the discussion concerning the forgotten Zuse machine .

    For those interested in the birthday paradox, here is the Wikipedia article on birthday paradox and another birthday paradox explanation which also lets you calculate similar probabilities.

    Here is the Wikipedia discussion of floating point representation .

    Here is the link for those interested in the history of computing site that I used in class. Many other sites are available. The history timeline used in class does seem to emphasize U.S. based contributions to the field. You might want to look at a more European history of computing . It is also fair to say that the University of Toronto was actively involved in the early history of computing as can be learned from William's article on U.Toronto Computation Centre and Hume's article on software for Ferut computer . Toronto faculty members Kelly Gotlieb and J. Patterson Hume were pioneers in the early development of computing.

    There are many sites that provide a discussion of Turing machines and gives examples and simulations for particular computational problems. Here is one such Turing machine site . And here is Turing's famous paper .

    Perhaps no topic is more widely discussed on the web than web search engines. We'll provide a very small selection of some interesting readings. I strongly suggest everyone to read an exceptionally prophetic 1945 article by Vannevar Bush . (In particular, see sections 6 and 7 for the concept of hyperlinks.) We mentioned in class that Google doesn't make it easy to find out specifics about their capabilites and methods. This 2004 Farach-Colton article is somewhat dated but still very interesting. One of the reasons that Google is so secretive can be understood from this article on Google ranking and spamming . For those interested in search anomalies, here is an article on the OR anomaly . At the end of the October 27 class, I was asked about how search engines accomodate for geographical location .

    Here follows a few of the many histories of the internet: It is interesting that the history of packet routing seems to be a little controversial as seen in this who invented packet routing debate .

    We have discussed the counter-intuitive idea of using negative results (assumptions about what can not be computed efficiently) leading to positive results (pseudo random generators, public key cryptography). In particular, we have been discussing results based on the assumed difficulty of factoring numbers. The Blum Blum Shub pseudo random generator is one example of a pseudo random generator. Perhaps the best known public key system is RSA . The original $100 RSA challenge and subsequent larger RSA number factoring challenges have been broken with improved factoring and computational resources but still most people continue to believe it is difficult to factor large numbers. For the fifth assignment you need to execute the extended Euclidean algorithm .

    Social networks and their study are being impacted by online networks and an emerging emphasis on more mathematical and algorithmic understanding of such networks. We start our discussion of social networks by asking (as suggested by Milgram's seminal studies), if it is a small world , and if so, is this surprising, and is the world made smaller or bigger by online social networks. Any study of the nature of social ties (e.g. friendship) must take into account the strength of such ties and in this context we consider Granovetter's strength of weak ties . An imporatnt aspect of social network study is the nature of communities in a network (i.e. how they can be defined and structural information about such communities) as well as how communities grow (and break apart). Two very interesting papers are the Leskovec et al study of community structure in large scale networks and the Backstrom et al study of the evolution of groups .

    In our discussion of cryptography, we introduced the idea that certain problems (like factoring) cannot be "efficiently" computed. And in our discussion of social networks, we came across many large scale graph theoretic problems where it is not always clear how to solve such problems. We recall Turing's work and the Church-Turing thesis which equates the intuitive concept of "computable" with the mathematically defined "computable by a Turing machine". In order to formalize the concept of "efficiently computable", we will assume the (debateable) extended Church-Turing thesis, namely we equate "efficiently computable" with "computable by a Turing machine in polynomial (as a function of the length of the encoded input/output) time". Now the question of what is and what is not efficiently computable becomes the precise (but very difficult) question of what is and what is not computable in polynomial time. We will foucs on decision problem (as justified in class) and consider the now famous P vs NP conjecture as introduced by Stephen Cook in 1971 (and independently in the Soviet Union) by Leonid Levin. To gain some appreciation of the importance of this question for not only computing, but for all mathematics and science, you can consider becoming a millionaire by solvina the "P vs NP" question, one of the seven Clay Millennium Prizes . The prizes are listed alphabetically and a description of the problem can be found by clicking on "P vs NP".

    Our next topic was a brief intrdocution to machine learning and, in particular, classification. After a brief overview of some common concepts and terminolog, we briefly considered support vector machines as one of the generic classification methods. Then we had a special guest lecture by Professor Geoffrey Hinton, celebrated for his work on machine leraning and especially for his seminal work relating to neural networks. For those wishing to get a related more technical version of his presentation, I suggest watching the UTUBE video of Hinton's Google Tech Talk "The Next Generation of Neural Networks" ..

    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 John Backus. Some other historical notes on John Backus, Fortran and the history of programming languages can be found at the following sites:
  • Nebel article biographical note
  • References for history of programming languages .

    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).

    For our next topic, we will discuss operating systems, the software that controls the allocation of systems resources (computing cycles, memory, I/O). The idea of having an operating system is another 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.
    HR>

    Allan Borodin, Mark McCartin-Lim; 2008.