Structured Programming 1110/1140/6710
Review: Sample Exam R1
Imperative programming, standard library, types
Copyright By PowCoder代写 加微信 powcoder
Types, objects, classes, inheritance, interfaces
Naming, literals, primitives
Arrays, operators, expressions, statements, blocks
if-then-else, switch
while, do-while, for
parameters, return values
Nested classes
Integer, autoboxing, Math, Random
Character and String
Type Inference
Collections and sorting
Java exceptions, catch or specify, Java syntax
Structured Programming 1110/1140/6710 6
Review: Sample Exam R1
Object Oriented Programming
Class declaration, object creation
Initializers, access control, nested classes, enum types
Interfaces
Inheritance, overriding, polymorphism, super
java.lang.Object, final, abstract
Structured Programming 1110/1140/6710 7
Review: Sample Exam R1
“I want to know [what] we need to grasp about JavaFX. ”
JavaFX is examinable in main exam, but isn’t in the sample exam. You won’t be expected to memorize details, but understand concepts.
Structured Programming 1110/1140/6710 8
Review: Sample Exam R1
Abstract Data Types (ADTs)
List implementation 1
List implementation 2
The set ADT and its implementation
Hash tables
Map ADT implementation, ADT recap
Structured Programming 1110/1140/6710 9
Review: Sample Exam R1
Core Computer Science
Hash functions, choosing a good hash function
Hashing applications, Java’s hashCode()
Computational Complexity
Structured Programming 1110/1140/6710 10
Review: Sample Exam R1
Software Engineering
IDEs, revision control, Git
TDD, JUnit
Structured Programming 1110/1140/6710 11
Introduction to Software Systems 1110/1140/1510/6710
Introduction
Rolls XWB for the A350. Photo: AINonline
Introduction to Software Systems 1110/1140/1510/6710 13
Revision R2
Call by value and call by reference
• ParametersarevaluesinJava
• Javacannotpassobjects,justreferencestoobjects
Introduction to Software Systems 1110/1140/1510/6710 15
Methods Parameters Return values
Introduction to Software Systems 1110/1140/1510/6710
Introductory Java J7
Parameters (method arguments)
Parameters are the mechanism for passing information to a method or constructor.
• Primitivetypespassedbyvalue
– Changes to parameter are not seen by caller
• Referencetypespassedbyvalue
– Changes to the reference are not seen by caller – Changes to object referred to are seen by caller
• Yourlastparametermayinfactbemorethanoneparameter (varargs), and treated as an array
Introduction to Software Systems 1110/1140/1510/6710 17
Revision R2
Collections & ADTs
• Collections:‘Containersforobjects’
– set: mathematical set, unordered, can add, remove, test for membership – list: ordered list of objects, can add, can remove, can traverse
– map: key, value pairs, keys used to add and retrieve values
• ImplementedusingthefollowingfundamentalADTs(abstractdata types):
– Linked lists – Hashmaps
Introduction to Software Systems 1110/1140/1510/6710 19
Collections
Collections
Introduction to Software Systems 1110/1140/1510/6710
Collections J13
The Collection Framework
• Interfaces
– Implementation-agnostic interfaces for collections
• Implementations
– Concrete implementations
• Algorithms
– Searching, sorting, etc
Using the framework saves writing your own: better performance, fewer bugs, less work, etc.
Introduction to Software Systems 1110/1140/1510/6710 21
Collections J13
Concrete Collection Types
Implemented Using
Interfaces
Hash table
Resizable array
Linked list
Hash table + linked list
LinkedHash Set
LinkedList
LinkedList
LinkedHash Map
Based on table from http://docs.oracle.com/javase/tutorial/collections/implementations/index.html
Introduction to Software Systems 1110/1140/1510/6710 22
Abstract Data Types: Lists 1
The List ADT
A List interface and its implementation: Part 1
Introduction to Software Systems 1110/1140/1510/6710
Abstract Data Types: Lists A1
Abstract Data Types (ADTs)
Abstract data types describe containers for storing data elements. An ADT is abstract, not concrete.
A container is a very general ADT, serving as a holder of objects. A list is an example of a specific container ADT.
An ADT can be described in terms of the semantics of the operations that may be performed over it.
Introduction to Software Systems 1110/1140/1510/6710 24
Abstract Data Types: Lists A1
The List ADT
The list ADT is a container known mathematically as a finite sequence of elements. A list has these fundamental properties:
• duplicatesareallowed • orderispreserved
A list may support operations such as these: • create:constructanemptylist
• add:addanelementtothelist
• isempty:testwhetherthelistisempty
Introduction to Software Systems 1110/1140/1510/6710 25
• Hashfunctions
• Hashingapplications • Java’shashcode()
Introduction to Software Systems 1110/1140/1510/6710 27
Hash Functions
Hash functions
Choosing a good hash function
Introduction to Software Systems 1110/1140/1510/6710
Hash Functions C2
Hash Functions
A hash function is a function f(k) that maps a key, k, to a value, f(k), within a prescribed range.
A hash is deterministic. (For a given key, k, f(k) will always be the same).
Introduction to Software Systems 1110/1140/1510/6710 29
Hash Functions C2
Choosing a Good Hash Function
A good hash for a given population, P, of keys, k∈
P, will distribute f(k) evenly within the prescribed range for the hash.
A perfect hash will give a unique f(k) for each k∈P
Introduction to Software Systems 1110/1140/1510/6710 30
Hashing Applications
Java hashCode() Hashing Applications
Introduction to Software Systems 1110/1140/1510/6710
Hashing Applications C3
Java hashCode()
Java provides a hash code for every object
• 32-bitsignedinteger
• InheritedfromObject,butmaybeoverwritten
• Objectsforwhichequals()istruemustalsohavethesame hashCode().
• Thehashneednotbeperfect(i.e.twodifferentobjectsmayshare the same hash).
Introduction to Software Systems 1110/1140/1510/6710 32
Hashing Applications C3
Uses of Hashing
• Hashtable(amapfromkeytovalue)
• Pruningasearch
– Looking for duplicates
– Looking for similar values
• Compression
– A hash is typically much more compact that the key
• Correctness
– Checksums can confirm inequality
Introduction to Software Systems 1110/1140/1510/6710 33
Hashing Applications C3
Practical Examples…
Luhn Algorithm
Used to check for transcription errors in credit cards (last digit checksum).
Hamming Codes
Error correcting codes (as used in EEC memory)
Introduction to Software Systems 1110/1140/1510/6710 34
Hashing Applications C3
Practical Examples…
rsync (Tridgell)
Synchronize files by (almost) only moving the parts that are different.
MD5 (Rivest)
Used to encode passwords for a long time (but no longer).
Introduction to Software Systems 1110/1140/1510/6710 35
Revision R2
Computational Complexity
• Howwilltheexecutiontimeofaproblemchangeasthesizeofthe problem changes?
– Need to define ‘size of problem’
– Need to understand how problem time changes as that variable changes
Introduction to Software Systems 1110/1140/1510/6710 37
Computational Complexity
Time and Space Complexity Big O Notation
Practical Study: Sets
Introduction to Software Systems 1110/1140/1510/6710
Computational Complexity C5
Key computational resources: • Time
Computational complexity is the study of how problem size affects resource consumption for a given implementation.
• Worstcase
• Averagecase
Introduction to Software Systems 1110/1140/1510/6710 39
Computational Complexity C5
Broad Approach
1. IdentifyN,thenumberthatcharacterizestheproblemsize. – Number of pixels on screen
– Number of elements to be sorted
2. Studythealgorithmtodeterminehowresourceconsumption changes as a function of N.
Introduction to Software Systems 1110/1140/1510/6710 40
Computational Complexity C5
Concrete Examples
public int mindist(ArrayList
int min = Integer.MAX_VALUE;
for (int i = 0; i < values.size(); i++) {
for (int j = i + 1; j < values.size(); j++) { (N – 1)N/2
int diff = values.get(i)-values.get(j); if (Math.abs(diff) < min) (N – 1)N/2
min = Math.abs(diff); (N – 1)N/2 }
(N – 1)N/2
S(N) = 1 + N + 4 ((N – 1)N/2) = 1 + N + 2N2 – 2N = 2N2 – N + 1 ∈ O(N2)
Note: N -1 + N – 2 + ... 2 + 1 = (N – 1)N/2
Introduction to Software Systems 1110/1140/1510/6710 41
Revision R2
Formal Grammars (EBNF)
• Notaboutsemantics,justaboutrulesthatdefinerelationship among symbols
Introduction to Software Systems 1110/1140/1510/6710 43
Formal Grammars
Grammars EBNF
Introduction to Software Systems 1110/1140/1510/6710
Grammars C6
Formal Grammars
Formal languages are distinguished from natural languages by their artificial construction (rather than natural emergence).
Noam Chomsky is often credited with opening the field of formal grammars while studying natural languages.
(Creative Commons)
Noam Chomsky
Introduction to Software Systems 1110/1140/1510/6710 45
Grammars C6
Extended Backus-Naur Form
EBNF is a standard way of representing the syntax of a formal language (but not the semantics!)
• Terminalsymbols
– e.g. characters or strings
• Productionrules
– combinations of terminal symbols
to Software Systems 1110/1140/1510/6710 46
Grammars C6
Extended Backus-Naur Form
Very basic syntax of EBNF production rules:
• ‘=’ defines a production rule
• ‘|’ identifies alternates (e.g. ‘1’ | ‘2’ | ‘3’ )
• ‘{’, ‘}’ identify expressions that may occur zero or more times (e.g. ‘1’, { ‘0’ } )
• ‘[’, ‘]’ identify expressions that may occur zero or one time (e.g. ‘1’, [ ‘0’ ])
• ‘,’ identifies concatenation
• ‘-’ identifies exceptions
• ‘(’, ‘)’ identify groups
• ‘;’ terminates a production rule
Introduction to Software Systems 1110/1140/1510/6710 47
Grammars C6
(* a simple program syntax in EBNF − Wikipedia *)
program = 'PROGRAM', white space, identifier, white space,
'BEGIN', white space,
{ assignment, ";", white space }, 'END.' ;
identifier = alphabetic character, { alphabetic character | digit } ; number=["-"],digit,{digit};
string = '"' , { all characters − '"' }, '"' ;
assignment = identifier , ":=" , ( number | identifier | string ) ; alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G"
| "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; white space = ? white space characters ? ;
all characters = ? all visible characters ? ;
Introduction to Software Systems 1110/1140/1510/6710 48
Grammars C6
‘0’ | ‘1’ | ’00’ | ‘11’ | ‘000’ | ‘101’ | ‘111’ | ’010’ pal = ‘0’ | ‘1’ | (‘0’ , [pal], ‘0’) | (‘1’, [pal], ‘1’);
Introduction to Software Systems 1110/1140/1510/6710 49
Revision R2
• NeedtounderstandbasicJavacollections – How do you add, get and remove elements
• Needtounderstandrecursion – Stopping conditions
– Tracing execution
Introduction to Software Systems 1110/1140/1510/6710 51
Revision R2
• Onlyanswerquestionsyou’reconfidentabout
• Canget10/10marksbyonlyanswering10/15questions – Don’t stress if there are some you don’t know
• Ensureyoumarkyouranswerclearly
Introduction to Software Systems 1110/1140/1510/6710 52
Revision R2
• Readallpartsofthequestionverycarefully
• Ensureyouincludeallrelevantcode
• MaywanttorevisitdesignafterotherpartsofQuestion
• 3i)AboutclearlyexplainingagoodOOdesign – Does your design make good use of OO?
– Does it make sense to use inheritance?
– Does it make sense to use interfaces?
– What relationship should there be among classes? – Should you use collection types?
Introduction to Software Systems 1110/1140/1510/6710 53
Revision R2
• 3ii)Knowhowtodeclareaclassanditsfields
• 3iii),iv),&vi)ensureyouwriteallrelevantcode • 3v)knowhowtowriteaunittest
Introduction to Software Systems 1110/1140/1510/6710 54
Revision R2
• Veryclosetoexampleinlecture
• Ensureyouincludeallrelevantcode
• Don’timplementadd(Vvalue)as{secretadd(value);} • Noticedifferenceswithlecturecode
• Answerthisquestionyourselfandthencomparetolecturecode
Introduction to Software Systems 1110/1140/1510/6710 55
Revision R2
• i) Be clear and specific. Need to understand what a race is (J16)
• ii)Needtounderstandsets,linkedlistsandcomplexity
• iii) Not too hard, only four digits, each can be `1’ or `0’. Try to do it. • Iv)Harder;;seerevisionlecture
Introduction to Software Systems 1110/1140/1510/6710 56
Revision R2
• Providefiveclearlyidentifiedmajorpoints • Writeinsimple,plainclearEnglish
• Clarityisessential
• Lessismore
Introduction to Software Systems 1110/1140/1510/6710 57
Revision R2
Exam, Overall
• Budgetyourtime
• Stateyourassumptions
• Trytocommunicateyourunderstandingclearly
Introduction to Software Systems 1110/1140/1510/6710 58
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com