News (Posted September 1)
In general, I will post announcements on the quercus page for CSC196 and will 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 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 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 (once it is initialized) 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 48 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. NOTE: there was a typo in question 3. The rightmost node at level j should is labelled (2^j)-1 and not 2^j. Assignment is due September 24 at 3PM.
Assignment 2 Assignment 2 is now complete. There was a typo in Q2. The set of edges are a subset of V_1 x V_2.
Assignment 2 is due October 15 at 3PM. NOTE: All answers to questions require an explanation so that it is clear as to how you arrived at your answer.
Assignment 3 Assignment 3 is complete.
Assignment 3 is due November 5 at 3PM. NOTE: All answers to questions require an explanation so that it is clear as to how you arrived at your answer.
Assignment 4 Assignment 4 is now complete.
Assignment 4 is due November 26 at 3PM. NOTE: All answers to questions require an explanation so that it is clear as to how you arrived at your answer.
Slides for Class Meetings wll be posted here sometime after the class
Class 1
Course organization and motivating the course.
Class 2
Great ideas can have negtive consequences. Possible topics.
Class 3
The von Neuman architecture. Floating point representation. Will LLMs make Wikipedia obsolete?
Class 4
ChatGPT indicates why ChatGPT will not replace Wikepedia. The memory hierarchy and memory management. Data types and the dictionary data type.
Class 5
Data structures for the ditionary data type: Unsorted array, sorted array, linked list, balanced binary search trees, hash tables. Much of this discussion was just on the black board. I will start the next class with a review of search trees and graph theoretic terminology, and then discuss hash tables which have not been included in these slides.
Class 7
What is a computable function. The Turing machine model. Hilbert's 10th problem. Undecideable decision problems.
Class 8
The simplicty of the TM model. The Universal Turing machine. Turing reductions.
Class 9
Turing machine. Turing reductions and computable transformations.
Encoding computations and the Entscheidungsproblem problem.
Class 10
review of Turing reductions and computable transformations.
Encoding computations and the Entscheidungsproblem problem. Start of complexity theory.
Class 11 was a guest presentation by Nathan Wiebe on quantum computation.
Class 12
Start of complexity theory. The extended Church-Turing thesis. The class P of decision problems decideable in polynomial time. The class NP of decision problems veriable in polynomial time.
Class 13
Continuation of complexity theory. The class NP of decision problems veriable in polynomial time. $NP$-complete decision problems.
Class 14
Continuation of complexity theory. The importance of NP completness. Some examples of NP complete problems. A tree of polynomial time transformations.
Class 15
Guest presentqtion by Chris Maddison on machine leartnoing (ML).
Class 16
A discussion following up on Chris Maddison's presentation.
Continued discussion of complexity theory.
Class 17
Finish discussion of complexity theory.
Class 18
Guest presentation by Niv Nayan on the Memory Hierarchy and Bloom Filters.
Class 19
Complexity based cryptography.
Class20
Finish up complexity based cryptography. Start social networks.
Class21
Continue social networks. Preferential attachment models for social networks. Properties of preferential attachment models. Centrtality of nodes, dense communtites, high clustering coefficient. The Backstrom and Kleinberg experiment to detect a romantic relation in a Facebook sub-network.
Class 22 was a guest presentation by Jonathan Panuelos on computer graphs}
Class23
Continue social networks. Triadic closure and the clustering coerficient.
The Watts-Strogatiz, amd Kleinberg random grid models.
Class24
Finishing social networks. Extending from grid distnace to general distances and then to social distance. Strong an weak ties. The strength of weak ties. The strong triadic closure property. Infering which edges are strong and weak.
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
For a discussion about the nature of research and the future of ML see Geoff Hinton's commencement address at IIT-Mumbai
Geoff Hinton';s warning regarding the existential threat of AI see
CNN August, 2025 News article on talk by Geoff Hinton
CBS 60 minutes interview with a Facebook whistleblower
A biography of Charles Babbage . Link provided by Sarah from the New Hampshire Technology Club.