What is Computer Science?

"What is it that distinguishes it from the separate subjects with which it is related?
What is the linking thread which gathers these disparate branches into a single discipline?
My answer to these questions is simple -- it is the art of programming the computer.
It is the art of designing efficient and elegant methods of getting a computer to solve problems, theoretical or practical, small or large, simple or complex."

C.A.R. (Tony) Hoare







Why is Programming Fun?

What delights may its practitioner expect as a reward?

First is the sheer joy of making things.

Second is the pleasure of making things that are useful

Third is the fascination of fashioning complex puzzle-like objects of interlocking moving parts

Fourth is the joy of always learning

Finally, there is the delight of working in such a tractable medium. The programmer, like the poet, works only slightly removed from pure thoughtstuff.










Efficient Programming

• Designing and Building efficient programs requires knowledge and practice

  • Hopefully the programming language helps

  • Object-oriented concepts and general programming concepts help in developing programs

  • Knowledge of data structures and algorithms help

• Tools of the engineer/scientist programmer
  • A library or toolkit is essential, don't reinvent

  • Someone must build the tools

  • Programming is not just art, not just science, not just engineering

Course Overview

• Lectures, Recitations, Quizzes, Programs

  • Lectures

    based on reading, inclass questions, group work, quizzes

    ask questions

  • Recitations

    questions before, questions during, quiz

    ask questions

  • Programs

    theory and practice of data structures, OO programming

    Fun, practical, tiring...

  
  
  
  
  
  
  
  
  
  
  Tradeoffs
  • Course is about tradeoffs

    • Programming: simple, elegant, quick to run/to program

    • Structural: how to structure data for efficiency

      • Issues in efficiency? Time, space, programmer-time

    • Algorithmic: similar to structural issues

  • How do we decide which choice to make, what tradeoffs are important?
  
  
  
  
  
  
  
  
  
  
  Review
  • Chapter 7

    • Read

    • Design, iterative enhancement

    • Quiz and Random Walks - Example programs

  • Chapter 8
    • Read/Skim

    • tvector

    • built-in arrays

  • Chapter 9
    • Read/Skim

    • Strings

  
  
  
  
  
  
  
  
  
  
  readwords.cpp
  
  Reads words, how can we count different/unique words

  
  
  

  tvector<string> list; string filename,word; cin >> filename; ifstream input(filename.c_str()); CTimer timer; timer.Start(); while (input >> word) { list.push_back(word); } cout << "Last word was " << list[list.size()-1] << endl; timer.Stop(); cout << "read " << list.size() << " words in "; cout << timer.ElapsedTime() << " seconds" << endl;
  
  
  
  
  
  
  
  
  
  Tracking different/unique words

• How many times does the word "the" occur?
  • Do search engines do this?

    Do the number of occurences of "basketball" on a web page raise its priority in search engines?

    Downside in search engines?

• Constraints on solving this problem?
  

  • Must read every word in the file or web page

  • Must search - word been read before?

  • Must process word - bump count, store word)

    
    
    

  • Are there fundamental limits on these operations?

Search: Measuring Performance

• How fast is fast enough?
  bool search(const tvector<string> & a, const string & key) // pre: a contains a.size() entries // post: returns true if and only if key found in a { int k; int len = a.size(); for (k=0; k < len; k++) { if (a[k] == key) return true; } return false; }

• C++ details: parameters? return values? vectors?

• How do we measure performance of the code? of algorithm?

  Does processor make a difference?

Tradeoffs in Reading/Counting

• If you read all the words, then sort them, can we determine unique words?
  
  
  
  frog, frog, frog, rabbit, turtle, turtle, turtle, turtle

• If we look up words as we're reading them, bump a counter if find a word, is this slower than previous idea?

  How do we look up a word? How do we add a word?

• Are there kinds of data that make one approach preferable?

  What is best case, worst case, average case?

Structuring data: readwords4.cpp

• Search for a word using binary search

  • Differences from sequential/linear search?

  • What's a precondition for binary search to work?

• How can we store new words so that binary search will work?
  • Add to end of vector and sort the vector
  • Add to end of vector and shift(down) until location found
  • Advantages of one method over another?

    What about C++ details in using a struct/class to store data, how are comparisons made?

---

Susan H. Rodger

Last modified: Tue Aug 27 11:28:14 EDT 2002