CompSci 100E1.1CompSci 100EDietolf (Dee) Rammhttp://www.cs.duke.edu/courses/cps100e/spring06http://www.cs.duke.edu/~drCompSci 100E1.2What is Computer Science?What is it that distinguishes it from theseparate subjects with which it is related?What is the linking thread which gathers thesedisparate branches into a single discipline?My answer to these questions is simple --- it isthe art of programming a computer. Itistheartof designing efficient and elegant methods ofgetting a computer to solve problems,theoretical or practical, small or large, simpleor complex.C.A.R. (Tony)HoareCompSci 100E1.3Programming != Computer Scienceÿ What is the nature of intelligence? How can one predict theperformance of a complex system? What is the nature ofhuman cognition? Does the natural world 'compute'?ÿ It is the interplay between such fundamental challenges andthe human condition that makes computer science sointeresting. The results from even the most esoteric computerscience research programs often have widespread practicalimpact. Computer security depends upon the innovations inmathematics. Your Google search for a friend depends onstate-of-the-art distributed computing systems, algorithms,and artificial intelligence.http://www.post-gazette.com/pg/pp/04186/341012.stmCompSci 100E1.4Efficientdesign, programs, codeObject-oriented designand patterns. Softwaredesign principlestranscend language,but …Engineer, scientist:what toolkits do youbring to programming?Mathematics, designpatterns, libraries ---standard and Duke CPSKnow data structuresand algorithms. Trees,hashing, binarysearch, sorting,priority queues,greedy methods, …Using the language:Java (or C++, orPython, or …), itsidioms, itsidiosyncraciesCompSci 100E1.5Course Overviewÿ Lectures, Labs, Quizzes, Programsþ Lectures based on readings, questions, programso Online quizzes used to motivate/ensure readingo In-class questions used to ensure understandingþ Programso Theory and practice of data structures and OO programmingo Fun, practical, tiring, …o Weekly programs and longer programsþ Labs based on current worko Get in practical stuffo Become familiar with toolsÿ Exams/Tests (closed book)þ Two “midterms”þ FinalCompSci 100E1.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 PenziasCompSci 100E1.7TradeoffsSimple, elegant, quick,efficient: what are ourgoals in programming?What does XP sayabout simplicity?Einstein?How do we decidewhat tradeoffs areimportant? Tensionbetween generality,simplicity, elegance, …Fast programs, smallprograms, runanywhere-at-allprograms. Runtime,space, your time, CPUtime…Programming, design,algorithmic, data-structuralCompSci 100E1.8OO design in code/wordcountÿ Count number of different words in an array,how can we accommodate more than oneapproach?public interface UniqueCounter {public int uniqueCount(String[] list);}ÿ Three (or more) approaches:þþþCompSci 100E1.9Fast, cheap, out-of-control?ÿ This is valid and correct Java code, questions?import java.util.*;public class SetUniqueCounterimplements UniqueCounter {public int uniqueCount(String[] list) {TreeSet set = new TreeSet();set.addAll(Arrays.asList(list));return set.size();}}CompSci 100E1.10Some Java / Matlab Differencesÿ Compile & Execute vs Interactiveþ In Java, compile, then run (execute)–like.m filesþ Matlab executes as you type in programÿ Java requires declaration of variablesþ Need to tell about the variable before creatingþ Declaration is distinct from Definition (creation)ÿ Java is not matrix orientedþ Operators (+, -, *, /, %), do not work on matricesþ You must write code with loops for matrix operationsþ - or use functions (methods)CompSci 100E1.11Some Java / Matlab Differencesÿ No exponentiation operatorþ Cannot say X^3 for X3þ Use X*X*X or a functionÿ Syntax differencesþ Use of braces, { ... }, in place of xxx … endþ Semicolon has somewhat different meaningþ Use quotes, ” ... ”, for strings not ’... ’þ Loops and if require parentheses (...)ÿ You’ll find many more differencesþ Will be an annoying, but transient problemCompSci 100E1.12Some Java Vocabulary and Conceptsÿ Java has a huge standard libraryþ Organized in packages: java.lang, java.util, javax.swing, …þ API browseable online, but Eclipse IDE helps a lotÿ Java methods have different kinds of access inter/intra classþ Public methods …þ Private methods …þ Protected and Package methods …ÿ Primitive types (int, char, double, boolean) are not objects buteverything else is literally an instance of class Objectþ foo.callMe();CompSci 100E1.13Basic data structures and algorithmsÿ Arrays are typed and fixed in size when createdþ Not like vector in C++þ Don't have to fill the array, but cannot expand itþ Can store int, double, String, Foo, …ÿ ArrayList (and related class Vector and interface List) growsþ Stores objects, not primitivesþ Accessing elements can require a downcastþ ArrayList objects grow themselves intelligentlyÿ java.util package has lots of data structures and algorithmsþ Use rather than re-implement, but know how do to do bothCompSci 100E1.14Tracking different/unique wordsÿ We want to know how many times ‘the’ occursþ Do search engines do this? Does the number ofoccurrences of “basketball” on a page raise the priority of awebpage in some search engines?o Downside of this approach for search engines?ÿ Constraints on solving this problemþ We 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 algorithmicimprovements?CompSci 100E1.15Whatdoesittrytodo?Whyisitwrong?public class SlowUniqueCounter implements UniqueCounter{public int uniqueCount(String[] list) {int count = 0;int diffSize = list.length;for(intk=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;}}CompSci 100E1.16Search: measuring performanceÿ How 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
View Full Document
Unlocking...