MIE 335: Algorithms and Numerical Methods
Introduction to Algorithms
Department of Mechanical and Industrial Engineering University of Toronto
January 12, 2021
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 1
TODAY’S OUTLINE
I Aboutme
I AboutTAs
I Aboutthisclass
I Backgroundinalgorithms
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 2
ABOUT ME…
Prof. Merve Bodur
I Background
• B.S.inIEandB.A.inMath,
Bogazici University, Turkey, 2011
• M.S.inISyEandM.S.inCS, UW-Madison, 2014
• Ph.D.inISyE,UW-Madison,2015
• PostdocinGATech,Aug2015-Jan2017
I Researchexpertise:Optimization
• Researchareas:Integerprogramming,stochasticprogramming,
combinatorial optimization, multi-objective optimization
• Applicationsareas:Decisionmakingunderuncertainty, scheduling, power systems, healthcare, transportation, telecommunication
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 3
TEACHING ASSISTANTS
Lab: Berk Gorgulu
I Inprogress:Ph.D.inIE,UofT I M.S.inIE,BogaziciU(Turkey) I B.S.inIE,BogaziciU(Turkey)
Tutorial: Neda Tanoumand
I Inprogress:Ph.D.inIE,UofT
I M.S.inIEandM.S.inMath,SabanciU(Turkey)
I B.S.inPetroleumEng,minorinIE,AmirkabirUof Tech (Iran)
Project: Maryam Daryalal
I Inprogress:Ph.D.inIE,UofT
I M.S.inIE,AmirkabirUofTech(Iran),andM.S.in CS, Concordia U
I B.S.inIE,AmirkabirUofTech(Iran)
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 4
Course Details
COURSE LOGISTICS
I Pleasecheckthesyllabusforallthedetails
I CoursepagesonQuercus:
• AllmaterialwillbepostedontheLEC0101website
• Forlivesessions(i.e.,lectures,tutorialsandlabs)andavailable
recordings, you need to go to the Course Room of their respective pages (LEC0101,PRA0101,PRA0101,TUT0101,TUT0102)
I DiscussionboardonPiazza:
• Post/answerquestionsaboutthecourse(avoidemails)
I Livesessionparticipation:
• Optionalbutstronglysuggested • Askandanswerquestions
I Classroombehaviour:
• Followstandardclassroometiquette
• Virtuallyraiseyourhandtoask/answerquestions • Ifpossible,turnonyourcamerabeforespeaking
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 5
Course Details
CLASS OVERVIEW
I Pleasecheckthesyllabusforallthedetails I Norequiredtextbook
See syllabus for supplementary texts, e.g., Problem Solving with Algorithms and Data Structures using Python
(All MIE335 notes from 2016 are posted on the website) I Syllabusdatesaretentative
I Prof.Bodurofficehour(tobefixed):Th1-2pm(EST)
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 6
Course Details
COURSE STRUCTURE
I Lectures
• Newconcepts,problems,algorithms
• Purposeandcorrectnessofalgorithms • Algorithmcomplexityanalysis
• Illustrativeexamples
I Tutorials
• Topicoverview
• Examples,examples,examples I Labs
• ImplementationoflectureconceptsusingPython I Project
• Applicationofallkeycourseconcepts
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 7
Course Details
ATTENDANCE: OPTIONAL
Course mark Final exam Midterm
Lab project Lab HW
Whole class (N =87)
71.58 63.89 75.87 75.12 30.59
Good Bad attendance attendance (N =30) (N =57)
79.30 67.45 75.53 57.65 81.07 73.08 80.12 72.43 33.55 29.01
% improv.
17.57% 31.02% 10.93% 10.62% 15.64%
(MIE335, Winter 2015)
M. Bodur MIE 335_01
Algorithms and Numerical Methods: Introduction to Algorithms 8
Course Details
COURSE GOALS: ALGORITHMS (65%)
I I
I I
I I
Learntodesignalgorithmstosolveproblems
Understandthebasicprinciplesofalgorithmdesign,especiallyfor applications in industrial engineering
Understandbasictechniquesforanalyzingtheperformanceof algorithms
Developanappreciationfortheimportanceofimplementing algorithms efficiently and the skills necessary for doing so
Learntoperformcomplexityanalysisonalgorithms Learnhowtobalanceaccuracyandefficiencyinalgorithm
selection
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 9
Course Details
COURSE GOALS: NUMERICAL METHODS (35%)
I
Appreciatetheimportanceofnumericalmethodsthrough implementing core techniques such as solving
• linearsystemsofequations
• unconstrainedoptimizationproblems
tin alg
I I I
Learntheoreticalunderpinningsbehindmatrixdecomposition Learnhowtocalculatethecomplexityofmatrixdecomposition Learnhowtoselectappropriatematrixdecompositionmethods
? Gain experience programming in Python ?
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 10
M. Bodur
Course Details
WHY PYTHON?
I I I I
I I
I I
I
M. Bodur
Oneofthemostpopularprogramminglanguages General-purpose,extensivelyused Extensivesupportlibraries(e.g.,NumPy,Matplotlib)scipy Freeandopen-source
Interpretable:Morelikeareadable,humanlanguage Simpletolearn(syntax,newfeatures),fasttowriteprograms
Efficient:Candoalotinasinglelineofcode
Object-oriented JupyterNotebook
(N.B. You will need to submit .py scripts, executable with arguments)
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 11
lab isokay
google co must submit pyfile
but
Course Details
GRADING
I Pleasecheckthesyllabusforallthedetails I Coursephilosophy:Youlearnbydoing
Assessment Weight
Midterm 30% Final exam 37% Lab project 25% Lab homeworks* 8%
Take-home
Take-home
Term-wide with Checkpoints Weekly, lowest dropped
* Lab homeworks are due on Saturday morning, but should be mostly
complete-able during your lab section on Thursdays.
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 12
Course Details
COURSE PROJECT:
DECISION DIAGRAMS FOR SET COVERING
I Teams of four (mostly) or three (can use the Teammate Search on Piazza)
I Solvesetcoveringproblemusingbinarydecisiondiagrams
• Generate(random)instances
• Implementmultiplealgorithms
• Develop/testalgorithmicenhancementideas
• Comparecomputationalefficiencyofdifferentapproaches • Analyzetheoreticalcomplexity
I Deliverables:PDFreport(viaLaTeX),Pythonsourcecode
I TherewillbeCheckpoints(willbeprovidedinthedescriptionfile)
Start early! Ask questions!
I Thisisaproject,notanassignment)nostandardexpectations
Anything you try, any observation/analysis you make is valuable
Gurobi
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 13
Course Details
ACADEMIC CODE REMINDER
All homeworks (projects) are individual (team) assignments. The following are academic offenses: %vfill
I Copyinganysegmentofcodefromanysource
I Submittingcodethatyou(yourteam)didnotthinkofpersonally I Sharingyourcodewithsomeoneelse
I Makingiteasyforsomeonetostealyourcode
? On a different note, keep in mind: Any source code you submit should
I runwithoutanyerrors“outofthebox”!o.w.,getszero! I runcorrectly
I bewell-commented
Please check the syllabus for further details
(Lab1 will have an auto-grading example)
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 14
Course Details
APPROXIMATE SYLLABUS (SUBJECT TO CHANGE WITHOUT NOTICE)
Week Topic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Course overview, exponential/polynomial-time algorithms Decision algorithms: Greedy methods
Decision algorithms: NP-hard problems
Sorting
Big-O, Algebraic operations
READING WEEK
Modular arithmetic, Hashing
Intro to RSA encryption
RSA computational issues
Cramer’s rule, Gaussian elimination Forward/backward substitution
Cholesky and LU factorizations Unconstrained optimization: Steepest descent Unconstrained optimization: Newton’s method
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 15
Course Details
QUESTIONS ABOUT THE COURSE?
? Feedback: If you have constructive comments on the way the class is going, please tell me!
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 16
Algorithms
A BRIEF HISTORY OF ALGORITHMS
I
I
I
I
AccordingtotheOxfordEnglishDictionary,thewordalgorithmisa combination of the Middle English word algorism with arithmetic
ThiswordprobablydidnotentercommonusageintheEnglish language until sometime last century
ThewordalgorismderivesfromthenameofanArabic mathematician circa A.D. 825, whose surname was Al-Khwarizmi
Al-Khwarizmiwroteabookonsolvingequationsfromwhosetitle the word algebra derives
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 17
Algorithms
A BRIEF HISTORY OF COUNTING
I Inordertounderstandalgorithms,wehavetounderstand counting and basic arithmetic
I Simpleenough:972⇥345=335,340
I HowaboutCMLXXII⇥CCCXLV=|III|XXXVCCCXL? I ThedecimalsystemisinventedinIndiaaroundA.D.600
Using only 10 symbols, even very large numbers can be written down compactly, and arithmetic can be done efficiently on them by follow- ing elementary steps
I Al-Khwarizmilaidoutthebasicmethodsforadding,multiplying, and dividing numbers, even extracting square roots and calculating digits of ⇡
I Theseprocedureswereprecise,unambiguous,mechanical, efficient, correct ! they were algorithms
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 18
Algorithms
m lo
god 6.4 godc2,4 godc2 2
4
n
godCo4 2
THE FIRST ALGORITHM
I ItiscommonlybelievedthatthefirstalgorithmwasEuclid’s Algorithm (c. 300 BC) for finding the greatest common divisor
(gcd) of two integers, m and n, (m n)
TEALBEP’s 4 I Basedontheprinciplethatthegcdoftwonumbersdoesnot
change if the larger number is replaced by its difference with the smaller number
Euclid’s Algorithm(m, n)
I Dividembynandletrbetheremainder I Ifr=0,thengcd(m,n)=n
I Otherwise,gcd(m,n)=gcd(n,r)
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 19
Algorithms
SHOW ME THE ALGORITHMS
I Algorithmsareliterallyeverywhereyoulook
I Somecommonapplicationsofalgorithms: • Sortingnumbers
• Searchingformatchingstrings(DNA–HumanGenome) • Solvingequations(NumericalLinearAlgebra)
• Internetsecurity–PublicKeyCryptography
• ShortestPaths–GoogleMaps
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 20
Algorithms
WHAT IS AN ALGORITHM?
output
I I
I I
input I Mathematicalabstractionofcomputerprogram
Takesasetofvaluesasinput Produces a set of values as output
Asequenceofcomputationalstepsthattransformtheinputinto the output
Atoolforsolvingawell-specifiedcomputationalproblem
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 21
Algorithms
WHAT IS A PROBLEM?
I Roughly,aproblemspecifieswhatsetofoutputsisdesiredfor each given set of inputs
I Aprobleminstanceisjustaspecificsetofinputs
Example: The Sorting Problem
I Input:Asequenceofnumbersa1,a2,…,an
I Output: A reordering a01,a02,…,a0n such that a01 a02 ··· a0n.
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 22
Algorithms
WHAT DO YOU MEAN BY “SOLVE”?
I
I
I I
I I
input instance output solution
Solvingaprobleminstanceconsistsofspecifyingaprocedurefor converting the inputs to an output of the desired form (called a solution)
Analgorithmthatisguaranteedtoresultinasolutionforevery instance is said to be correct
Acorrectalgorithmsolvesthegivencomputationalproblem Anincorrectalgorithmmightnotstopatallonsomeinput
instances, or it might stop with an incorrect answer Inthisclass,westudy(formally)howtoprovethatanalgorithmis
correct
Wealsostudyhowtoformallycharacterize(analytically)the amount of effort required to produce a solution
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 23
Algorithms
EFFICIENCY
I I
I I
Differentalgorithmsdevisedtosolvethesameproblemoftendiffer dramatically in their efficiency Considerexecutingthemusingthesamehardwareandsoftware, i.e., machine-independent Wewanttomeasurethecomputationaleffort
comparison
couldbe 1 x 46,42
“Running time”: The number of primitive operations
or “steps” eg Sorting with operation compare 4
executed
⇧ What operations the algorithm uses
⇧ The running time of each operation
⇧ Running time of the algorithm = sum of running times
Ingeneral,runningtimegrowswiththe“sizeoftheinput”
) describe the running time as a function of the size of its input (e.g., as a function of the number of items in the input) Worst-caserunningtime:Thelongestrunningtimeforany input of a given size
6 I 2,3
and swap
I I
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms
24
Algorithms
ASIDE: PSEUDO-CODE
I I I I
I
Wewillusuallyusepseudo-codetospecifyalgorithms
ThesyntaxissimilartoPython,butwithdeparturesforclarity
WewillusedescriptionsinEnglishtospecifycertainoperations
Thepseudo-codeusedinlecturemaydifferfromthatinthebook (I may use more Python-like syntax)
Booksmayusedifferentpseudo-codeconventions
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 25
Algorithms
A SIMPLE EXAMPLE
How do we calculate xn for given x, n 2 N?
I Thefirstthingthatcomestomind:Multiply1byxexactlyntimes def pow1(x,n):
result = 1
for i in range(n):
result *= x
return result
2 2 2 2XZ
I Afterthinkingalittlebit:Repeatsquaring recursive def pow2(x,n):
22
2
22
return x * pow2(x,int(n/2)) * pow2(x,int(n/2))
if (n == 0): return 1
elif (int(n % 2) == 0):
return pow2(x,int(n/2)) * pow2(x,int(n/2))
else:
I After thinking a bit more: Store work def pow3(x,n):
if (n == 0): return 1
temp = pow3(x,int(n/2))
if (n % 2 == 0):
return temp * temp
else:
return x * temp * temp
that don’t needto so we
cn twice calculate same pond
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 26
Algorithms
ANOTHER EXAMPLE: FIBONACCI NUMBERS
I I
I
Anothersimpleexampleoftheimportanceofefficientalgorithms arises in the calculation of Fibonacci numbers Fibonaccinumbersariseinpopulationgenetics,aswellasahost of other applications. (Including the analysis of Euclid’s Algorithm!)
0,1,1,2,3,5,8,13,21,34,55,…
The nth Fibonacci number is defined recursively as follows:
F0 = 0,
F1 = 1,
Fn=Fn 1+Fn 2, 8n2N,n>2.
I
I
M. Bodur
ThesequenceofratiosofadjacentFibonaccinumbersconvergestothe
Golden Ratio, ‘, that is,lim (F /F ) = ‘ ⇡ 1.618 takeany n
ifyou n!1 n+1 n goldenratio
1.618
How do we calculate Fn for a given n 2 N?
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 27
Algorithms
CALCULATING FIBONACCI NUMBERS
Obvious Solution: A recursive function fib1() def fib1(n):
if n < 0:
return error
elif n == 0 or n == 1:
return n
return (fib1(n-1) + fib1(n-2))
M. Bodur
MIE 335_01
Algorithms and Numerical Methods: Introduction to Algorithms 28
Algorithms
BASIC QUESTIONS
Q
1. 2.
You must ask designing algorithm Is fib1() correct?
• Yes,bydefinitionofFn
How efficient is the recursive form of fib1()? How much time does it take, as a function of n?
• Wewillanswerthis(analytically)
• Youwillansweritempiricallyinlab
Can we do better?
Is there a more efficient algorithm?
• Yes!
• Youwillworkonitinthelab
3.
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 29
for
Classification of algorithms
EFFICIENCY OF fib1() I Let On be
in the algorithm (+, ,⇥,÷)
the number of operations (steps)
I Weconsider tibi n
elementary arithmetic operations
n
0 1 2 3 4 .
13
.
200
Action
return 0
return 1 fib1(0) + fib1(1) fib1(1) + fib1(2) fib1(2) + fib1(3)
fib1(11) + fib1(12) fib1(198) + fib1(199)
On
0
0
1 + 0 + 0 = 1 1 + 0 + 1 = 2 1 + 1 + 2 = 4
1 + 143 + 232 = 376 4.5 · 1041
On+1 /On -
1 2.000 2.000 1.750
1.619 1.618
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms
30
Classification of algorithms
EFFICIENCY OF fib1()
Number of operations required for fib1(n)
41 x 10
4 3 2 1
700 5 600
500
400
300 200 100
00
0 5 10 15 0 50 100 150 200
nn
(a) Small values of n (b) Large values of n I Buthowlongwillittake?
I Suppose that we can perform 1015 floating-point operations (flops) in a second (using a supercomputer) ) 1.44 · 1019 years to compute F200!!!
Having an algorithm does not mean we have solved the problem!
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 31
O (# operations) n
O (# operations) n
Classification of algorithms
CURSE OF EXPONENTIAL TIME
I On numbers are generated almost identically to the Fibonacci numbers:
On =1+On 1 +On 2
I Thus,theratioofconsecutiveoperationsalsoapproachestothe
Golden Ratio, which implies
On 1.618n 2
I Therefore,therecursiveFibonaccicalculationfib1requiresan
exponential number of calculations as a function of its input (n). Exponential algorithms
Algorithms for which the number of operations is a power of the size of the problem.
⇧ So, our naive recursive algorithm is correct but hopelessly inefficient. It is useful only for small values of n
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 32
Classification of algorithms
WHY SO SLOW?
I Manycomputationsarerepeated!
I Easyfix:Storetheintermediatevalues.
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 33
Classification of algorithms
CAN WE DO BETTER?
A non-recursive function fib2():
def fib2(n):
# Trivial cases
if (n < 0):
return 0
f = [0]*(n+1) # Create an array f[0,...,0] of size n+1
if n o
I
I
return error
if (n < 2):
return n
# Initialization
f[1] = 1
# Fill out the rest of the array
for i in range(2,n+1):
f[i] = f[i-1] + f[i-2]
return f[n]
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 34
Classification of algorithms
BASIC QUESTIONS
1. Is fib2() correct? • Yes,againbydef-
inition of Fn.
2. How efficient is fib2()?
How much time does it take, as a function of n?
• On=n 1
(linear!) Polynomial algorithms
200
150
100
50
00 50
100 150 200
n
in terms of instance
Algorithms for which the number of operations is a polynomial, of any order, of the size of the problem.
Polynomial time is MUCH MUCH better than exponential time!
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 35
O (# operations) n
Classification of algorithms
HOW IT COULD HAVE BEEN BETTER?
Logarithmic algorithms
Algorithms for which the number of operations is a logarithm, of any base, of the size of the problem.
8 7 6 5 4 3 2 1
0
0 50 100 150 200
n
⇧ As log n < n, logarithmic time is better than linear time!
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 36
Base 10
Base e Base 2
O (# operations) n
input size of addition
n of digits single digit sum
Classification of algorithms
CATCH OR SIMPLIFICATION
I We have been counting the number of elementary operations i.e., the number of basic computer steps executed
I Andassumingthatthesebasicstepsastakingaconstantamount of time
I However,thesebasicoperationshavetheirowncomplexity.E.g., • Additionvsmultiplication
• Smallnumbersvslargenumbers
I Nevertheless,thisdoesnotdiminishourconclusion
⇧ It is okay not to be precise whether it's polynomial
⇧ We mostly care about the order logarithmic or We will always express running time by counting the number of basic
computer steps, as a function of the size of the input.
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 37
Big-O
YET ANOTHER SIMPLIFICATION
⇧ It is okay not to be precise
⇧ We mostly care about the order
I Donotmeasuretheliteralnumberofsteps
I Onlyinterestedinthe“important"contributorstothecomplexity I Measuretheorderofcomplexity:Big-Ocomplexity
I Forexample:
• O(2n)!O(n)
⇤ We don’t care about the 2; the n is the important part
• O(n2+n)!O(n2)
⇤ n2 is a lot more important than n
⇤ The value of n2 dominates the value of n
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 38
Big-O
e shape ofalgo carre
exity increase
GROWTH OF FUNCTIONS
Question
Why are we really interested in the theoretical running times of algo- rithms?
Answers
I I I
I I
Togettotheotherside Togetareasonablegradeinthiscourse Tocomparedifferentalgorithmsforsolvingthesameproblem.
Weareinterestedinperformanceforlargeinputsizes. Forthispurpose,weneedonlycomparetheasymptoticgrowth
th
rates of the running times.
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 39
n increase
compl
M. Bodur
Big-O
BIG-O
ai
h
Cgen
IIe
Big-O complexity
Let f(n) and g(n) be two functions. We say f = O(g) (meaning f
grows no faster than g) if there is a constant c > 0 such that f (n) c g(n).
We can think of f and g as the running times of algorithms f and g, respectively. Then, O(g) is called the Big-O complexity of algorithm f .
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 40
Big-O
On TO BIG-O
I I I I I I
I
UsetheOnfunctionstoplaytheroleofthef(n)functions Ignorethelowerorderterms
Dropconstantcoefficients
Droplogarithmbases
Assume that On is an upper bound on the number of operations Assumethattherunningtimeisproportionaltothenumberof
operations
Examples: 2h
• 3n2 +20n+5=O(n2)
• 2log2n+2=O(logn)
• 6nlog5n+30n 15=O(nlogn)
06
57015N
c0C5y
Oczny
M. Bodur
MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 41
Big-O
COMMON FUNCTION CLASSES
Notation
O(1) O(log n) O(n) O(n2 ) O(np ) O(pn )
Name
constant logarithmic linear quadratic polynomial exponential
I pisaconstant
I O(n)6=O(logn)
I O(pn)6=O(np)
I Polynomialsare“worsethan”logarithms
Exponentials are “worse than” polynomials
Source:http://bigocheatsheet.com
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 42
Big-O
NEXT…
I Decisionalgorithms:GreedymethodsandNP-hardproblems I Then,backtobig-Oanalysesandalgorithmswithnumbers
M. Bodur MIE 335_01 Algorithms and Numerical Methods: Introduction to Algorithms 43