Unit 5 – Algorithms and Reporting Verbs I Algorithms 1. Which algorithms do you often use (at school or in your everyday life)? Describe them. 2. Watch the video https://www.youtube.com/watch?v=CvSOaYi89B4 and tick which algorithms are mentioned. · Riding a bicycle · Making a grilled cheese sandwich · The way to the nearest grocery store · Transmitting live video across the Internet · A route finding algorithm · Creating virtual rooms · Designing molecular structures · Preparing weather forecasts 3. Pair work: answer the following questions. a) What is an algorithm? b) What are algorithms used for? c) How old is the concept of an algorithm? d) Which types of algorithms do you know? e) What is the difference between determinism and randomness? 4. Read the text below and compare your answers with the information from the text. In mathematics, computer science, and related subjects, an algorithm is an effective method for solving a problem expressed as a finite sequence of steps. Algorithms are used for calculation, data processing, and many other fields. Each algorithm is a list of well-defined instructions for completing a task. Starting from an initial state, the instructions describe a computation that proceeds through a well-defined series of successive states, eventually terminating in a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate randomness. The concept of algorithm has existed for centuries. It was used by Greek mathematicians, and the term derives from the 9th Century mathematician al'Khwārizmī latinized 'Algoritmi'; however, a partial formalization of the concept began with attempts to solve the Entscheidungsproblem (the "decision problem") posed by David Hilbert in 1928. Subsequent formalizations were framed as attempts to define "effective calculability" or "effective method"; those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's "Formulation 1" of 1936, and Alan Turing's Turing machines of 1936–7 and 1939. Giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem. The text based on https://en.wikipedia.org/wiki/Algorithm 5. Match the terms to their definitions. paradigm recursion exhaustive deterministic including or considering all elements or aspects relating to the doctrine that events are caused by previous steps, i.e. given a particular input, we will always get the same output a pattern, model or methodology for doing something the process of defining a function or calculating a number by the repeated application of an algorithm 6. Find the right description for each paradigm. a) Dynamic programming b) Brute-force c) Reduction ( = transform and conquer) d) Linear programming e) Divide and conquer f) Search and enumeration g) The greedy method 1) ………………………………… or exhaustive search. This is the naïve method of trying every possible solution to see which is best. 2) ………………………………… repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually recursively) until the instances are small enough to solve easily. One such example merge sorting. Sorting can be done on each segment of data after dividing data into segments and sorting of entire data can be obtained in the conquer phase by merging the segments. 3) ………………………………… - when solving a problem using this method, specific inequalities involving the inputs are found and then an attempt is made to maximize (or minimize) some linear function of the inputs. 4) ………………………………… involves solving a difficult problem by transforming it into a better known problem. The main goal is to find the simplest transformation possible. 5) ………………………………… is the method which models problems on graphs. A graph exploration algorithm specifies rules for moving around a graph. This category also includes search algorithms, branch and bound enumeration and backtracking. 6) ………………………………… is used when the optimum solution to a problem can be constructed from optimal solutions to overlapping subproblems, which avoids recomputing solutions that have already been computed. 7) ………………………………… is similar to a dynamic programming algorithm, but the difference is that solutions to the subproblems do not have to be known at each stage; instead a "greedy" choice can be made of what looks best for the moment. It is not exhaustive, and does not give accurate answer to many problems. But when it works, it will be the fastest method. 7. Which algorithms would you use in these situations? a) Find the shortest path to a goal from a vertex in a weighted graph using the shortest path to the goal from all adjacent vertices. …………………………. b) Problems such as the maximum flow for directed graphs. ……………….. c) Finding the median in an unsorted list involves first sorting the list and then pulling out the middle element in the sorted list. ………………. d) Problems such as playing chess. ……………….. ex. 6+7 based on https://www.scriptol.com/programming/algorithms-classification.php Divide and Conquer Algorithm divide and conquer www.CartoonStock.com 8. Watch parts of a lecture on divide and conquer problems. Decide whether the statements are true or false. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis- of-algorithms-spring-2015/lecture-videos/lecture-2-divide-conquer-convex-hull-median-finding/ 1. The lecturer will show two attractive divide and conquer problems today. 2. The convex hull is the lecturer’s most favourite solution to the divide and conquer problems. 3. The lecturer uses an object which helps illustrate a three dimensional problem. 4. The lecturer shows what a convex hull means by stretching the string around points. 5. Segments and tangents mean the same. 6. The input for the problem is just the set of points with the coordinates. 7. Gift wrapping algorithm has little in common with the convex hull. 8. The lecturer suggests that students should minimize gift wrapping paper. 9. Summarize the lecture using appropriate verbs. II Reporting verbs (by Keith Taylor ) The most common verbs we use to report what someone says are "say" and "tell". These are the verbs which students learn first when they learn reported speech. These are fine, of course, but there will come a time in your students' learning when they want to use other verbs to more accurately report what someone says. We use many different reporting verbs in English, and the way we use them in a sentence varies, for example: Verb + gerund: James denied taking the money. Verb + preposition + gerund: They apologized for arriving late. Verb + infinitive: Susan promised to work hard. Task 1. Read the story and answer the questions using reporting verbs. 7 year old Adam was leaving school one afternoon when he saw a group of older boys, aged 8, smoking. One of them, Chris, said 'Hey, Adam, have a drag of this'. What did Chris do?........... 'No, I don't want to', Adam replied. What did Adam do?.............................................................. 'Go on. It's really good', said Chris, and then Trevor said 'I smoke 5 a day.' What did Chris do? And Trevor? ……………………………………………………………………………………………. 'Go on. You'll like it and you can join our gang', said Chris. 'Well, OK then', said Adam. What did Chris do? And Adam? …………………………………………. Adam coughed and coughed and he felt sick. On his way home he stopped to buy some mints to get rid of the smell. But when he got home Mummy was waiting for him and she gave him a big kiss. 'Adam. You've been smoking!' she said. What did Mummy do? ………………………………………. 'No, I haven't.' What did Adam do? ……………………………………………………………………. 'Tell me the truth Adam.' 'OK, I did smoke, but only a little.' What did Adam do? ……………………………………………….. 'Adam, if you ever smoke again I'll tell Daddy.' What did Mummy do? ………………………………. 'No Mummy, please don't tell Daddy. I'm really sorry. I'll never smoke again.' What did Adam do? …………………………………………………………………………………………………………… 'OK, Adam. You shouldn't listen to those naughty boys. Now, why don't you go upstairs and do your homework?' What did Mummy do? ……………………………………………………………………. Task 2. There are some reporting verbs. Divide them into columns according to the pattern they use. remind promise blame deny admit encourage offer congratulate apologize accuse recommend invite refuse advise insist suggest threaten warn agree decide add emphasise affirm argue explain verb object infinitive verb infinitive verb (that) verb -ing verb object preposition --ing verb preposition --ing Task 3. A role-play. Work in the groups of 3 – 4. You are friends who share a house, but you have been living together for some time, and your habits are starting to annoy each other. You are going to have a house meeting to discuss your complaints! If a student has slips of paper with, for example, "deny", "accuse" and "apologise", (s)he must deny doing something, accuse someone of doing something and apologise for doing something. Model activity: "Mario, you're always leaving your laundry on the floor." "Elena, if you don't stop playing loud music at 2am, I'll throw your stereo out of the window." Ask the students what you said. (You accused David of leaving his laundry on the floor. You threatened to throw Elena's stereo out of the window.)