Computer Science 3600, Winter '27
Course Diary

---

Copyright 2027 by H.T. Wareham
All rights reserved

---

Week 1, (end of diary)

Thursday, January 7 (Lecture #1)
[Sections 1.1-1.2]

• Introduction to course; dates and conventions.
• Interlude: Why do a course like this in 2027?
  • Algorithms and their analysis and design has traditionally been seen as central to Computer Science. Such analysis and design typically encompasses four activities:
    1. Figure out exactly what problem needs to be solved (including all relevant restrictions that may hold relative to your particular instance of this problem).
    2. Determine if an efficient algorithm for your problem in (1) relative to its relevant restrictions already exists. If there is a range of possible algorithms, pick the best one.
    3. If you can't find an existing efficient algorithm in (2), design one using existing techniques, e.g., combinatorial solution-space trees, divide and conquer, dynamic programming, greedy algorithms, exploiting advanced data structures.
    4. If you cannot design an efficient algorithm in (3), apply computational complexity analysis to see if efficient algorithms for your problem are impossible; if so, see what alternatives exist, e.g., randomized algorithms, cost-approximation algorithms, parameterized algorithms, heuristics, and pick the best one.

  • Some claim that, given AI's new-found abilities to automate writing computer programs, AI can also do algorithm design and analysis. While AI can help with some of the activities above, it cannot do all of them as well as a human being yet (and maybe even ever)
  • Example: Asking Gemini for the most efficient algorithms for finding shortest paths in cities.
  • Given this, humans are for now still very much necessary to algorithm design and analysis, and you as CS students should do at least one course like this.
• Background: Problems and Algorithms
  • Computational Problems
    • A computational problem is a relation between inputs and outputs.
    • Types of computational problems.
      • By type of output:
        • Decision problem: Returns a Boolean value (typically the answer to a question about the optimal solution for a given instance of a problem).
        • Cost / Evaluation problem: Returns a number (typically the cost of an optimal solution for a given instance of a problem).
        • Example / Solution problem: Returns a structure (typically an optimal solution for a given instance of a problem).
        • Example: Versions of the Shortest Path problem:

          Shortest Path (Unweighted) [Decision]
          Input: A graph G = (V,E), two vertices u and v in V, and a positive integer k.
          Question: Is there a path P in G from u to v such that the number of edges in P is <= k?

          Shortest Path (Unweighted) [Evaluation]
          Input: A graph G = (V,E) and two vertices u and v in V.
          Output: The length of the path in G from u to v with the smallest possible number of edges.

          Shortest Path (Unweighted) [Solution]
          Input: A graph G = (V,E) and two vertices u and v in V.
          Output: A path P in G from u to v such that the number of edges in P is the smallest possible.

      • By entities in I/O relation:
        • Discrete problem: Manipulates integers and/or discrete structures.
        • Numerical problem: Manipulates (arbitrary-precision) real numbers in addition to integers and/or discrete structures.
    • This course will focus on various discrete problems. In particular, we will be looking at a number of discrete problems in which we are looking for a substructure of a given structure that is optimal relative to some function (combinatorial optimization problems).
    • Guidelines for defining computational problems
      • Strike balance between abstraction, formalization, and phrasing in terms of stated entities -- the former exposes the mathematical structures underlying a problem, the latter keeps the problem relevant.
      • Abstraction useful as it may show that your problem is the same as one that has already been solved
        => The first rule of algorithm design is don't <=

      • Make sure that the problem you defined and subsequently will be working on is the one you actually need to solve, e.g., checking possibility of vs checking costs of vs checking routes for airline flights.
    • Example: Bob's Trucking Company.
      • Examine contents of all depots in a shipping network => graph traversal (assuming shipping network can be modeled as a graph in which vertices are depots and edges are routes).
      • Minimizing costs associated with deliveries => shortest paths (# edges / summed edge-lengths)

        Shortest Path (Unweighted)
        Input: A graph G = (V,E) and two vertices u and v in V.
        Output: A path P in G from u to v such that the number of edges in P is the smallest possible.

        Shortest Path (Weighted)
        Input: An edge-weighted graph G = (V,E,W) and two vertices u and v in V.
        Output: A path P in G from u to v such that the sum of the weights of the edges in P is the smallest possible.

      • Maximizing reimbursements associated with deliveries => longest paths (# edges / summed edge-lengths)

        Longest Path (Unweighted)
        Input: A graph G = (V,E) and two vertices u and v in V.
        Output: A path P in G from u to v such that the number of edges in P is the largest possible.

        Longest Path (Weighted)
        Input: An edge-weighted graph G = (V,E,W) and two vertices u and v in V.
        Output: A path P in G from u to v such that the sum of the weights of the edges in P is the largest possible.

      • Maximizing the value of items loaded on a truck with a specified maximum capacity, where truck must carry all or none of each item => 0/1 Knapsack
        0/1 Knapsack
        Input: A set U of items, an item-size function s(), an item-value function v(), and a positive integer B.
        Output: A subset U' of U such that the sum of the sizes of the items in U' is less than or equal to B and the sum of the values of the items in U' is the largest possible.

      • Minimizing the number of emergency aid depots required in a shipping network such that at least one of the endpoints of each route has such a depot => Vertex Cover

        Vertex Cover
        Input: An undirected graph G = (V,E).
        Output: A subset V' \subseteq V such that for all edges (u,v) \in E, at least one of u and v is in V', and the size of V' is the smallest possible.

  • Algorithms
    • An algorithm for a problem is a finite sequence of instructions relative to a particular computer-model that, given an input for that problem, computes the corresponding output.
      • This is the classicial definition of an algorithm.
      • Such algorithms are hand-crafted by human beings and are not the same as procedures developed by computational methods (e.g., backpropogation, reinforcement learning) that are encoded in particular devices (e.g., neural networks), e.g. social media content choice algorithms, ChatGPT.
    • Types of algorithms.
      • By mode of algorithm creation: hand-crafted vs machine-crafted.
      • By type of computer-model:
        • Instruction execution mode: Deterministic / Randomized / Nondeterministic
        • Number of processors: Serial (single processor) / Parallel (multiple processors)
      • By type of computation: Discrete / Numerical.
    • This course will focus on hand-crafted deterministic serial discrete algorithms.
  • There are typically many possible algorithms for a particular problem. Which algorithm should we use? Perhaps we should use the one that is most efficient -- this, however, requires a useful and usable measure of algorithm efficiency ... This will be the topic of our next lecture.
• Potential exam questions

References

Unless otherwise stated, all references above are to Cormen et al. (2009).
• Aaronson, S. (2007) "The Limits of Quantum." Scientific American, 298(3), 62-69.
• Ausiello, G., Crescendi, G. Gambosi, V. Kahn, A. Marchetti-Spaccamela, and M. Protasi (1999) Complexity and Approximation of Combinatorial Approximation Problems and their Approximability Properties. Springer; Berlin.
• Brassard, G. and Bratley, P. (1996) Fundamentals of Algorithmics. Prentice-Hall; Englewood Cliffs, NJ. [Abbreviated above as B&B]
• Bernstein, A., Nanongkai, D., and Wulff-Nilsen, C. (2025) "Negative-weight single-source shortest paths in near-linear time." Communications of the ACM, 68(2), 87-94 Cesati, M. and Wareham, H.T. (1995) "Parameterized Complexity Analysis in Robot Motion Planning." In Proceedings of the 25th IEEE International Conference on Systems, Man, and Cybernetics: Volume 1. IEEE Press; Los Alamitos, CA. 880-885.
• Cook, S. (1971) The complexity of theorem proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing. ACM Press; New York. 151-158.
• 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]
• Daily, W. (2022) "Point/Counterpoint: On the Model of Computation." Communications of the AC M, 65(9), 30-32. [PDF]
• Downey, R.G. and Fellows, M.R. (1999) Parameterized Complexity. Springer-Verlag; Berlin.
• 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.
• Gonzalez, T. F. (2007). Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC.
• Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995) Limits to Parallel Computation: P-completeness Theory. Oxford University Press.
• Moret, B.M. (1999) "Towards a discipline of experimental algorithmics." In Data Structures, Near Neighbor Searches, and Methodology, DIMACS. 197-213.
• Karp, R.M. (1972) Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher (eds.) Complexity of Computer Computations. Plenum Press. 85-103.
• Motwani, R. and Raghavan, P. (1995) Randomized Algorithms. Cambridge University Press.

Created: October 21, 2026
Last Modified: October 21, 2026