22C:002:001 First year Seminar
Algorithms: From Euclid to the iPad
Fall 2011

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.

Prerequisite
We will do a small amount of programming in class, but students are not required to have any previous computer programming experience. However, basic knowledge of how to use a computer (e.g., simple word processing, using a web browser) will be assumed. Ocassionally, some middle-school level mathematics will be needed to communicate an algorithmic idea and I will assume that students have a middle-school level competency in arithmetic, algebra, and geometry.

Textbook
There is no required textbook for this course. I will hand out articles from newspapers and magazines and chapters from books, as the semester progresses. Occasionally I will use slides and when I do, I will post these on the course page. I will also do a bit of programming in class and when I do, I will post these programs on the course page as well.

Tentative List of Topics
The course is broken up into three parts. We will spend about 9 weeks on the first part and 3 weeks each on the remaining two parts. Here are more details on each of the three parts.

1. How do I get to McLean Hall from my dorm room? In this part of the course we will study elementary algorithms for searching, sorting, making change, getting married, etc.

2. How does Google know all that stuff?: In this part of the course we will study a couple of applications of algorithms to large systems. The current plan is to look under the hood of search engines such as Google and understand (at the most basic level) how their algorithms work.

3. Can all problems be solved? It turns out that not all computational problems can be solved. And yes, this can be proved! Even worse, there are lots of computational problems that can be solved, but not efficiently enough. In this part of the course we will study intractability of various computational problems and try to understand what makes certain problems intractable and how this is dealt with in practice.

Grading
Grades will be based on in-class participation, weekly homeworks, 2-3 programming assignments, and a short term paper. Plus/Minus grading will be used for the course. Here are more details.

• In-class Participation: 30% I see your in-class participation as the key to your individual success in the course as well as the success of the course on the whole. I will do my best to make the material engaging and the class environment conducive to free and open discussion. As an incentive to get you to speak up, I have decided to set aside 30% of the grade for class participation. After every class, I will write down my impressions of your class participation and will eventually turn these impressions into a number (out of 30).

• Homeworks: 25% You will be assigned weekly homeworks that may involve, among other things, reading and critiquing articles, designing and describing simple algorithms, doing simple calculations pertaining to an algorithm's efficiency, presenting informal arguments for why an algorithm may or may not be correct, etc.

• Programming Assignments: 20% You will be assigned 2-3 programming assignments in the second half of the course. Since this is not a programming course and since you are not computer science students, these programming assignments will be quite elementary. My plan is to give you an "almost complete" program that you'll have modify a bit to get it to run as you want. So the focus will not be on designing your own program, but on understanding my program and seeing how it encodes algorithms we have discussed in class.

• Term Paper: 25% I'll assign a short term paper (4 pages long) in the second half of the semester. My plan is to have you turn it back in 3-4 weeks before the end of the semester and give you feedback which you can use to turn in a polished, final version during the last class of the semester.

Late submissions will not be accepted and in general you will be better off turning in what you have on time rather than seeking extra time to complete your work. Excused absence forms are available at the Registrar's website. Recently, the Student Health Services changed the policy on class excuses, please read here.

Communicating with me
Asking me questions by e-mail is quite appropriate and I will try to answer any e-mails related to 22C:002 within 12 hours of e-mail receipt. You should make sure to include 22C:002 (or some reasonable variant) in the subject line to help me get to your e-mail quickly. I will occasionally send e-mail announcement to all students in the class and you are responsible for all official correspondence sent to the UI address (@uiowa.edu). Make sure that you check this e-mail account regularly. I would also prefer receiving e-mails from your uiowa account, rather than from commercial e-mail providers (e.g., gmail or yahoo!). I will try to call you by your preferred name. As a matter of professionalism, I'd prefer you call me "Prof. Pemmaraju" or "Dr. Pemmaraju". I will insist that we all start our e-mails with the recipient's name (not "Hey" or just blank) and end our e-mails with the sender's name.

Course Home
This course is run by the Computer Science department which is part of the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found online here.

Students with disabilities
I would like to hear from anyone who has a disability which may require seating modifications or testing accommodations or accommodations of other class requirements, so that appropriate arrangements may be made. Please contact me during my office hours.

Academic Dishonesty
Academic dishonesty will not be tolerated. Under no circumstances should you pass off someone the work of someone else as your own. This also applies to code or other material that you might find on the internet. Note that we will routinely use available software systems for detecting software plagiarism, to test any suspicions we might have. If you are unclear about what constitutes academic dishonesty contact your professor or consult the policy in the CLAS Bulletin (online version). We do want students to talk to each other about concepts and ideas that relate to the class. However, it is important to ensure that these discussions do not lead to the actual exchange of written material.

Student Complaints
If you have any complaints or concerns about the course please feel free to talk to me. You are also welcome to get in touch the the Computer Science department chair, Prof. Alberto Segre (alberto-segre@uiowa.edu, 319-335-1713, 14D McLean Hall). Consult the college policy on Student Complaints Concerning Faculty Actions (online version) for more information.

Classroom Etiquette
Showing up to class late, leaving your cell phone ringer on, etc. can be quite distracting to the instructor and fellow students. If you are in class, it is your responsibility to pay attention and to make sure that you are not doing anything that makes it harder for fellow-students to pay attention. When disruptive activity occurs, a University instructor has the authority to determine classroom seating patterns and to request that a student exit immediately for the remainder of the period. One-day suspensions are reported to appropriate departmental, collegiate, and Student Services personnel (Office of the Vice President for Student Services and Dean of Students).

University Statement on Sexual Harassment
Sexual harassment subverts the mission of the University and threatens the well-being of students, faculty, and staff. All members of the UI community have a responsibility to uphold this mission and to contribute to a safe environment that enhances learning. Incidents of sexual harassment should be reported immediately. See the UI Comprehensive Guide on Sexual Harassment for assistance, definitions, and the full University policy.

Reacting Safely to Severe Weather
In severe weather, class members should seek appropriate shelter immediately, leaving the classroom if necessary. The class will continue if possible when the event is over. For more information on Hawk Alert and the siren warning system, visit the Public Safety web site.