DOC PREVIEW
Duke CPS 100E - Dietolf (Dee) Ramm

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CompSci 100E1.1CompSci 100EDietolf (Dee) Rammhttp://www.cs.duke.edu/courses/cps100e/spring05http://www.cs.duke.edu/~drCompSci 100E1.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)HoareCompSci 100E1.3Programming != Computer Scienceÿ What 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.stmCompSci 100E1.4Efficientdesign, 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 idiosyncraciesCompSci 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 work o 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 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-structuralCompSci 100E1.8OO design in code/wordcountÿ Count number of different words in an array, how can we accommodate more than one approach?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 but everything 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 of occurrences of “basketball” on a page raise the priority of a webpage 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 algorithmic improvements?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();


View Full Document

Duke CPS 100E - Dietolf (Dee) Ramm

Documents in this Course
Topics

Topics

9 pages

Lecture

Lecture

3 pages

Notes

Notes

2 pages

Hashing

Hashing

19 pages

Lecture

Lecture

59 pages

Lecture

Lecture

6 pages

Lecture

Lecture

4 pages

Lecture

Lecture

20 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

7 pages

Lecture

Lecture

8 pages

Lecture

Lecture

10 pages

Lecture

Lecture

4 pages

Notes

Notes

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Lecture

Lecture

13 pages

Lecture

Lecture

6 pages

Lecture

Lecture

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

5 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

10 pages

Sets

Sets

14 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Test 1

Test 1

7 pages

Load more
Download Dietolf (Dee) Ramm
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Dietolf (Dee) Ramm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Dietolf (Dee) Ramm 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?