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