CSC152 2005F, Class 54: An Overview of CS

Admin:
* Extra credit for attending Cassie's talk TOMORROW: 4:15 ARH 305
  A Comparative Analysis of the Native Movements in Mexico and Ecuador
* Free CDs
* Questions on the exam?
  * How do I create an array whose base type is a type variable?
    T[] contents = ...?
    T[] contents = new T[10]; // WON'T COMPILE
    * One solution
      T[] contents = (T[]) new Object[10]; // Gives you a warning
      * Rolf notes that this solution only works if T is completely generic
    * Another solution
      Object[] contents = new Object[10];
      ...
      return ((T) contents[i]); // Also gives you a warning
  * Does DynamicArray have to be a parameterized type?
    * No, it does not have to be a parameterized type.
    * Next year, it will be :-)
  * For the dynamic array question, what does "the pos must be the same as the index"
    * I mean "when someone says get(5), you should look at index 5 in the underlying array"
  * Suppose my array has a "hello" at position 2 and a "goodbye" at position 5, and nulls everywhere else what should toString return?
    * Anything reasonable that gives the reader a sense of the complete contents of the array
      * [null, null, hello, null, null, goodbye]
      * [ ... 2:hello ... 5:goodbye ... ]
      * [0:null, 1:null, 2:hello, 3:null, 4:null, 5:goodbye]
      * [2:hello , 5:goodbye]
      * [0:, 1:, 2:hello, 3:, 4:, 5:goodbye]
      * [null null hello null null goodbye]
      * [ ... 2:hello ... 5:goodbye ... ]
      * [0:null 1:null 2:hello 3:null 4:null 5:goodbye]
      * [2:hello  5:goodbye]
      * [0: 1: 2:hello 3: 4: 5:goodbye]

Overview:
* What is CS, revisited?
* Some key subfields of CS
  * Algorithms
  * Theory
  * AI
  * Graphics
  * HCI
  * ...

What is computer science?
* NOT the science of computers (or, more precisely, not the application of the scientific method to computers)
* The study of algorithms and data structure
  * Algorithms: Rules for manipulating data
  * Data structures: Rules for organizing data
  * (Note that two are related)

Lots of different subdisciplines

Algorithms
* Write algorithms for new problems
  * Find new problems
  * Sometimes better algorithms for old problems
* Prove interesting properties of algorithms or problems
  * Theorem: No compare-and-swap sorting algorithm can take time less than O(nlogn)
* Attempt to answer a big open question: Is P equal to NP?
  * P = problems for which the running time is bounded by *some polynomial*  O(n^2)  O(n^100) O(n^10000000logn)
  * NP = problems for which the running time of the "check of a solution" is bounded by some polynomial
  * Typical solution for solving NP problems: Generate every possible solution, and check each one for correctness
  * Particular example: Traveling Salescritter Problem
    * Given N cities with roads connecting them and distances associated with those roads
    * Is there a path that goes through all of the cities and has length under M?
    * One solution to TSP: List every possible order of the cities and choose the smallest O(n!)
    * No solution whose running time is bounded by a polynomial has been found!
    * Most computer scientists believe that none will ever be found.
    * So what do we do with these kinds of problems (many of which are very real)?
      * Approximate or trust your luck!
* "I think I heard about it, but I didn't learn anything" -- C.S. on her career in CS.
* Sometimes design new data structures, too
* CSC301

Theoretical Computer Scientists
* Pretend to be mathematicians
* Prove things like "There are problems for which no computational solution exists" (e.g., the Halting problem)
  * Prove things like "No computational solution exists for *this particular problem*"
* Prove weird variants of P vs. NP: Oracular complexity
* Develop new models of computation
* CSC341

Artificial Intelligence
* Once upon a time: Attempted to develop computational simulations to intelligence
  * Failed!
* AI looks at interesting mechanism for solving problems that are less "predictable" than normal mechanisms
* One solution: Neural networks
  * A network (collection of connected "neurons")
  * Some set of input connections
  * Some set of output connections
  * Each neuron uses some formula to change its inputs to outputs
  * We "train" the network by giving it input/output pairs
* Another solution: Genetic programming
* Yes, these funky solutions have been successful in a wide variety of cases
* CS261

Software Engineering
* How do we improve the process of building software?
* More verifiable solutions
  * Proof is hard
  * Testing is often inadquate
* New policies/strategies for building software
* Open source movement (and philosophies of)
* Tools to support programmers (Eclipse, Emacs, RCS, Make)
* CS223

Human Computer Interaction (in Engineering: Ergonomics)
* How do we measure the "usability" of a computer program
* How do we make programs more usable?
* Design new interface mechanisms and models
* Not in the grinnell curriculum (except as i.s.)

And lots lots more