CSC196 Home Page (September 2023 - December 2023)

Here is the course syllabus.
Here is a list of possible topics

News (Posted September 1)

In general, I will post announcements on the quercus page for CSC196 but will sometimes also use this web page.

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 wll 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) and concerns regarding deep learning and large language models. 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 Axios article on the impact of AI wth regard to hate speech and a text file below with some links to articles 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 in person.

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). IMPORTANT: You can submit multiple times. I suggest you submit a version in advance of the due date to be sure you can upload onto Markus successfully.

  • Assignment 0 A simple introductory assignment.
  • Assignment 1 Assignment 1 is now complete. Reposted September 29 at 2:15 PM
  • Assignment 2 Assignment 2. Posted October 7
  • Assignment 3 Assignment 3. Posted November 3; reposted November 13 with a revised question 3(a). Due date changed to Monday, November 20
  • Assignment 4 First three questions of Assignment 4 posted November 18; last question posted November 25.

    • Slides for Class Meetings

  • Week 1. Motivating the course.
  • Week 2 Beyond the von Neumann sequential model, floating point numbers, wikipedia vs chat-gpt, the dictionary data types, data structures for the dictionary data type.
  • Week 3 Hash tables, the birthday paradox and other balls and bins surprises, a brief introduction to graphs/networks and applicatons. A brief introduction to ML,DL,neural nets.
  • Week 4 Recap of presentation by Colin Raffel on large language models. Start of computability and Turing machines.
  • Week 5 Computability and Turing machines, the halting problem, reductions.
  • Week 6 The ingrediants leading to the undecideability of the Entscheidungsproblem; the universal TM, encoding TMs and TM computations, encoding a halting computation as a statement in 1st order logic; diagonalization. New topc: Search Engines
  • Week 7 Finish discussion of search engines, the online auction matching advertisers to queries, the semantic web and search that are difficult. Begin complexity theory. The class NP and NP-completeness. The P vs NP question.
  • Week 8 The class NP and NP-completeness. The P vs NP question. Note: On Monday, we stopped at slide 9 but I am ading slides that will complete our discussion of NP completeness. On Wednesday, Professor Srinivasan discussed zero knowldege proofs. Here are his slides: Zero knowledge proofs.
  • Week 9 The class NP and NP-completeness, polynomial time reductions and transformationsthe Karp tree of NP complete problems, reducing search and optimization problems to the "underlying" decision problem.
  • Week 10 Can randomization help? The class RP, polynomial zero testing. Begin complexity based cryptography. One time pads. Public key cryptography, RSA, pseudo random generators.
  • Week 11 Brief introduction to Computational social choice.
  • Week 12 Social networks. The preferential attachment network generative model. Extrating information from the network structure.

    • Some Previous Tutorial Notes from 2003

    Readings, Slides and Vidoes

  • A short video on Computability
  • A short video on P vs NP
  • My slides for the first week of CSC303s20 which provides graph theory definitions and examples of networks.
  • Text file containing links relating to social media and concerns regarding hate speech, bias, and targetting communities
  • The Dartmouth Summer 1955 AI Project
  • 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 commencement address at IIT-Mumbai
  • CBS 60 minutes interview with a Facebook whistleblower
  • A biography of Charles Babbage . Link provided by Sarah from the New Hampshire Technology Club.

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