Transcript CSvsCP - Columbia University

CS4HS Workshop @ Columbia University
Computer Science
vs.
Computer Programming
Adam Cannon
Department of Computer Science
Columbia University
July 7, 2011
CS@CU
Outline



Motivation: The Numbers
Preliminary Definitions
Algorithmic Thinking




Some everyday examples
Some slightly more technical examples
Analyzing algorithms
Computer Science Today and Tomorrow
Why Are We Here?




In the last 10 years CS enrollments at
US colleges has declined sharply
CS education is important not just for
future STEM professionals
We believe part of the problem is
perception
We need your help!
CS@CU
CS Enrollements
Just how bad is it?
This data is from the CRA annual Taulbee surveys
(see more at http://www.cra.org)
CS@CU
Degree Production vs. Job Openings
160,000
140,000
120,000
100,000
80,000
60,000
40,000
20,000
Sources: Thanks to Eric Roberts. Adapted from a presentation by John Sargent, Senior Policy Analyst, Department of Commerce, at
the CRA Computing Research Summit, February 23, 2004. Original sources listed as National Science Foundation/Division
of Science Resources Statistics; degree data from Department of Education/National Center for Education Statistics:
Integrated Postsecondary Education Data System Completions Survey; and NSF/SRS; Survey of Earned Doctorates; and
Projected Annual Average Job Openings derived from Department of Commerce (Office of Technology Policy) analysis of
Bureau of Labor Statistics 2002-2012 projections.
See http://www.cra.org/govaffairs/content.php?cid=22.
CS@CU
Big Slice of Pie
CS@CU
A popular misconception
• Cultural stereotypes
• CS is nerdy
• CS is for men
• Misconceptions about careers in
computing
• There are no jobs
• CS is like solitary confinement
• CS and CP are the same thing
• Who is to blame?
• Media?
• AP exams?
• Wall Street?
CS@CU
Preliminary Definitions
Computer Science
(Gibbs and Tucker, 1986)
The study of algorithms including
•
•
•
•
Their
Their
Their
Their
formal and mathematical properties
hardware realizations
linguistic realizations
applications
Preliminary Definitions
Algorithm:
Dictionary Definition: A procedure for solving a mathematical
problem in a finite number of steps that frequently involves
repetition of an operation; broadly: a step-by-step method of
accomplishing some task.
Preliminary Definitions
Computer Programming:
Dictionary Definition: Constructing a sequence of
instructions to enable a computer to perform a specific
task.
CS@CU
Algorithmic Thinking
• Algorithms extract the intelligence from a task
• Algorithms can amplify human intellect
• We employ algorithmic thinking everyday
• To do lists
• Optimizing travel by subway
• Cooking dinner
• Sorting laundry
• Playing sports
Whether or not we are interested in a career in computer
science we cannot escape the profound effect it has on our
lives every day.
CS@CU
Introduction to Algorithms
There are three components to an algorithm:
1.
2.
3.
A set of inputs, where each input is a finite sequence of items.
A set of outputs, where each output is a finite sequence of items.
A method consisting of a finite sequence of instructions, each one of
which can be mechanically executed in a fixed length of time with a
fixed amount of resources. The method must produce an output for
each input in the set of possible inputs in a finite amount of time.
Introduction to Algorithms

Input size: associated with each input is a measure
of its size. How we measure the size can vary from
problem to problem.
Examples:



Number of digits as in the number of digits in a number
(Often we use binary digits).
Number of characters in a string.
Number of items as in the number of items to be searched
or sorted.
Your first Algorithm
Linear Search: (also called sequential search)
Algorithm to determine whether a given name x appears
on a list.
Input: A list of n ≥1 names A[1], A[2], ... , A[n],
and a given name x.
Output. The message "Sorry, x is not on the list" if x is not
on the list.
Otherwise, the message: "x occurs at position i on the list."
Linear Search
Searching a phone book:
1.5 Million people in Manhattan
I can scan 15 names/second
This could take me 100,000 seconds
Which is about 28 hours!
Not a great algorithm for searching
the phone book
Binary Search





Searching a sorted list
How can we exploit the structure that a
sorted list provides?
Start in the middle and determine in which
half of the list our target lives
Repeat this procedure eliminating half of the
remaining list elements on each iteration
What is the maximum number of
comparisons required here?
Binary Search
Each time I check a name I eliminate half of the
remaining names.
At most how many names must I check in the
previous phone book example?
log2(1.5 million)
This is only about 21 names!
CS@CU
Where does programming fit in?



Suppose we want a computer to
execute the algorithms we just
described
We need a notation that specifies
instructions that a computer can
execute
Pseudocode is an informal example of
what this notation might look like
CS@CU
Pseudocode for Linear Search
found = "no";
i=1;
while (found == "no" and i <= n)
{
if (A[i] == x)
{
found = "yes";
location = i;
}
i++;
}
if (found == "no")
{
print ("Sorry, " + x + " is not on the list");
}
else
{ print (x + " occurs at position " + location +
" on the list");
}
Pseudocode for Binary Search
found = "no";
begin = 1;
end = n;
while (found == "no" and begin  end)
{
m = begin + floor((end-begin)/2)
if(A[m] == x)
{
found = "yes";
location = m;
}
if(A[m]>x)
end = m-1;
if(A[m]<x)
begin = m+1;
}
if (found == "no")
{
print ("Sorry, " + x + " is not on the list");
}
else
{ print (x + " occurs at position " + location +
" on the list");
}
Computer Science Today





Designing software/hardware systems
 Personal computers (Windows, OSX, Linux)
 Tablets
 Smartphones
 Xbox
Creating services/businesses
 Google
 Facebook
 eBay
Solving problems
Amplifying the intellect
Having fun, serving society, and making a profit!
CS@CU
Computer Science: What’s inside?








Software and hardware systems
Networks, security, embedded systems
Theoretical foundations
Multimedia generation and user interfaces
Information representation, management, and
data mining
Vision, graphics, and robotics
Computational biology, quantum computing
Machine learning, artificial intelligence
CS@CU
CS Research Groups at Columbia












Asynchronous Circuits and Systems
Group
Autonomous Agents Lab
Columbia Automated Vision
Environment
Columbia Vision and Graphics
Center
Computational Biology
Computer Architecture and Security
Technology Laboratory
Computer Graphics Group
Center for Computational Learning
Systems
Computer Graphics and User
Interfaces Laboratory
Database Research Group
Digital Libraries
Distributed Computing and
Communications Laboratory














Distributed Network Analysis
Research Group
Information-Based Complexity
Internet Real-Time Laboratory
Intrusion Detection Systems
Languages and Compilers Group
Machine Learning
Natural Language Processing
Group
Network Computing Laboratory
Network Security Laboratory
Programming Systems Laboratory
Robotics Laboratory
Systems Security Center
Spoken Language Processing
Group
Theory of Computing Group
CS@CU
What About Jobs?





Technology
Applications
Finance
Preparation for a professional School
Graduate school  research
CS@CU
Want to learn more?
Check out these resources:
Contact me: [email protected]
Check out these great papers:

http://www.cs.cmu.edu/afs/cs/usr/wing/www/publications/Wing06.pdf

http://www.cs.princeton.edu/%7Echazelle/pubs/algorithm.html
Or check out these books:

http://www.amazon.com/Blown-Bits-Liberty-HappinessExplosion/dp/0137135599/ref=sr_1_1?ie=UTF8&qid=1310015907&sr=8-1

http://www.amazon.com/Fluency-Information-Technology-ConceptsCapabilities/dp/0136091822/ref=sr_1_1?s=books&ie=UTF8&qid=1310016060&sr=1-1
CS@CU