CSC152 2004F, Class 55: An Overview of CS

Admin:
* Participation grades distributed
  * Sam generally errs on the harsh side
  * Feel free to correct!
* Attempting to decrease their participation grade:  Eric (just really late)
* Questions on exam?
  * For problem 4, tell me about the hash table
public class DynamicArrayImplementedWithJavaUtilHashtable
{
	Hashtable stuff;
	public DAIWJUT()
	{
		this.stuff = new Hashtable();
	}

	public Object get(int i)
	{
		...
	}

	public void set(int i, Object o)
	{
		...
	}

	public String toString()
	{
	}
}
  * What should toString return?  (E.g., for something with only value 5 set?)
    * [null,null,null,null,null,hello] // use a for loop
    * [5:hello]  // use keys()
    * Either is acceptable (as is any alternative that actually shows the contents and helps us figure out the index)
  * Do we have to deal with infinite sets? NO, just finite sets whose elements you know.
  * Do we have to permit null to be in the set?  It's up to you.
  * Do we have to permit empty sets?  Yes.
  * What do you mean by "increment steps by 1+ub-lb?"
    * I mean "increment steps by 'the number of things in the subarray'"
  * Should we be able to convert sets to strings?
    * Not necessarily
  * Should we be able to iterate sets?
    * Not necessarily
  * Does it matter what order the elements appear?
    * If you don't iterate and don't print, the elements never appear
  * If we iterate or convert to strings, does it matter?
    * No
* Custom evaluation due Friday.
* Standard evaluation filled out in class on Friday.
* Cool thing Saturday: Kumail the Komedian (7 pm, South Lounge) Extra Credit
* Extra credit options:
  * Osgood Convo
  * Chemistry Convo
  * Body Image Convo
  * Whiteness Convo
  * Women's Soccer Finals
  * Arjun Guha (Math)
  * Cassie Schmitz, Sam Martin, and Stephane Nyonbayire
  * American Studies Master Class on Incarceration
  * Davis Hart, Oge Nnadi, Dimitar Tasev
  * Liberal Arts Debate
  * Kumail Nanjiani (coming Saturday)
* About grades in this class
  * Person group doesn't get a project grade.  I multiply their grade by 5/4
  * Participation: 10%
  * Homework (percent done): 10%
  * Project: 20%  (not less than B)
  * Exams: 20% each
  * Example: 87, six extra credit 90
  * 94+: A
  * 90-93: A-
  * 87-89: B+
  * 84-86: B
  * 80-83: B-
  * 77-79: C+
  * Almost anything else: C

Overview:
* What is CS? Revisited
* Subareas of CS
* The Grinnell curriculum

What is Computer Science?
* The study of algorithms and data
* The study of formalized problem solving
* Computer science combines ideas from
  * Mathematics (proof, analysis)
  * Engineering (building stuff)
  * "Science" (approach to world; test-based analysis)
  * Other disicplines?

Many different ways to study algorithms and data
* Implement them in software (Software Engineering; Programming)
  * CSC151, CSC152, CSC201
  * CS223: Software Design (F)
* Implement algorithms in hardware (Architecture, Computer Organization, Computer Engineering)
  * CS211: Architecture (alternate F)
  * PHY220: Electronics (F)
* Design new ones (and look at techniqeus for design
* Analyze them for running time (Algorithm Analysis)
  * CSC301: Algorithms (F)
* Ask whether they exist or whether efficient ones exist (Theory; Computational Complexity)
  * CSC341: Automata, Formal Languages, and Computational Complexity (S)
* Design languages in which algorithms can be expressed (Programming Languages)
  * CSC302: Programming Languages
* Implement languages in which algorithms can be expressed (Compilers)
  * CSC362: Compilers
* Consider the impact of algorithms on society (Computers in Society)
  * CSC105: A Social and Algorithmic Overview of Computing
  * Yes, we should have a majors course, too
* Consider the usability of algorithms implemented as programs (Human-Computer Interaction; CHI; Ergonomics)
  * Not in our curriculum
* Apply algorithms to the problem of modeling human thought (AI)
  * CSC262: AI (Alternate F)
* Devise algorithms and data structures for managing large collections of data (Databases)
  * Not in our curriculum
* Implement algorithms and data in software to support other algorithms (Operating Systems)
  * CSC213: Operating Systems (Alternate F)
* Prove algorithms correct
  * CSC201

As we design languages, we also design "paradigms" for thinking about expressing algorithms

* Functional: Model algorithms as compositions of functions (Scheme)
  late 1950's as programming language (LISP)
  1920's as logical model
* Imperative: Model algorithms as sequenced operations (Cookbooks, The implementation of many methods in Java, begin blocks and do loops in Scheme)
  as old as algorithms
* Object-Oriented: Model algorithms as compositions of objects (Java)
  mid 1960's (Simula67)
* Declarative: Model algorithms as "facts plus automatic means of using those facts" or "say what you want but not how its computed" (Prolog, SQL, Regular Expressions)
  early 1970's (Prolog)
  * A sorted version of list l is a permution of list l.
  * A sorted list is a list in which each element is no smaller than its preceding elements
  * Find me a sorted version of [4,2,3,1]

Are there algorithms that cannot exist?
* Yes: There are algorithms that can be proven to be impossible.
* An interesting one: Write an algorithm, halts, that takes two input: an algorithm and the input to that algorithm.  halts returns true if the input algorithm terminates and false if it runs forever.

	while (true)
		;

	void f(i)
	{
		if (i == 0)
			return 1;
		else
			return f(i-1);
	}

There are also problems for which no known efficient algorithm
exists and theorems about the relationships of those problems

Approximation algorithms: How to approximate the answers to those
algorithms efficiently

SEE YOU FRIDAY