Algorithms: From Euclid to the iPad

Fall 2011

2:00-2:50 Th B11 MLH

**Instructor:**
Sriram V. Pemmaraju

101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956

**Office Hours:** 2:30-3:30 W and by appointment

**Course website:** `http://www.cs.uiowa.edu/~sriram/2/fall11/`

**Department website:** `http://www.cs.uiowa.edu/`

**Algorithms: From Euclid to the iPad** is a "first year seminar" that aims to introduce you to the intellectual life of the University by means of engaging a topic
that is increasingly playing a central, though often invisible, role in our lives.
Algorithms are "recipes" for solving computational problems and have been around since Euclid, who in 300 BCE
described an algorithm for computing the greatest common divisor of a given pair of numbers.
Now "algorithmic thinking" is viewed as the greatest contribution of the field of computer science
to every day life. Algorithms are used wherever computers are; search engines, weather prediction, drug design, financial
markets, supply-chain management and even "JEOPARDY!" are just a few examples from among many.

In this seminar, we will discuss algorithms for a variety of computational problems. Throughout the seminar we will focus on issues of correctness and efficiency of the algorithms we discuss. We will also try to understand inherent limits of the power of algorithms and why some problems seem so intractable. To place all of this in a larger context, we will also discuss popular perceptions of algorithms, as evidenced by articles in NYT, WSJ, New Scientist, etc.

Syllabus document, Announcements, Homeworks, Weekly Topics, Online Resources

(From xkcd)

**Due 9-1**Homework 1**Due 9-8**Read this Sorting Activity and answer the question at the bottom of Page 66.**Due 9-22**Homework 3**Due 10-6**Homework 4**Due 10-27**Homework 5**Due 11-3**Homework 6**Due 11-17**Homework 7

**8-25**Getting to know each other. Searching algorithms; an activity involving*binary search*.**9-1**Pseudocode for binary search. Translating the pseudocode into a Python program. The*divide-and-conquer*paradigm. The*sorting*problem.**9-8***Selection sort*. Managing to sort while comparing only a small fraction of pairs of elements:*Merge sort*.**9-15***Greedy algorithms*for minimum spanning trees, making change, and the traveling salesman problem.**9-22***Search Algorithms*for solving mazes; the*depth-first search*algorithm.**9-29**More on search algorithms:*breadth-first search*and*Dijkstra's shortest path algorithms*.**10-6**More on Dijkstra's algorithm, shortest paths in Google maps.**10-13**The technology behind Google maps: TIGER files, satellite images, street views, KML files, Google APIs, Google mashups, etc.**10-20**Playing around with some Google mashups.**10-27**Introduction to web search.**11-3**Crawling the web and data structures for indexes of the web.**11-10**Link Analysis: Computing PageRank and Kleingberg's HITS algorithm.

- Binary Search Animation
- Computer Science Unplugged Many of the interactive activities we are doing in class are from this resource.
- YouTube has many videos on sorting. Here are two that I liked. Merge Sort with Transylvanian-saxon (German) folk dance, Sorting Algorithms.
- Two problems we discussed in the context of
*greedy algorithms*are the Traveling Salesman Problem and the Minimum Spanning Tree Problem. - A nice article and animation on algorithms for building mazes and solving them.
- The ladders game: dictionary of 5-letter words, java program to play the ladders game, sample out of the java program.
- Animations for Dijkstra's algorithm: shortest paths from Tokushima
- Google Street View, Google map maker, Google map mashups and more Google mashups.
- KML Tutorial.
- The Anatomy of a Large-Scale Hypertextual Web Search Engine. The original "Google" paper by Brin and Page.
- How Internet Search Engines Work by HowStuffWorks.com.