CS4HS Workshop @ Columbia University Computer Science vs.

CS4HS Workshop @ Columbia University Computer Science vs.

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]

Recently Viewed Presentations

  • Genetic Variation for Maize Grain Yield in the

    Genetic Variation for Maize Grain Yield in the

    The percent genetic contribution by heterotic group and by decade computed from pedigrees for different sets of lines. SS Heterotic group founders. NSS Heterotic group founders. G2F males (NSS) Percent genetic contribution of a set of lines may not sum...
  • Attraction and Flirtation in Young Adults and Middle-Aged

    Attraction and Flirtation in Young Adults and Middle-Aged

    This research was supported by funding from the Office of Research and Sponsored Programs at the University of Wisconsin-Eau Claire. Figure 1: Young adults' and middle-aged adults' reasons for maintaining their opposite-sex friendship.
  • Vector Calculus - Ms Gugger&#x27;s Classes 2016

    Vector Calculus - Ms Gugger's Classes 2016

    The position vector, ?(?), of a golf ball at a time ? seconds is given by ??=15??+20?−4.9?2? for ?≥0, where the distance is in metres, ? is a unit vector horizontally forward and ? is a unit vector vertically upwards...
  • Cognitive processes, problem solving, and reasoning

    Cognitive processes, problem solving, and reasoning

    Deductive reasoning - A form of thinking in which one draws a conclusion that is intended to follow logically from two or more statements or premises; ... Why: the ability to make correct judgments quickly (fast) and with limited resources...
  • Rhetoric of the op-ed page

    Rhetoric of the op-ed page

    Rhetoric of the op-ed page. Erwc Module 2 ... Do these concepts apply to politics and advertising as well as person-to-person persuasion? Can you think of some examples? ... and more esoteric questions like the age of our universe, a...
  • The Second War for Independence and the Upsurge of ... - APUSH

    The Second War for Independence and the Upsurge of ... - APUSH

    How can one argue that this is an oversimplification? New Spreading Nationalism . ... Fletcher v. Peck - declared a state law unconstitutional . Martin v. Hunter's Lease - S. Court has jurisdiction over state courts in cases involving const....
  • Influences and Foundations of American Democracy

    Influences and Foundations of American Democracy

    The Preamble: When in the Course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume among the powers of the earth, the separate and equal station...
  • Periodic Table Brochure - Midland High School

    Periodic Table Brochure - Midland High School

    Back: Families, Periods. 1. 2. Front 1. ... Reading the Periodic Table. Illustration: Draw one element "square" and label element name, chemical symbol, atomic number, atomic mass. Write: Explain how to determine the number of protons, neutrons, and electrons from...