CSC148 Notes Lec3 PDF

Preview

Summary

CSC148 Notes Lec3...

Description

CSC 148 Introduction to Computer Science Who am I? Industry experience. Geac, Bakerstreet. Consulting experience. Cantel, Trimark, O'Donnell, RBC, ... Academic experience. Computational Geometry, Computational Complexity Teaching: 108, 148, 207, 209, 290, 236, 309 (designed), 363, 343, 347 (designed), 320, 350, 470, 492, ..., best instructor Why is CS hard? A level of abstraction above. What is an expert? Minimal effort, maximal effect. How to become good? Repeat until its easy. Must think and do. Why do I call on you in class? Why am I 'not prepared'? Make me sweat! Will I teach you everything? No and Yes! python.org The result: You have the magicwand... Image Morphing James McCrae Students at IBM, RIM, Google, Microsoft, ... eUnity (our students companies)

Programming versus Science CSC108 CSC Building blocks of a program Control structures: if statements, CS: Mo of compu ion and h o use th m to effective ve prob ems. For 148... loops a Structu ( Useful tures in gramming la ge) : dictionaries, lists, stacks, Functions: function definition, function call queues, tr , graphs Classes: instanc es, methods Algori s: How t te them w to meas hem Style conven All in a particula

Steps to 1

he problem.

ocumentat on, played w

the Python command line etc.

exercises.py

ards. follows...

recursion, using only python string functions etc.

or example, rocess to carry out) for

e points with the

c) A d) Fin re are 3) Write a function is_ That is, s and t 'star', 'rats' and is_jumble('star', 'ra Write it four times as a) is_jumble1(s,t): The f

nd top right point, . side the box. specified by bottom-left and top-right points) ed means that the top and bottom of the s. The left and right sides of the rectangle n true iff strings s and t are jumbles of eachother. cters, but possibly in a different order. For example, jumbles of eachother, so umble('arts', 'star')==True but is_jumble('star', 'ssttar')==False s: ction uses while loops (no for loops)

b) is_jumble2(s,t): The function uses for loops (no while loop) c) is_jumble3(s,t): The function is only a couple of lines long, no loops and recursion, using only python string functions etc. d) is_jumble4(s,t): The function uses recursion, no loops etc. 3) Hard Computational geometry problems (just something to think about) a) Find the smallest rectangle which contains p. I don't care if the rectangle is axis-oriented or not. Also, what is the right notion of 'smallest' (area or perimeter)? You can play with both and see what turns up. b) Given a line and two points, determine whether both points are on the same side of the line or not. That is return true if both boints are on the same side of e line and false otherwise. c) Suggest an approach for finding a convex hull for the points in p. The convex hu s mallest convex polygon which contains p. convex means that the polygon has no ind tions. You can think about it as the result of shrinking a rubberband around p until it can't shrink anymore. http://en.wikipedia.org/wiki/File:ConvexHull.svg...