Algorithms (Introduction)
Algorithms (Introduction)q Readings: [SG] Ch. 1, Ch. 2q Chapter Outline:1. Chapter Goals2. What are Algorithms [SG] Ch. 2.13. Pseudo-Code to Express Algorithms [SG] Ch. 2.24. Some Simple Algorithms5. Examples of Algorithmic Problem SolvingLast Revised: August 2016.Hon Wai Leong, NUS(UIT2201 Notes) Page 1 Leong Hon Wai, 2003--
1. Goals of Algorithm Studyq To develop framework for instructing computerto perform tasks (solve problems)q Algorithm as a“means of specifying how to solve a problem”q To introduce the idea of decomposing complextasks into simpler tasks;Hon Wai Leong, NUS(UIT2201 Notes) Page 2 Leong Hon Wai, 2003--
Recurring Principles in CS & ITRP1: Multiple Levelsof Abstraction(very high to very low)RP2: One Data,Multiple Views(thru diff interfaces)RP3: Define a (small) setof basic primitives(building blocks)RP4: Divide & Conqueraka(Decomposition)RP5: “The Power of Iteration”(aka Recursion)Hon Wai Leong, NUS(UIT2201 Notes) Page 3 Leong Hon Wai, 2003--
Computing Devices q Computing devices are dumbv How to instruct a dumb mechanical /computing device to solve a problemq Express instructions using“a small, basic set of primitive instructions”Hon Wai Leong, NUS(UIT2201 Notes) Page 4 Leong Hon Wai, 2003--
Dog obedience training RP3: Define a (small) setof basic primitives(building blocks)sit, heel, down,stand, come, etcSource: http://lacetoleather.com/obedience.htmlHon Wai Leong, NUS Leong Hon Wai, 2003--(UIT2201 Notes) Page 5
Dog obedience training Higher-order primitives(complex building blocks)Roll-over, Shake-a-paw,Wave, High-Five, etcSource: http://lacetoleather.com/easydogtricks.htmlHon Wai Leong, NUS Leong Hon Wai, 2003--(UIT2201 Notes) Page 6
q Chapter Outline:1. Chapter Goals2. What are Algorithms [SG] Ch. 2.11. Real Life Examples (origami, recipes)2. Simple Example: Calculating Mile-per-Gallon3. Definition of Algorithm4. A B C (self-study, [SG]-C1.2, 2.1)3. Pseudo-Code to Express Algorithms4. Some Simple Algorithms5. Examples of Algorithmic Problem SolvingHon Wai Leong, NUS(UIT2201 Notes) Page 7 Leong Hon Wai, 2003--
Computer Science and Algorithms q Computer Science is the study of algorithms, includingv their formal and mathematical propertiesv their hardware realizations,v their linguistic (software) realisations,v Their applications (to diverse areas)(Read carefully Ch-1.2 of [SG])Hon Wai Leong, NUS(UIT2201 Notes) Page 8 Leong Hon Wai, 2003--
Algorithmsin Real-LifeHon Wai Leong, NUS(UIT2201 Notes) Page 9 Leong Hon Wai, 2003--
Algorithms: Real Life Examplesq Many Real-Life Analogiesv Dog Training (seen already )v Directions: How to go to USP-JAR (tutorial )v Origami: The Art of Paper Foldingv Cooking: Recipe for preparing a dishKeep in Mind:1. Framework: “Input, output, hardware, software ”2. Algorithm: “The actual step-by-step instructions”3. Abstraction: “Decomposing / Simplifying”Hon Wai Leong, NUS(UIT2201 Notes) Page 10 Leong Hon Wai, 2003--
OrigamiasAlgorithmHon Wai Leong, NUS(UIT2201 Notes) Page 11 Leong Hon Wai, 2003--
An Origami Analogy for Algorithmq Framework:“Origami or Paper-Folding language”q Algorithm:“Sequence of Paper-Folding Instructions”(step-by-step instructions for each fold)q Primitives and Problem Decompositionv Start with a Bird Base; v Finish the Head;v Finish the Legs; Finish the ird-base.htmlHon Wai Leong, NUS(UIT2201 Notes) Page 12 Leong Hon Wai, 2003--
Primitives in OrigamiRP3: Define a (small) setof basic primitives(building blocks)q Primitive folds in Origamiv Valley fold, Mountain fold, Triangle foldv Squash fold, Petal foldv Inside and Outside Reverse foldsHon Wai Leong, NUS(UIT2201 Notes) Page 13 Leong Hon Wai, 2003--
Primitive Fold: Valley FoldAnd similar forMountain FoldHon Wai Leong, NUS(UIT2201 Notes) Page 14 Leong Hon Wai, 2003--
Primitive Fold: Triangle FoldAlso calledShawl or Diaper FoldHon Wai Leong, NUS(UIT2201 Notes) Page 15 Leong Hon Wai, 2003--
Primitive Fold: Inside Reverse FoldUseful for makingheads, tails, legs, etcHon Wai Leong, NUS(UIT2201 Notes) Page 16 Leong Hon Wai, 2003--
“Higher-level Primitives” in OrigamiRP1: Higher-Levels Abstraction(Define higher-level primitivesfor often-used sequences)q Patterns of Often-used Folds:v Square basev Kite base à Diamond base,v Square base à Bird base,v Blintz base, Boat base, Helmet base,v Organ base, Pig base, etc Hon Wai Leong, NUS(UIT2201 Notes) Page 17 Leong Hon Wai, 2003--
Higher-Level Primitive: Square BaseThere is also anothermethod to fold aSquare BaseStarting point for frog,ninja star, star box, etcHon Wai Leong, NUS(UIT2201 Notes) Page 18 Leong Hon Wai, 2003--
Square Base à Bird BaseUsed for all kinds ofbirds, such as crane,flapping bird, etcHon Wai Leong, NUS(UIT2201 Notes) Page 19 Leong Hon Wai, 2003--
Problem Decompostion in Origamiq Making an Origami crane.htmlq Problem Decompositionv Start with a Bird Base;v Fold the outside corners inside v Using reverse fold, make neck and tailv Finish the Head;RP4: Divide & Conquerv Finish the Wings;akaq Modular ons.com/modular-origami-instructions.htmlHon Wai Leong, NUS(UIT2201 Notes) Page 20 Leong Hon Wai, 2003--
Cooking RecipesasAlgorithmHon Wai Leong, NUS(UIT2201 Notes) Page 21 Leong Hon Wai, 2003--
A Recipe Analogy for AlgorithmRecipe for a chocolate mousseIngredients:8 ounces of semi-sweet chocolate pieces,2 tablespoon of water,1/4 cup of powdered suger,6 separated eggs, .“Melt chocolate and 2 tablespoons water in double boiler.When melted, stir in powdered sugar; add butter bit by bit. Set aside.Beat egg yolks until thick and lemon-colored, about 5 minutes.Gently fold in chocolate. Reheat slightly to melt chocolate, ifnecessary. Stir in rum and vanilla.Beat egg white until foamy. Beat in 2 tablespoons sugar; beat untilstiff peaks form. Gently fold egg whites into chocolate-yolk mixture.Pour into individual serving dishes.Chill at least 4 hours.Serve with whipped cream, if desired. Makes 6 to 8 servings.”Hon Wai Leong, NUS(UIT2201 Notes) Page 22 Leong Hon Wai, 2003--
Framework (for the Recipe Example)Sample Problem: Making chocolate mousseAlgorithmsFramework for ils, oven, pots, pens, chefRecipeChocolate s,oven, bakerPrimitive (Basic) Operations: pour, mix, stir, drip, stir-fry bake, boil, melt, open-oven-door, remove-pan measure time, volume, weightChocolate mousseHon Wai Leong, NUS(UIT2201 Notes) Page 23 Leong Hon Wai, 2003--
RP1: Multiple Levels of Abstractionq The level of abstraction(level of detail of the instructions) should vary with thesophistication of the hardware / software toolsq Hierarchy of abstraction levels L0: Prepare Chocolate mousse for 5 peopleL1: Prepare chocolate mixture;Prepare chocolate-yoke mixture;Prepare egg-white batter; Hon Wai Leong, NUS(UIT2201 Notes) Page 24 Leong Hon Wai, 2003--
RP1: Multiple Levels of Abstractionq The level of abstraction(level of detail of the instructions) should vary with thesophistication of the hardware / software toolsq Hierarchy of abstraction levels L0: Prepare Chocolate mousse for 5 peopleL1: Prepare chocolate mixture;Prepare chocolate-yoke mixture;L2: Meltchocolateand 2batter;tablespoonsPrepareegg white water stir in powdered sugar; add butter bit-by-bitL3: take a little powdered sugar,pour it into the melted chocolate, stir it in,take a little more sugar, pour , stir ,Hon Wai Leong, NUS(UIT2201 Notes) Page 25 Leong Hon Wai, 2003--
RP1: Multiple Levels of Abstractionq Hierarchy of abstraction levels L0: Prepare Chocolate mousse for 5 peopleL1: Prepare chocolate mixture;Prepare chocolate-yoke mixture;L2: Meltchocolateand 2batter;tablespoonsPrepareegg white water stir in powdered sugar; add butter bit-by-bitL3: take a little powdered sugar,pour it into the melted chocolate, stir it in,take a little more sugar, pour , stir ,L4: take 2365 grains of powdered sugar, pour them into themelted chocolate, pick up a spoon anduse circular motion to stir it in, L5: move your arm towards the ingredients at an angle of 14º,at a velocity of 0.5m per second, Hon Wai Leong, NUS(UIT2201 Notes) Page 26 Leong Hon Wai, 2003--
RP1: Multiple Levels of Abstraction(very high level to very low)q Why have some many levels of abstraction?v L0: Good for “bosses”v L1: Good for experienced chefsA Master Chef knowsv L2: Good for inexperienced chefsALL the levelsv L3: Good for newbie chefsv L4: Good for an “automated” processv L5: Good for people who needs toprogram the automated processq Question: What is the appropriate level?Hon Wai Leong, NUS(UIT2201 Notes) Page 27 Leong Hon Wai, 2003--
Elon Musk’s Interviews"If someone was really the person who solved theproblem, they'll be able to answer at all levels — they'llbe able to go down to the brass tacks," Musk explains."And if they weren't, they'll get stuck.""Anyone who struggled hard with a problem neverforgets it," Musk said. Elon Musk: CEO of SpaceX, Tesla, w-at-tesla-20160622-gpps1tHon Wai Leong, NUS(UIT2201 Notes) Page 28 Leong Hon Wai, 2003--
Summary: Cooking Analogyq Framework:“Cooking or Recipe mini-language”q Algorithm:“Recipe for Chocolate Mousse”(step-by-step instructions)RP4: Divide & Conqueraka(Decomposition)q Problem Decompositionv L0 task is decomposed into L1 tasks Prepare the Chocolate Mixture; Prepare Chocolate-Yoke Mixture; Prepare Egg-White Batter;v Each L1 task is further decomposed into L2 tasksv And so on Hon Wai Leong, NUS(UIT2201 Notes) Page 29 Leong Hon Wai, 2003--
Hon Wai Leong, NUS (UIT2201 Notes) Page 17 Leong Hon Wai, 2003-- “Higher-level Primitives” in Origami ! Patterns of Often-used Folds:
THIRD EDITION Naveed A. Sherwani Intel Corporation. KLUWER ACADEMIC PUBLISHERS NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW. eBook ISBN: 0-306-47509-X . Graph Search Algorithms Spanning Tree Algorithms Shortest Path Algorithms Matching Algorithms Min-Cut and Max-Cut Algorithms
Graph algorithms Geometric algorithms . Textbook Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Third Edition, McGraw-Hill, 2009. 4 Suggested Reading Polya, How to Solve it, Princeton University Press, 1957. Preparata and Shamos, Computational Geometry, an . limitations of algorithms? Computability .
Swarm Intelligence and bio-inspired computation have become increasingly popular in the last two decades. Bio-inspired algorithms such as ant colony algorithms, bat algorithms, bee algorithms, firefly algorithms, cuckoo search and particle swarm optimization have been
Metaheuristic Algorithms Genetic Algorithms: A Tutorial “Genetic Algorithms are good at taking large, potentially huge search spaces and navigating them, looking for optimal combinations of things, solutions you might not otherwise find in a lifetime.” - Salvatore Mangano Computer Design, May 1995 Genetic Algorithms: A Tutorial
algorithms, which are very different in principle than the above algorithms, are covered in Chapter 6. Genetic algorithms—search and optimization algorithms that mimic natural evolution and genetics—are potential optimization algorithms and have been applied to many engineering design problems in the recent past.
In this course we study algorithms for combinatorial optimization problems. Those are . and so it is unlikely that we can design exact e cient algorithms for them. For such problems, we will study algorithms that are worst-case e cient, but that output . make us give a second look at the theory of linear programming duality. Online Algorithms.File Size: 832KB
use of these algorithms. The algorithms assist the staff concerned in making analyses and taking decisions. This does not detract from the fact that – viewed from the aspect in the year 2021 – there is room for improvement, as algorithms are set to be used more and more often in the years ahead. If algorithms
selection algorithms can be categorized as supervised algorithms [35], [41], unsupervised algorithms [11], [19] or semi-supervised algorithms [43], [49]. From the per-spective of selection strategy, feature selection algorithms broadly fall into three models: filter, wrapper or em-bedded [16]. The filter model evaluates features without
