CSC196 Home Page (September 2021 - December 2021)
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 might mean in person or mean meet via zoom or skype.
You may be interested in starting or joining a recogized study group for this course or any course
This page will provide WWW access to various documents concerning CSC196.
See also the references given in 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 modified 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 CSC196
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.
We will also discuss bias and fairness in machine learning algorithms. Ssee, for example, NY Times article on facial recognition.
. Also see below a text file with a few links concerning social media and the issue of hate speech, bias and divisive spread of information.
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 Quercus.
Assignments and Quizzes
Assignments will be posted here and will be submitted on Markus. The two quizzes will be conducted on Markus.
Assignments are expected to
be handed in on time, as specified in the due date of the assignemnt. We will state clearly (and Markus enforces) precise rules about the penalties for late submissions.
The penalty for a late assignment 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 20. You may want to do the first question last as floating point will be discussed Wensday, September 22. The remaining questions should be self-contained even though one of the motivations for hashing has not yet been discussed
Assignment 2
Posted October 13. There will be further explanations regarding questions 2 and 3 during the Friday, October 15 tutorial and the Monday, October 18 class.
Assignment 3.
Posted November 1 and reposted November 6 and complete assignment posted November 8.
Assignment 4.
First question of A4 posted November 18. Full assignment posted November 20.
Slides for Class Meetings
Slides for our meetings will be posted here. I will try to post a preliminary version of the slides for each week by the preceding Sunday and then a "final" version by the end of the week.
Week 1
Motivating the course. The von Neumann architecture
Week 2
Continuing the discussion on the von Neumann architecture, floating point representation, the dictionary data type and its implementations.
Week 3
A discussion of ML and AI as a preface to our guest presentation. Continuing the discussion of floating point representation. I also have the continuation of data structures for dictionaries in the slides although we did not get to those slides.
Week 4
Review and finishing the discussion of data structures for dictionaries.
Turing machines, a precise mathematical model for the concept of a ``computable function''. The undeciability of the halting problem.
Monday, October 11 was Thanksgiving and hence no class. On Wednesday, October 13 Professor Nathan Wiebe discussed quantum computing.
Week 6
Review and finishing the discussion of the Church-Turing hypothesis. Turing reduction and more on undecidability.
Week 7
Guest presentation by Professor Nisarg Shah on fair division as p[art of social choice.
Week 8
Search Engines .
Week 8 Friday class.
Complexity Theory. The class NP of languages (decision problems), the P vs NP question.
Week 9
NP completeness and its importance.
VR-slides
Guest presentation by Professor Fanny Chavlier on Virtual Reality.
Week 10
Finish discussion of NP completeness. Introduction to complexity based cryptography.
Week 11 (part 1)
Finish up complexity based cryptography. Start networks and social networks
Week 11 (part 2)
Finish social networks.
Basic graph concepts
An appendix containing some basic graph concepts.
Week 12
Short introduction to mechanism design.
Some Previous Tutorial Notes from 2003
Readings and Slides
Text file containing
links relating to
social media and concerns regarding hate speech, bias, and targetting communities
The Dartmouth Summer 1955 AI Project
The The 7 Worst Tech Predictions of all Time
A History of Aritficial Intelligence
For a discussion about the nature of research and the future of ML see Geoff Hinton's commencdement address at IIT-Mumbai
CBS 60 moinutes interview with a Facebook whistleblower
Some Readings from the Previous SCI199 and CSC196 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 .