CS4HS Workshop @ Columbia University Computer Science vs. Computer Programming Adam Cannon Department of Computer Science Columbia University July 7, 2011 [email protected] 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! [email protected] CS Enrollements Just how bad is it? This data is from the CRA annual Taulbee surveys (see more at http://www.cra.org)

[email protected] 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. [email protected] Big Slice of Pie [email protected] 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? [email protected] 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. [email protected]

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.

[email protected] 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! [email protected] 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 [email protected] 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]

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! [email protected] Computer Science: Whats 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 [email protected] 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 [email protected] What About Jobs?

Technology Applications Finance Preparation for a professional School Graduate school research [email protected] 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-Happiness-Explosion/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 [email protected]