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