COMPSCI 100, Java-style Owen AstrachanWhat is Computer Science?Programming != Computer ScienceEfficient design, programs, codeCourse OverviewQuestionsTradeoffsOO design in code/wordcountFast, cheap, out-of-control?Some Java Vocabulary and ConceptsBasic data structures and algorithmsTracking different/unique wordsWhat does try to do? Why is it wrong?Search: measuring performanceTradeoffs in processing and countingBenefits of inheritance, interfacesWhy inheritance?Example of inheritanceInheritance (language independent)Who is Alan Perlis?CPS 1001.1COMPSCI 100, Java-styleOwen Astrachanhttp://www.cs.duke.edu/courses/cps100/fall04http://www.cs.duke.edu/~olaCPS 1001.2What 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 a 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)HoareCPS 1001.3Programming != Computer ScienceWhat is the nature of intelligence? How can one predict the performance of a complex system? What is the nature of human cognition? Does the natural world 'compute'?It is the interplay between such fundamental challenges and the human condition that makes computer science so interesting. The results from even the most esoteric computer science research programs often have widespread practical impact. Computer security depends upon the innovations in mathematics. Your Google search for a friend depends on state-of-the-art distributed computing systems, algorithms, and artificial intelligence.http://www.post-gazette.com/pg/pp/04186/341012.stmCPS 1001.4Efficient design, programs, codeObject-oriented design and patterns. Software design principles transcend language, but …Engineer, scientist: what toolkits do you bring to programming? Mathematics, design patterns, libraries --- standard and Duke CPSKnow data structures and algorithms. Trees, hashing, binary search, sorting, priority queues, greedy methods, …Using the language: Java (or C++, or Python, or …), its idioms, its idiosyncraciesCPS 1001.5Course OverviewLectures, Recitations, Quizzes, ProgramsRecitation based on questions given out in previous week•Discuss answers, answer new questions, small quiz•More opportunities for questions to be answered.Lectures based on readings, questions, programs•Online quizzes used to motivate/ensure reading•In-class questions used to ensure understandingPrograms•Theory and practice of data structures and OO programming•Fun, practical, tiring, …•Weekly programs and longer programsExams/TestsSemester: closed bookFinal: open bookCPS 1001.6QuestionsIf you gotta ask, you’ll never knowLouis Armstrong: “What’s Jazz?”If you gotta ask, you ain’t got itFats Waller: “What’s rhythm?”What questions did you ask today? Arno PenziasCPS 1001.7TradeoffsSimple, elegant, quick, efficient: what are our goals in programming? What does XP say about simplicity? Einstein?How do we decide what tradeoffs are important? Tension between generality, simplicity, elegance, …Fast programs, small programs, run anywhere-at-all programs. Runtime, space, your time, CPU time…Programming, design, algorithmic, data-structuralCPS 1001.8OO design in code/wordcountCount number of different words in an array, how can we accommodate more than one approach?public interface UniqueCounter { public int uniqueCount(String[] list);}Three (ore more) approaches: CPS 1001.9Fast, cheap, out-of-control?This is valid and correct Java code, questions?import java.util.*;public class SetUniqueCounter implements UniqueCounter { public int uniqueCount(String[] list) { TreeSet set = new TreeSet(); set.addAll(Arrays.asList(list)); return set.size(); }}CPS 1001.10Some Java Vocabulary and ConceptsJava has a huge standard libraryOrganized in packages: java.lang, java.util, javax.swing, …API browseable online, but Eclipse IDE helps a lotJava methods have different kinds of access inter/intra classPublic methods …Private methods …Protected and Package methods …Primitive types (int, char, double, boolean) are not objects but everything else is literally an instance of class Objectfoo.callMe();CPS 1001.11Basic data structures and algorithmsArrays are typed and fixed in size when createdNot like vector/tvector in C++/TapestryDon't have to fill the array, but cannot expand itCan store int, double, String, Foo, …ArrayList (and related class Vector and interface List) growsStores objects, not primitivesAccessing elements can require a downcastArrayList objects grow themselves intelligentlyjava.util package has lots of data structures and algorithmsUse rather than re-implement, but know how do to do bothCPS 1001.12Tracking different/unique wordsWe want to know how many times ‘the’ occursDo search engines do this? Does the number of occurrences of “basketball” on a page raise the priority of a webpage in some search engines?•Downside of this approach for search engines?Constraints on solving this problemWe must read every word in the file (or web page)Search for the word? Avoid counting twice? Store?Are there fundamental limits on any of these operations? Where should we look for data structure and algorithmic improvements?CPS 1001.13What does try to do? Why is it wrong?public class SlowUniqueCounter implements UniqueCounter{ public int uniqueCount(String[] list) { int count = 0; int diffSize = list.length; for(int k=0; k < diffSize; k++){ String word = list[k]; count++; for(int j=k+1; j < diffSize; j++){ if (list[j].equals(word)){ list[j] = list[diffSize-1]; diffSize--; } } } return count; }}CPS 1001.14Search: measuring performanceHow fast is fast enough? /** pre: a contains a.size() entries * post: return true if and only if key found in a */ boolean search(ArrayList a, String key) { for(int k=0; k < a.size(); k++) if (a[k].equals(key)) return true; return false; }Java details: parameters? Return values? ArrayLists?How do we measure performance of code? Of
View Full Document
Unlocking...