Notes for CSC 162, 19 Jan. 2010 ff Chapter 1 of the text ---------------------------------------- Opening exercise Imagine it's 1943. You're a law clerk, charged with organizing the records of a newly created law firm. How do you expect people to use the files? What sorts of questions will they want to answer -- what sorts of things will they want to look up? - records of a particular case, by - date - plaintiff / defendant / client name - court docket # - all cases with given - plaintiff - defendant - judge - point of law - size of award How would you organize the files to facilitate these queries? By - date? - docket #? - name of plaintiff / defendant / client? What other indices would you keep? How hard would it be to find things for which you don't have an index? What shortcuts might be possible? ** The list of operations you want the files to support is analogous to an Abstract Data Type (ADT). The physical organization is analagous to a Data Structure (DS). It's *very important* to distinguish between these two concepts. We will look at three main things this semester: ADTs, DSes, and algorithms. ---------------------------------------- Big-O How many people have heard of this? It captures the notion of *asymptotic complexity* -- how much time (and sometimes space) it takes to solve a problem of a given input size. If you keep taking CS, you'll learn a lot more about this in 173, 280, or 282. We'll deal with it very informally this semester. Sorting is a canonical example. For lists of length N, we'll look at sorts that take time proportional to 2^N, N^2, N log N, and (in special cases) N. Note that if N is big enough, 1,000,000 N log N is still less than N^2. (Does everybody know what log is?) ======================================== Administration Prerequisite: 161 or equivalent. Course web site: www.cs.rochtester.edu/u/scott/162/ - syllabus - schedule - assignments - my lecture notes (such as they are) Text: Problem Solving with Algorithms & Data Structures using Python, by Miller & Ranum Using Python 2.6 (what's in the book, and was used in 161). If you have an older or newer version, you should get a copy of this one. Recommend the IDLE GUI, Zelle's simple graphics.py. (Anybody not in 161 last fall?) Projects will be handed in through Blackboard. There's also a Blackboard discussion group, and you can see your grades there as well. Does everybody know how to use BlackBoard? (my.rochester.edu) Lab I'd like to have just one of these. Most students signed up for the TR 4:50-6:05 session. I'd like to ask the three who signed up for the later session to switch. Two have agreed via e-mail. How about Cheng-Tse Lee? Lab sessions will be mainly a place/time to work on homework assignments with a helpful TA present. They will be staffed by UG TAs. Workshop Again, with such a small class, we need only one of these. Let's find a time (probably evening or weekend). Workshop leader will be Aaron Gorenstein. Grading There will be homework projects (roughly one every other week), quizes (one per week, based on Workshop material), and midterm and final exams. Grading will be roughly class participation 15% programming projects 20% homework/lab assignments 10% quizes 15% workshop attendance 5% midterm 15% final 20% Note the score for class participation! NO LATE ASSIGNMENTS. Academic Honesty My standard policy: consult whomever you want, work with classmates as much as you like, but take no written notes away from any meeting. All written work has to come out of your own head (see the web for more details). Lots more detail, including grading scale for code, is on the web. ======================================== Review of Python interpreter GUI (IDLE) python.org # documentation, downloads data types integer, long integer, real, complex (we won't use the latter) >>> 7/3 2 >>> 7.0/3 2.3333333333333335 >>> 10**20 100000000000000000000L conversions float() int() long() boolean >> not (False or True) False sequences support (among other things) [ ] indexing + concatenation in membership len a:b slice from a through b-1 strings -- immutable sequences of characters, delimited w/quotes support (among other things) s.center(w), s.ljust(w), s.rjust(w) # field width w s.lower(), s.upper() s.count(t) # string t s.find(t) # returns index s.split(c) # returns list, uses white space if c is missing # will also split on a _string_ note distinction between methods and functions former are ~shorthand for the latter Q: how come 3.__add__(4) doesn't work, but (3).__add__(4) does? lists -- heterogeneous mutable sequences, delimited with brackets what many languages call vectors first index is 0 support (among other things) l.append(x) l.insert(i, x) l.pop(i) # remove & return ith element; last if i is missing l.sort(), l.reverse() del l[i] # remove ith element l.index(x) # first occurrencce l.count(x) # number of occurrences l.remove(x) # remove first occurrence probably maintained internally as an array with end index resize as needed when run out of space adding at the end is usually cheap; occasionally expensive adding at the beginning is expensive removing at either end is usually cheap; occasionally expensive tuples like immutable lists, delimited with parens exist separately because they're cheaper to manage can be returned from functions (a, b) = getPair() a, b = getPair() # also ok dictionaries like unordered sets of pairs delimited with braces squares = {1:1, 2:4, 3:9, 4:16} support (among other things) d.keys(), dd.values() # lists d.items() # list of (key, value) tuples d.get(k), d.get(k,alt) # None or alt if missing d.has_key(k), k in d # former dropped from Python 3 d[k] = v, del d[k] None variables created when first assigned to local to current subroutine unless overridden with /global var_name/ control flow if, if...else for v in collection range(n) --> [0, 1, 2, ..., n-1] if collection is a dictionary, iterates over keys, not pairs while exceptions try: # protected code except excType: # handler except excType as e: # if excType is nontrivial, can get at its insides using e except: # catches everything -- dangerous finally: # executed at end, regardless of exceptions else: # has to come last # ececuted at end, but only if there are no exceptions raise excType # trivial type raise excType(args) # nontrivial type assert functions def square(n): return n*n classes class Fraction: def __init__(self, n, d): self.num = top self.den = bottom # assignments create fields def __str__(self): return str(self.num) + "/" + str(self.den) def __add__(self, other): sum_n = self.num*other.den + self.den*other.num sum_d = self.den*other.den return Fraction(sum_n, sum_d) # not in lowest terms -- see lab exercise def integral(self): return self.num % self.dem = 0 inheritance class sprocket(part): # add methods # redefine methods def __init__(args): part.__init__(part_args)