Recursive Algorithms
Structured Programming 1110/1140/6710
Copyright By PowCoder代写 加微信 powcoder
Recursion C1
Recursive Data Structure
A recursive data structure is comprised of components that reference other components of the same type.
linked list
Structured Programming 1110/1140/6710
Recursion C1
Recursive Algorithms
A recursive algorithm references itself.
A recursive algorithm is comprised of:
• one or more base cases
• a remainder that reduces to the base case/s
Structured Programming 1110/1140/6710
Recursion C1
Example: Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377…
fib(0) = 1 (base case)
fib(1) = 1 (base case)
fib(n) = fib(n-1) + fib(n-2) (for n ≥ 2)
Structured Programming 1110/1140/6710
Recursion C1
Example: Mergesort (von Neumann, 1945)
Sort a list
• List of size 1 (base case) – Already sorted
• List of size > 1
– Split into two sub lists
– Sort each sub list (recursion)
– Merge the two sorted sub lists into one sorted list (by iteratively picking the lower of the two least elements)
Animation: Visualizing Algorithms, , bost.ocks.org/mike/algorithms
Structured Programming 1110/1140/6710
Hash Functions
Hash functions
Choosing a good hash function
Structured Programming 1110/1140/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/6710
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/6710
Hashing Applications
Java hashCode() Uses of Hashing
Structured Programming
Hashing Applications C3
Java hashCode()
Java provides a hash code for every object
• 32-bit signed integer
• Inherited from Object, but may be overridden
• Objectsforwhichequals()istruemustalsohavethesame hashCode().
• The hash need not be perfect (i.e. two different objects may share the same hash).
Structured Programming 17
Hashing Applications C3
Uses of Hashing
• Hash table (a map from key to value)
• Pruning a search
– Looking for duplicates
– Looking for similar values
• Compression
– A hash is typically much more compact that the key
• Correctness
– Checksums can confirm inequality
Structured Programming 18
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)
Structured Programming 19
Hashing Applications C3
Practical Examples…
rsync (Tridgell)
Synchronize files by (almost) only moving the parts that are different.
MD5 (Rivest)
Previously used to encode passwords (but no longer).
Structured Programming 20
Java File IO Streams
Standard IO Random access files Buffering
Structured Programming 1110/1140/6710
File IO as Streams
A stream is a standard abstraction used for files: A sequence of values are read.
A sequence of values are written.
The stream reflects the sequential nature of file IO and the physical characteristics of the media on which files traditionally reside (e.g. tape or a spinning disk).
Structured Programming 1110/1140/6710 6
Structured Programming 1110/1140/6710 7
Structured Programming 1110/1140/6710 8
Java I/O: Byte Streams
The classes InputStream and OutputStream allow you to read and write streams of bytes to and from streams including files (subclasses: FileInputStream and FileOutputStream).
• Open the stream
• Read or write from the stream (in bytes)
• Wrap operations in a try clause
• Use finally to close the streams
ints are used, even though bytes are transferred(!)
Structured Programming 1110/1140/6710 9
Java I/O: Character Streams
When reading and writing characters, you should use the classes Reader and Writer, which allow you to read and write streams of characters to and from streams including files (subclasses: FileReader and FileWriter).
ints are used, even though chars are transferred.
Structured Programming 1110/1140/6710 10
File I/O: Buffering
Reading data one byte at a time is costly. Buffering is used to absorb some of that overhead.
Disk: ~10ms SSD: ~100μs RAM: ~10ns Register: ~1ns
In Java the BufferedReader and BufferedWriter classes can be used to buffer data read or written with FileReader and FileWriter.
To be sure that a buffer is flushed, call flush(), or close the file.
Structured Programming 1110/1140/6710 11
Java Command Line IO
Three standard IO streams (globally-defined objects): • StandardinputSystem.in
• StandardoutputSystem.out
• StandarderrorSystem.err
byte b = (byte) System.in.read(); System.out.write(b); System.out.flush(); System.err.write(b);
Structured Programming 1110/1140/6710 12
“New” I/O (java.nio.file)
Java NIO offers simpler, event-driven interface
• Path — replaces java.io.File
• FileSystem — factory class for objects in the filesystem
• WatchService — utility class to detect file system changes through event notification
• Files —create, rename, copy, modify attributes and delete files
Structured Programming 1110/1140/6710 13
Computational Complexity
Time and Space Complexity Big O Notation
Practical Study: Sets
Structured Programming 1110/1140/6710
Computational Complexity C5
Key computational resources: • Time
Computational complexity is the study of how problem size affects resource consumption for a given implementation.
• Worst case
– the complexity of solving the problem for the worst input of size n
• Average case
– is the complexity of solving the problem on an average.
Structured Programming 1110/1140/6710 23
Computational Complexity C5
(Computational) Scaling
1. Identify n, the number that characterizes the problem size. – Number of pixels on screen
– Number of elements to be sorted
2. Study the algorithm to determine how resource consumption changes as a function of n.
Structured Programming 1110/1140/6710 24
Computational Complexity C5
Big O Notation
Suppose we have a problem of size n that takes g(n) time to execute in the average case.
g(n) ∈ O(f(n))
if and only if there exists a constant c > 0 and a constant n0 > 0 such that for all n > n0 :
g(n) ≤ c × f(n)
Structured Programming 1110/1140/6710 25
Computational Complexity C5
Simple Examples
• Constant O(1)
– Time to perform an addition
• Logarithmic O(log(n))
– Time to find an element in a (balanced) BST
• Linear O(n)
– Time to find an element within a list
• O(n log(n))
– Average time to sort using mergesort
• Quadratic O(n2)
– Time to compare n elements with each other
Structured Programming 1110/1140/6710 26
Computational Complexity C5
Time Complexity: Counting Statements
Time complexity can estimated by simply counting the number of statements to be executed.
– Simple statements are constant time
– Library calls may have arbitrary complexity
Structured Programming 1110/1140/6710 27
Computational Complexity C5
Concrete Examples
Consider hashing into a table of n elements…
public int hash(Integer key, int buckets) { return key % buckets;
Constant time, O(1)
Structured Programming 1110/1140/6710 28
Computational Complexity C5
Concrete Examples
Consider summing a list of size n…
public int sum(ArrayList
for(Integer i: list) {
rtn += i; return rtn;
Linear time, O(n)
Structured Programming 1110/1140/6710 29
Computational Complexity C5
Concrete Examples
public int minDiff(ArrayList
int diff = values.get(i)-values.get(j); if (Math.abs(diff) < min)
min = Math.abs(diff);
for (int i = 0; i < values.size(); i++) {
for (int j = i + 1; j < values.size(); j++) {
(n – 1)n/2 (n – 1)n/2 (n – 1)n/2 (n – 1)n/2
222 S(N) = 1 + n + 4 ((n – 1) n/2) = 1 + n + 2 n – 2n = 2n – n + 1 ∈ O(n )
Note: n -1 + n – 2 + ... 2 + 1 = (n – 1) n /2
Structured Programming 1110/1140/6710 30
Formal Grammars
Grammars EBNF
Structured Programming 1110/1140/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
Structured Programming 1110/1140/1510/6710 15
Grammars C6
Generative Grammars
Sentence = Noun Phrase, Verb Phrase, [Noun Phrase]; Noun = signs, directions, lives
Article = the
Verb = show, matter, look
Adjective = big, small, white, black
Noun Phrase = [Article], [Adjective], Noun | Noun Phrase; Verb Phrase = Verb, [Noun Phrase];
The signs show the directions.
Small big directions matter the black white signs.
Noun Phrase
Verb Phrase
Noun Phrase
the signs show
the directions
Structured Programming 1110/1140/1510/6710 16
Grammars C6
Generative Grammars
Sentence = Noun Phrase, Verb Phrase, [Noun Phrase]; Noun = signs, directions, lives
Article = the
Verb = show, matter, look
Adjective = big, small, white, black
Noun Phrase = [Article], [Adjective], Noun | Noun Phrase; Verb Phrase = Verb, [Noun Phrase];
The signs show the directions.
Small big directions matter the black white signs.
Syntactically correct productions (sentences) don’t always convey meaning! E.g. “I tested positively towards negative.”
Noun Phrase
Verb Phrase
Structured Programming 1110/1140/1510/6710 17
Grammars C6
Extended Backus-Naur Form
EBNF is a standard way of representing the syntax of a formal language (but not the semantics!)
• Terminal symbols
– e.g. characters or strings
• Production rules
– combinations of terminal symbols
Programming 1110/1140/1510/6710 18
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
Structured Programming 1110/1140/1510/6710 19
Grammars C6
Example EBNF grammar
PROGRAM DEMO1
H:=-100023;
D123:=B34A; BABOON:=GIRAFFE; TEXT:="Hello world!";
(* a simple program syntax in EBNF − Wikipedia *)
program = 'PROGRAM', white space, identifier, white space, 'BEGIN', white space,
{ assignment, ";", white space },
= alphabetic character, { alphabetic character | digit } ; "-" ], digit, { digit } ;
identifier
number = [
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 ? ;
Structured Programming 1110/1140/1510/6710 20
Grammars C6
Simple EBNF Grammars
Grammar for arrangement of characters that are:
• Natural numbers?
natural = ‘0’ | (nzdigit, { digit }) ;
nzdigit = ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’ ; digit = ‘0’ | nzdigit ;
• Integers?
integer = ‘0’ | ([‘-’], nzdigit, { digit }) ;
• Decimal numbers?
real = ([‘-’], natural, [(‘.’ { digit }, nzdigit)]) – ‘-0’ ;
• 24hr time, digital clock?
time = hour, ‘:’, min ;
hour = ( ( ‘0’ | ‘1’ ) , digit ) | ( ‘2’ , ( ‘0’ | ‘1’ | ‘2’ | ‘3’)) ; min = ( ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ ), digit ;
Structured Programming 1110/1140/1510/6710 21
Concurrency
Structured Programming 1110/1140/6710
Threads C7
Concurrency, Processes and Threads
• Concurrency
– Multiple activities (appear to) occur simultaneously, (e.g. recording this lecture and displaying this slide).
– ‘Time slicing’ allows a single execution unit to give the appearance of concurrent execution
– Distinct execution context that (by default) shares nothing (e.g. IntelliJ, PowerPoint, Quicktime recorder)
– Intra-process execution context (e.g. IntelliJ’s compiler)
Structured Programming 1110/1140/6710 7
Threads C7
Why Threads?
• ‘Concurrency’
– Separate concerns (e.g. rendering v logic)
– Good for: distinct tasks that naturally occur concurrently
• ‘Parallelism’(aspecialcaseofconcurrency)
– Break task into pieces, exploit parallel hardware
– Good for: computationally intensive problems that can be readily partitioned
Structured Programming 1110/1140/6710 8
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com