Transcript ppt - Courses

i206: Lecture 9:
Review; Intro to Algorithms
Marti Hearst
Spring 2012
1
QuickSort
• A Divide-and-Conquer recursive algorithm
• Divide:
– If only one item in list, return it.
– Else choose a pivot, and
– Divide the list into 3 subsets
• Items < pivot, pivot, items > pivot
• Recurse:
– Recursively solve the problem on the subsets
• Conquer:
– Merge the solutions for the subproblems
• Concatenate the three lists
2
QuickSort Visualizations
• Wikipedia:
– https://en.wikipedia.org/wiki/File:Sorting_quicksort_anim.gif
• Xoax:
– http://www.youtube.com/watch?v=y_G9BkAm6B8
• The Sorter:
– http://www.youtube.com/watch?v=2HjspVV0jK4
• Robot battle:
– http://www.youtube.com/watch?v=vxENKlcs2Tw
3
Partitioning in QuickSort
• Partition:
– Select a key (called the Pivot) from the dataset
– Divide the data into two groups such that:
• All the keys less than the pivot are in one group
• All the keys greater than the pivot are in the other
– Note: the two groups are NOT required to be sorted
• Thus the data is not sorted, but is “more sorted” than
before
• Not too much more work to get them sorted.
– What is the order of this operation?
• Linear (or O(n))
4
QuickSort
• An advantage: can be done “in place”
– Meaning you don’t need to allocate an additional array or
vector to hold the temporary results
• Do the in-place swapping in the divide step
– Choose pivot
– Have two indexes: L and R
– While L is < R
• Move L forwards until A[L] > pivot
• Move R backwards until A[R] < pivot
• Swap them
5
Quick Sort – Choosing the Pivot
• Alternative Strategies
– Choose it randomly
• Can show the expected running time is O(n log n)
– Sample from the set of items, choose the median
• Takes more time
• If sample is small, only a constant overhead
6
Quick Sort
• Running Time analysis
– If the pivot is always the median value
•
•
•
•
Each list is divided neatly in half
The height of the sorting tree is O(log n)
Each level takes O(n) for the divide step
O(n log n)
– If the list is in increasing order and the pivot is the last
value
• Each list ends up with one element on the right and all the
other elements on the left
• The height of the sorting tree is O(n)
• Each level takes O(n) for the divide step
• O(n^2)
– However, in practice (and in the general case), QuickSort
is usually the fastest sorting algorithm.
7
QuickSort vs. MergeSort
• Similarities
– Divide array into two roughly equal-sized groups
– Sorts the two groups by recursive calls
– Combines the results into a sorted array
• The difficult step
– Merge sort: the merging
– Quick sort: the dividing
• Running Time
– QuickSort has a bad worst case running time
– But in practice it is faster than the others
• Constants, and the way data is distributed
– Also, MergeSort requires an additional array
8
The Paint Machine
Things to learn from this assignment
– Multiple representations for the same thing
• Truth tables & circuits
• Boolean logic & controlling machines
• Opcode & operand is like a method & its arguments
– How to use binary numbers to make codes
• Important in security and networking
– Designing for modularity
– Applying the principled of abstraction & simplicity
9
The Paint Machine
• E controls the forwards-backwards movement
–
When E=1, it moves the paper forwards or backwards one pixel
• F controls the left-right movement of the paper.
–
When F=1, it moves the paper one pixel left or right.
• G indicates the direction for the roller.
–
–
If G=1 and E=1, go forwards. If G=0 and E=1, go backwards.
If G=1 and F=1, go left. If G = 0 and F = 1, go right.
10
Strategy for Designing the
Instruction Set
• Use the principle of abstraction to break the
problem into subproblems
– The machine does four operations
– Each operation has different kinds of arguments
– Make the instructions reflect this
• Divide into opcodes and operands
• Opcodes are the commands saying what to do
• Operands are the arguments saying how to do it
• Use the principle of simplicity to design the
operand
– Make the bits of the operand mirror the functions of
the machine
11
Designing the
Circuit
Use the principle of abstraction
Use the 2-bit decoder to convert
the opcode into a control for the
machine
Use the principle of simplicity
Make the operands mirror the
structure of the machine’s
controls
A B C D E F G
mix red
11 100
1 0 0 0 0 0 0
mix yellow
11 010
0 1 0 0 0 0 0
mix blue
11 001
0 0 1 0 0 0 0
mix green
11 011
0 1 1 0 0 0 0
mix purple
11 101
1 0 1 0 0 0 0
mix orange
11 110
1 1 0 0 0 0 0
mix black
11 111
1 1 1 0 0 0 0
mix white
11 000
0 0 0 0 0 0 0
A B C D E F G
move left
10 011
0 0 0 0 0 1 1
move right
10 010
0 0 0 0 0 1 0
move forw
10 101
0 0 0 0 1 0 1
move back
10 100
0 0 0 0 1 0 0
paint
01 000
0 0 0 1 0 0 0
halt
00 000
0 0 0 0 0 0 0
12
The Circuit – My Intended Solution
Mix
A
Instr 2 (x)
Instr 3 (y)
Instr 0 (v)
C
2-bit
decoder
Instr 1 (w)
B
Move
Halt
Paint
Instr 4 (z)
E
Instr 2 (x)
F
Instr 3 (y)
Instr 4 (z)
G
D
Assumes that the compiler cannot produce an illegal instruction.
For example, 10111 is not legal but if produced would jam the machine.
13
Other Paint Machine Solutions
Luis Villafana
A B C D E F G
mix red
00 001
1 0 0 0 0 0 0
mix yellow
00 010
0 1 0 0 0 0 0
mix blue
00 100
0 0 1 0 0 0 0
mix green
00 110
0 1 1 0 0 0 0
mix purple
00 101
1 0 1 0 0 0 0
mix orange
00 011
1 1 0 0 0 0 0
mix black
00 111
1 1 1 0 0 0 0
mix white
00 000
0 0 0 0 0 0 0
move left
10 001
0 0 0 0 0 1 1
move right
10 010
0 0 0 0 0 1 0
move forw
10 110
0 0 0 0 1 0 1
move back
10 100
0 0 0 0 1 0 0
paint
01 000
0 0 0 1 0 0 0
halt
11 000
0 0 0 0 0 0 0
Stops illegal instructions from
having an effect via XORs.
14
Other Paint Machine Solutions
Stephanie Hornung
A B C D E F G
mix red
00 001
1 0 0 0 0 0 0
mix yellow
00 100
0 1 0 0 0 0 0
mix blue
00 010
0 0 1 0 0 0 0
mix green
00 110
0 1 1 0 0 0 0
mix purple
00 011
1 0 1 0 0 0 0
mix orange
00 101
1 1 0 0 0 0 0
mix black
00 111
1 1 1 0 0 0 0
mix white
00 000
0 0 0 0 0 0 0
move left
10 001
0 0 0 0 0 1 1
move right
10 011
0 0 0 0 0 1 0
move forw
10 101
0 0 0 0 1 0 1
move back
10 110
0 0 0 0 1 0 0
paint
01 000
0 0 0 1 0 0 0
halt
11 010
0 0 0 0 0 0 0
Stops illegal instructions from
having an effect.
15
Bonus Questions
• 1. Unnecessary instruction?
– Mix white
• 2. Bad program?
– Many possibilities, including forgetting a “paint”
• Mix orange
• Mix purple
• Paint
• 3. Make paper move >1 step at a time?
– Make direction part of op-code (needs 6 bits total)
• Left 3
• Forward 7
– Or use the extra bits not used by halt and paint
• Messy solution
• 4. Reduce instruction time by one clock cycle?
– Increment PC while the circuit is executing
– Or don’t disconnect circuit from machine
16
Exam Review
17
Boolean
• Be able to convert between Boolean
expressions and logic gates and truth tables
and Venn diagrams.
• Be able to use deMorgan’s laws to convert
Boolean expressions.
18
Binary
• Be able to
– Do the basics of binary arithmetic
– Convert among binary, decimal, and hexadecimal
• Understand the relationship between binary numbers
and truth tables.
• Understand the relationship between binary numbers
and powers of 2.
• Understand how information that isn’t numerical can
nonetheless be represented by binary numbers.
19
Machine Instruction Sets and
Assembly Language
• Understand the relationship between computer
instructions and binary numbers.
• Understand the relationship between machine
instructions and assembly language instructions and be
able to convert between them. Understand the language
from lecture, also found here:
http://courses.cs.vt.edu/~csonline/MachineArchitecture/Lesson
• Understand the meaning of a sequence of computer
instructions and describe what that sequence of
instructions does.
20
CPU, Circuits and Memory
• Understand the roles and behavior of the
major circuits that comprise the CPU,
including:
– Registers
– ALU
– RAM
• Understand the difference between
loading/storing a numerical value vs. a
memory reference (address) of a numerical
value.
• Understand the basic functioning of a CPU.
21
Math
• Be able express sums (and differences) of
sequences of numbers in sigma notation and
with python code.
• Understand the graphed shapes of and relative
size differences between different kinds of
functions
– E.g., linear, polynomial, exponential, log
22
Analysis of Algorithms
• Be able to analyze pseudocode or python code
to determine the number of steps required to
execute that code in the general case (for any
value of n)
• Be able to analyze algorithms in terms of their
big-O running time.
23
Sorting Algorithms
• Understand the basics of how the main ones
work.
• Know the running times of the main ones.
24
Distributed
Systems
Data
Structures
Security
Cryptography
Network
Standards
& Protocols
Inter-process
Communication
I/O
Operating
System
Methodologies/
Tools
Process
Application
Program
Memory
hierarchy
Memory
Register, Cache
Main Memory,
Secondary Storage
ALUs, Registers,
Compiler/
Program Counter,
Instruction Register Interpreter
Op-code, operands
Instruction set arch
Circuits
Lossless v. lossy
Info entropy &
Huffman code
Numbers, text,
audio, video,
image, …
Machine
Instructions
CPU
Data
storage
Data
compression
Assembly
Instructions
Decimal,
Hexadecimal,
Binary
Data
Data
Representation
Gates
Adders, decoders,
Memory latches,
ALUs, etc.
Boolean
Logic
AND, OR, NOT,
XOR, NAND, NOR,
etc.
Number
Systems
Binary
Numbers
Bits & Bytes
Design
Algorithms
Principles
Formal models
Analysis
Big-O
Data Structures
Searching, sorting,
Encryption, etc.
Stacks, queues,
maps, trees,
graphs, …
Truth table
Venn Diagram
DeMorgan’s Law
25
Outline
• What is a data structure
• Basic building blocks: arrays and linked
lists
• Data structures (uses, methods,
performance):
–
–
–
–
List, stack, queue
Dictionary
Tree
Graph
26
What is a Data Structure?
• A conceptual arrangement of data.
(Brookshear)
• A systematic way of organizing and accessing
data. (Goodrich & Tamassia)
• A way of storing data in a computer so that it
can be used efficiently. Often a carefully
chosen data structure will allow a more
efficient algorithm to be used. (Wikipedia)
• Common data structures: array, list, stack,
queue, dictionary, set, tree, graph, …
27
List
• An ordered collection of objects
• Example:
fib = [1,1,2,3,5,8,13]
Brookshear Figure 8.1
28
Set
• An unordered collection of non-repeated
objects
• Example:
>>> basket = ['apple', 'orange', 'apple',
'pear', 'orange', 'banana']
>>> fruit = set(basket) # create a set without duplicates
>>> fruit
set(['orange', 'pear', 'apple', 'banana'])
>>> 'orange' in fruit
# membership testing
True
29
Dictionary
• Also known as associative array, lookup table,
or map
• A searchable collection of key-value pairs
– each key is associated with one value
• Example:
>>> fullname = {‘chuang’:’John Chuang’,
‘i206’:’206 class mailing list’}
>>> fullname[‘chuang’]
‘John Chuang’
30
Tree
• A collection of data whose entries have a
hierarchical organization
Brookshear Figure 8.2
31
Question
• How are these data structures implemented?
– How are they stored in memory?
32
Basic Data Structures
• Array
Brookshear Figure 8.4
• Linked list
33
Linked List Operations
Brookshear Figure 8.9
• Insertion
• Deletion
34
Array vs. Linked List
• Q: what are the tradeoffs?
– Running time of insert, delete, lookup operations
– Storage requirements
• Example: implement a UCB student directory
35