Computer Science 6980, Winter '27
Course Diary

---

Copyright 2027 by H.T. Wareham and D. Churchill
All rights reserved

---

Week 1, (end of diary)

Thursday, January 7 (Lecture #1)
[DC3200, Lecture #1; RN3, Chapter 1; Class Notes]

• Went over course outline.
  • Important note: Though this course was created by Dave Churchill, I am not teaching it the way Dave does. Differences include:
    • Different lecture topics / assignments / evaluation scheme.
    • Assignments done individually, not in teams.
    • Assignments in Python, not C++.
    • No lecture capture (though links will be given to Dave's recorded lectures on YouTube where appropriate).
    • No course Discord channel.

    For those who prefer Dave's 3200, he will be teaching it in the Winter 2026 semester.

• As this course is on algorithmic techniques for artificial intelligence, let us first give brief overviews of intelligence, artificial intelligence, and algorithms.
• What is intelligence?
  • Intelligence is at its heart the ability to perform particular tasks, e.g.,
    1. problem solving, e.g., playing complex games like chess and Go, proving mathematical theorems, logical inference.
    2. being creative, e.g., producing literature, music, or art, doing research.
    3. using tools to perform tasks
    4. social interaction with others
    5. remembering / learning
    6. talking
    7. seeing

  • Intelligence is typically associated with agents and the behavior these agents exhibit when interacting with an external environment (more on this in the next lecture).
  • Intelligence has often been seen as anything humans do that animals don't, e.g., proposed biological Kingdom-level class Psychozoa for humans (Huxley (1957)); as evidence has accumulated of lower-level intelligence in animals, e.g., gorilla communication by American Sign Language (ASL), counting by crows, memory in bees, complex social interaction and tool use by chimpanzees, intelligence has been redefined in terms of complex high-level tasks, e.g., (1-2) above, to preserve human superiority.
  • This view of intelligence as exclusively human (and high-level adult human at that) surfaces in what we find anomalous (and funny), e.g., "Children / animals can't do that!"
  • Example: Not the Nine O'Clock News (1980): Gerald the Gorilla (Link)
• What is artificial intelligence (AI)?
  • Mythology and history are filled with artificial creatures that exhibited the appearance of (if not actual) intelligence, e.g., the bronze giant Talos, Roger Bacon's talking bronze head, European clock and musical automata, Vaucanson's mechanical duck (1739).
  • The term "artificial intelligence" was coined by John McCarthy to describe the goal of a two-month summer workshop held at Dartmouth College in 1956. AI is essentially the implementation of intelligent abilities by machines (in particular, electronic computers).
  • Many AI application areas, e.g.,
    • Problem solvers, e.g., General Problem Solver (GPS), artificial theorem provers, chess and Go programs (Deep Blue (1997); AlphaGo (2016)).
    • Logical / probabilistic reasoning systems, e.g., expert systems, Bayesian networks.
    • Generative AI, e.g., ChatGPT, DALI
    • (Swarm) Robotics
    • Machine learning
    • Natural Language Processing (NLP)
    • Computer Vision

  • Can distinguish types of AI based on mode of implementation (weak / strong), implementation mechanisms (symbolic / connectionist), and extent of implemented ability (Artificial Specialized Intelligence (ASI) / Artificial General Intelligence (AGI)).
    • Strong AI uses computational approximation of human / natural cognitive mechanisms; Weak AI uses any possible computational mechanisms.
    • Symbolic AI uses computer programs operating within discrete-entity frameworks, e.g., logic; Connectionist AI uses approximations of biological brain mechanisms, e.g., neural networks.
    • ASI implements a single intelligent ability, e.g., recognizing faces, answering questions, playing chess; AGI implements all intelligent abilities performed by a human being.
  • The initial focus of AI research was on strong symbolic ASI for high-level intelligent abilities (tasks (1-2) above) with the hope that developed ASI modules could be combined to create AGI. However, given the difficulties of implementing even supposedly low-level intelligent abilities (tasks (3-7) above), let alone AGI, current research tends more to weak connectionist ASI.
  • Though it has gone through several "winters" in the last 65+ years (Haigh (2023a, 2023b, 2024a, 2024b, 2025)), AI is currently in a boom period, with weak connectionist systems exhibiting seemingly human- (and sometimes trans-human-) level performance, e.g., ChatGPT, medical image analysis.
  • It is important to keep the distinctions made above in mind, particularly between ASI and AGI; it is often in the interests of researchers and corporations to claim that their systems do far more they than they actually do, and the resulting expectations can have embarrassing, e.g., automated machine (mis)translation, or even lethal, e.g., (non-)autonomous vehicles, consequences.
• What is an algorithm?
  • Classical CS definition: Given a problem P which specifies input-output pairings, an algorithm for P is a finite sequence of instructions which, given an input I, specifies how to compute that input's associated output in a finite amount of time.
  • This is the type of algorithm underlying symbolic GOFAI (Good Old-Fashioned AI); such algorithms are both created (hand-crafted) and understandable by humans.
  • Many modern AI systems have broadened the term "algorithm" to methods derived by machine learning systems that have been trained on massive amounts of data; such algorithms are machine-crafted and in many cases not easily understandable by humans, e.g., BERTology = the field of research devoted to trying to understand why the NLP BERT Large Language Model produces the outputs that it does.
  • It is critically important to keep the hand-crafted / machine-crafted distinction in mind given emerging challenges in real-world AI.
    • In order for AI systems to operate in tandem with humans or autonomously, these systems must be trustworthy (Schneier (2025)), i.e.,
      • These systems are reliable, i.e., they produce wanted behaviors consistently;
      • These systems are fair, i.e., they do not encode bias that compromises their behavior; and
      • These systems are explainable, i.e., the reasons why a system makes the decisions it does can be recovered in an efficient manner.

      While these properties can be ensured in hand-crafted, algorithms, it is not yet known if this can be done (even in principle, let alone efficiently (Buyl and De Bie (2024); Adolfi et al (2024a, 2024b, 2025)) for machine-crafted algorithms.

• AI is most certainly in an exciting yet unnerving state at present (Denning (2025)), but if one can forego knee-jerk panic, there are many opportunities for both applying existing and developing new algorithmic techniques for AI.
• In this course, we will first look at symbolic hand-crafted algorithmic techniques (search (single agent / multi-agent), constraint satisfaction, logical reasoning, planning) and then move on to symbolic and connectionist machine-crafted techniques (evolutionary computation, reinforcement learning, neural networks and deep learning).
• But before all that, next lecture, a closer look at agents and environments -- see you then!
• Potential exam questions

References

• Adolfi, F., Vilas, M., and Wareham, T. (2024a) "Complexity-Theoretic Limits on the Promises of Artificial Neural Network Reverse-Engineering." In the Proceedings of the 46th Annual Meeting of the Cognitive Science Society (CogSci 2024).
• Adolfi, F., Vilas, M., and Wareham, T. (2024b) "The Computational Complexity of Circuit Discovery for Inner Interpretability." arXiv.2410.08025 (71 pages). [PDF]
• Adolfi, F., Vilas, M., and Wareham, T. (2025) "The Computational Complexity of Circuit Discovery for Inner Interpretability." In the Proceedings of the 13th International Conference on Learning Representations (ICLR 2025). Selected for Spotlight presentation because the contribution has been judged to be especially notable.
• Barcelo, P., Monet, M., Perez, J., and Subercaseaux, B. (2020) "Model interpretability through the lens of computational complexity." In Advances in neural information processing systems, 33, 15487-15498. [PDF]
• Bassan, S., Amir, G., and Katz, G. (2024) "Local vs. Global Interpretability: A Computational Complexity Perspective." arXiv preprint arXiv:2406.02981. [PDF]
• Bellogin, A., Grau, O., Larsson, S., Schimpf, G., Sengupta, B., and Solmaz, G. (2024) "The EU AI Act and the Wager on Trustworthy AI." Communications of the ACM, 67(12), 58-65. [PDF]
• Buyl, M. and De Bie, T. (2024) "Inherent Limitations of AI Fairness." Communications of the ACM, 67(2), 48-55. [HTML]
• Bylander, T. (1994) "The Computational Complexity of Propositional STRIPS Planning.: Artificial Intelligence, 69(1-2), 165-204.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. (2009) Introduction to Algorithms. Third Edition. The MIT Press; Cambridge, MA. [Abbreviated above as CLRS]
• Cusumano, M.A. (2025) "DeepSeek Inside: Origins, Technology, and Impact." Communications of the ACM, 68(7), 18-22. (PDF)
• Denning, P. (2025) "Three AI Futures." Communications of the ACM 68(9), 31-33. (PDF)
• Denning, P. (2026) "The Conundrum of LLMs." Communications of the ACM 69(3), 31-34. (PDF)
• Dhar, V. (2024) "The Paradigm Shifts in Artificial Intelligence." Communications of the ACM, 67(11), 50-59. [HTML]
• Fikes, R.E. and Nilsson, N.J. (1971) "STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving." Artificial Intelligence, 2(3-4), 189-208.
• Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman; San Francisco, CA.
• Guest, O. and Martin, A. E. (2023) "On logical inference over brains, behaviour, and artificial neural networks." Computational Brain & Behavior, 6(2), 213-227 [PDF]
• Guest, O. and Martin, A.E. (2024) "A Metatheory of Classical and Modern Connectionism." Preprint. [PDF]
• Guest, O., Suarez, M., Muller, B.C.N., van Meerkerk, E., Beverborg, A.O.G., de Haan, R., Elizondo, A.R., Blokpoel, M., Scharfenberg, N., Kleinherenbrink, A., Camerino, I., Woensdregt, M., Monett, D., Brown, J., Avraamidou, L., Alenda-Demoutiez, J., Hermans, F., and van Rooij, I. (2025) "Against the Uncritical Adoption of 'AI' Technologies in Academia." Preprint. (PDF)
• Haigh, T. (2023a) "Conjoined Twins: Artificial Intelligence and the Invention of Computer Science." Communications of the ACM, 66(6), 33-37. [HTML]
• Haigh, T. (2023b) "There was No 'First' AI Winter." Communications of the ACM, 66(12), 35-39. [HTML]
• Haigh, T. (2024a) "How the AI Boom Went Bust." Communications of the ACM, 67(2), 22-26. [HTML]
• Haigh, T. (2024b) "Between the Booms: AI in Winter." Communications of the ACM, 67(11), 19-23. [HTML]
• Haigh, T. (2025) "Artificial Intelligence: Then and Now." Communications of the ACM, 68(2), 24-29. [HTML]
• Huxley, J. (1957) New Bottles for New Wine. Chatto & Windus.
• Kedia, A, and Rasu, M. (2020) Hands-On Python Natural Language Processing. Packt Publishing; Birmingham, UK.
• Livni, R., Shalev-Shwartz, S., and Shamir, O. (2014) "On the computational efficiency of training neural networks." Advances in Neural Information Processing Systems, 27, 1-9.
• Marcus, G. and Davis, E. (2019) Rebooting AI: Building Artificial Intelligence We Can Trust. Pantheon Books; New York.
• Marcus, G. and Davis, E. (2021) "Insights for AI from the Human Mind", Communications of the ACM, 64(1), 38-41. [Text]
• Newell, A. and Simon, H.A. (1956) The Logic Theory Machine: A Complex Information Processing System. RAND Technical Report P-868.
• Newell, A., Shaw, J.C., and Simon, H.A. (1959) Report on a General Problem Solving Program. RAND Technical Report P-1584.
• Newell, A. and Simon, H.A. (1972) Human Problem Solving. Prentice-Hall.
• Russell, S. and Norvig (2010) Artificial Intelligence: A Modern Approach (3rd Edition). Prentice-Hall.
• Russell, S. and Norvig (2022) Artificial Intelligence: A Modern Approach (4rd Edition). Prentice-Hall.
• Schmidhuber, J. (2015) "Deep learning in neural networks: An overview." Neural Networks, 61, 85-117.
• Schneier, B. (2025) "AI and Trust." Communications of the ACM, 68(8), 29-33. (PDF)
• Seuss, Dr. (1970) One fish two fish red fish blue fish. Random House.
• Shein, E. (2024) "The Impact of AI on Computer Science Education." Communications of the ACM, 67(11), 13-15. [HTML]
• Skinner, B.F. (1948) Walden Two. Hackett Publishing Company.
• Song, L., Vempala, S., Wilmes, J., and Xie, B. (2017) "On the complexity of learning neural networks." In Advances in Neural Information Processing Systems, 30, 1-9.
• Sutton, R.S. and Barto, A.G. (2018) Reinforcement Learning: An Introduction (Second Edition). The MIT Press. [Website]
• Van Rooij, I., Guest, O., Adolfi, F., de Haan, R., Kolokolova, A., and Rich, P. (2024) "Reclaiming AI as a theoretical tool for cognitive science." Computational Brain & Behavior, 1-21. [PDF]
• Wareham, T. (2022) "Creating Teams of Simple Agents for Specified Tasks: A Computational Complexity Perspective." CoRR abs/2205.02061 (20 pages). [PDF]
• Wareham, T. and Vardy, A. (2018) "Putting It Together: The Computational Complexity of Designing Robot Controllers and Environments for Distributed Construction." Swarm Intelligence, 12(2), 111-128.

Created: October 22, 2026
Last Modified: October 22, 2026