Course and Learning Objectives

This section covers some of the things you should expect to get out of this course. It's going to start out as a hodgepodge of Olin Competencies, CS "standard" topics (drawn from CC2001 and ABET's CAC, among other places), and my own personal ideas about what's important and what we'll be doing this semester. Eventually, it will be nicely sorted and coherent. Or not.

A Stab at Objectives

A successful student completing this course should be able to:

• Analyze a problem description and select an appropriate algorithm, simple language, or abstract machine to solve the problem (for the major classes of language and of computational complexity, for the most fundamental data structures and algorithms in computer science).
• Articulate tradeoffs in algorithm and language selection
• Identify tractable, intractable-but-computable, and non-computable problems, explain what these mean and identify sources of intractability and undecidability.

Olin Competencies

The big ones for this course:

• Qualitative Understanding and Quantitative Understanding: Absolutely. This course focuses on understanding what's needed and how problems are solved, on understanding how to measure solutions, on selecting among alternatives, etc. This course is substantially about the theory behind computation and how that relates to implementation.

Other Olin competencies and the roles they will (or won't) play in this course:

• Life-long Learning: Oh, yes. This course will be underdeveloped, the resources won't be adequate or adequately fine tuned, and the entire semester will be an exercise in figuring out how to learn what you need to know. OK, hopefully it won't be that bad, but at least the first time through this competency will definitely be a theme of the course. Taught a little -- as we share strategies -- and measured mostly implicitly by whether you learn the ostensible content of the course.

• Diagnosis: There will be some design-debugging and it's hard to do anything computational without this, but this skill probably plays a smaller role here than in, say, Software Design.

• Opportunity: Only insofar as you will learn what kinds of problems are amenable to which kinds of solutions.

• Teamwork: Probably some, in that all work at Olin seems to involve collaboration, but this is not a big focus of the course. It won't really be taught and it won't really be measured except insofar as there are study group and/or peer grading components to the course.

• Communication: Measured implicitly in problem sets, lab reports, and class and on-line participation (including notetaking), but again not a major focus.

• Design: Implicitly, in that we'll be learning the tools by which designs are measured and using them to do some simple designs, but again this is not a major focus of this particular course.

• Context: Not so much. Although there is a contextual aspect to deciding how to make tradeoffs, most of these will be more technical tradeoffs rather than social, ethical, or otherwise. (See lots of other courses I teach or plan for plenty of context, though.)

"Traditional" CS curricular objectives

• Hits main points of:
  • algorithm analysis
  • algorithm design
  • complexity theory
  • automata theory
  • computability theory
  • programming language paradigms
  • language design

• Includes:
  • basic logic (both predicate and propositional forms)
  • graphs and trees
  • algorithms and problem solving
  • fundamental data structures
  • recursion
  • basic algorithmic analysis
  • algorithmic strategies
  • fundamental computing algorithms
  • basic computability
  • the complexity classes P and NP
  • automata theory
  • language interpretation (and translation)
  • programming language paradigms
  • declarations and types
  • abstraction mechanisms
  • functional programming
  • issues in programming language design
  • search and constraint satisfaction
  • knowledge representation
  • basics of information management

• === My list, corresponding to nothing in particular ===
  • Be able to design, build, analyze, make appropriate tradeoffs among:
    • fundamental data structures and associated algorithms, including:
      • linear data structures
      • graph structures and algorithms
      • trees
    • fundamental N : log N depth relationship (inverse of power set)
    • algorithmic strategies including:
      • brute force
      • greedy
      • divide and conquer
      • backtracking
    • asymptotic analysis of algorithms
      • recognize basic patterns (sub-linear, linear, n log n, polynomial, exponential)
      • understand best/worst/average case concepts
      • appreciate amortization
    • language and automata hierarchy and equivalences:
      • finite state automata
      • regular expressions
      • push-down automata
      • context free languages
      • Turing machine
      • recursive/recursive enumerability
      • determinism/nondeterminism
    • incompleteness and non-computability
      • universal machine
      • halting problem
      • diagonalization as a strategy
      • Church/Turing
      • Godel
    • propositional (boolean) logic
      • truth tables
      • Karnaugh maps
      • universality of nand
      • SAT
    • predicate logic
    • knowledge representation
    • NP
      • hardness
      • completeness
      • short certificate
      • reductions
      • also PTime ? PSpace? ?NC?
    • Lisp
      • list processing (incrementally and map/filter)
      • recursion and stack
      • tail recursion
      • functional programming/no mutation
      • interpreter
    • ? Constraint programming/logic programming
    • ? Machine learning
    • ? Information Retrieval
    • ? Databases, relational algebra
    I'll bet there are other things I'm leaving out as I'm typing from memory now....