CSC196 Home Page (September 2020 - December 2020)

[ Previous offerings | Contacts & Overview | Readings | FORUM |
Here is the course syllabus with assignement and quiz dates
Here is a list of
possible topics

News (Posted October 8)!

Wednesday, October 14, our guest will be Professor Eyal de Lara who will be discussing ``virtualization''. See Quercus announcement for zoom link.

General Announcements

I will be announcing my regular office hours once the term begins and I know more about my schedule. However, I always welcome questions and we will probably also be using piazza as an additional means of communication. If you want to schedule an individual meeting, it is best to email me for an appointment and I am sure we can find mutually suitable times to "meet" where meet will unfortunately only be online for the time being.

This page will provide WWW access to various documents concerning CSC196. We will also be using Quercus for posting documents. See also the references given in the previous versions of the course. Please send any comments or questions to the instructor or the teaching assistant.


Previous Offerings

CSC196 is one of the First Year Foundations Seminars in the Faculty of Arts and Science. CSC196 is a new version of previous courses listed as SCI199 during the 1999-2000, 2001-2002, 2002-2003, 2003-2004, 2008-2009 and 2009-2010 academic years. Note that these SCI 199 were taught as full year (two term) courses. Given that our CSC196 course is a one term course, we will have to be the less ambitious in our choice of topics.


About First Year Foundation Seminars

Google "first year seminar faculty arts and science toronto" as to the nature and objectives of First Year Foundations Seminars. You probably alreacdy read this and perhaps that is why you chose to take a first year seminar course. But it is worth reading again.

CSC196 Course Overview

We will pursue the general (and very debatable) theme of GREAT IDEAS in COMPUTING (including some surprising algorithms). The ambitious goal is to try to identify some of the great ideas that have significantly influenced the field and made computing so pervasive. 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. As we will see, many of the great ideas were initially against the ``prevailing opinion''. In 2008 the Computing Community Consortium was 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 . It will be interesting to update this blog to reflect the last 12 years since 2008. For example, we plan to discuss the success (and limitations) of deep learning. Another recent topic of interest is social networks and the way information (and mis-information) is spread on social networks. Infiormation spread has become a major topic of discussion especially as it now impacts political opinions. See, for example, Starbird et al paper on strategic information spread.

This page will provide WWW access to various documents concerning CSC196. Some announcements may also be made on this page. See also piazza (oncde the term begins) and Quewrcus. Please send any comments or questions to the instructor Allan Borodin (bor ..funnyatsign ..cs.toronto.edu) or the teaching assistant (TBA).

Assignments and Quizzes

Assignments will be posted here and (with the exception of A0) will be submitted on Markus. The two quizzes will be conducted on Markus.

Assignments are expected to be handed in on time, at the beginning of the lecture/tutorial in which they are due. Penalty for a late assignments is 5% for each 24 hours up to 96 hours. No further extensions are allowed without a valid documented reason (e.g., sickness with a doctors letter).

  • Assignment 0 A simple introductory assignment
  • Assignment 1 Posted September 21
  • Assignment 2 Reposted October 20 with improved wording and with clarification of question 1. .
  • Quiz 1 The quiz took place October 19.
  • Assignment 3 A3 is now complete. Reposted November 5 with a small rewaording in question 2, second part
  • Assignment 4 Start of A4. Reposted December 1. Note change of due date
  • Lecture-Meetings

    Slides for our meeting will be posted here. I will try to post a preliminary version of the slides before the lecture and then a "final" version following the lecture.
  • Week 1 Motivating the course, von Neumann architecture, floating point representation (finalized 14/9/20)
  • Week 2 Wikipedia, dictionaries, data structures for dictionaries. (Repossted 23/9/20)
  • Week 3 Guest presentation by Henry Yuan on quantum computing. Turing machines and undecideabile problems (Reposted 2/10/20)
  • Week 4 Turing machines and undecideabile problems. (Reposted 9/10/20)
  • Week 5 Guest class by Eyal de Lara on the topic of visualization. Start discussion of search engines (Posted 14/10/20)
  • Week 6 Continue discussion of search engines (Reposted 24/10/20)
  • Week 7 On Wednesday, we will start Week 7 with a guest discussion on machine learning (ML) by Professor Roger Grosse. On Friday, we begin by giving examples of different networks and basic network/graph concepts as part of our discussion of social networks. (Reposted 15/11/20) correcting a typo on slide 28 where the matrix is B(G)
  • Week 8 Continue discussion of graph concepts and social networks (Reposted 6/11/20)
  • Week 9 Guest presentation by Professor Aleksander Nikolov on differential privacy. On Friday, we begin discussion of complexity theory and the P vs NP question. (Posted 15/11/20)
  • Week 10 We continue the discussion of complexity theory and the P vs NP question. We will then begin a discussion of complexity based cryptography. (Reposted 27/11/20)
  • Week 11 Finish the discussion of complexity based cryptography. (Posted 5/12/20)
  • Week 12 Very briefly discss porgamming languages, compilers, operating systems and paging. (Posted 9/12/20)

  • Some Previous Tutorial Notes from 2003


    New Readings and Slides

  • Henry Yuan's slides for the September 30 discussion on quantum computing.
  • Some Readings from the Previous SCI199 offerings

    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 model at the moment but the model still represents our high level view of a computer. Further discussion of the von Neumann architecture and some associated 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 on computing 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 .