CSCI B503 Analysis of Algorithms.  

Instructor: Funda Ergun


Basic Information

Welcome to CSCI 503!

I will use this page to post various announcements and documents; any information you need about this class will be in one of these documents. Please check this page regularly for updates.

Regarding homework submissions, please look below to where the assignments are for more info.

Important Announcement

Midterm coming up, Oct 10/11 (depending on which class you're in).

Sections from CLRS: Chapters 2, 3, 4 (except 4.2, 4.6), 7 (except we were not very thorough on the analysis of randomized quicksort), 8.1, 9, 16.1, 16.2, 16.3.

Logistics

Instructor: Funda Ergun. Office: LH 428C. Email: fergun@indiana.edu.

Instructor office hours: M 1:45 --2:45 or by appointment.

AIs: We have a bunch. Stay tuned for contact and office hour information.

Textbook: Introduction to Algorithms. T. Cormen, C. Leiserson, R. Rivest, C. Stein.

What to Call Me

Funda. No, we didn't do this in my home country either, but I got used to it and so can you. What not to call me: Ma'am, anything that starts with Miss, Ms., Mrs. -- tolerable (for a little while) is stuff that starts with "Professor" if you really must.

What This Course is about:

This course studies algorithms: what they do, how to construct them, how to analyze them for correctness and efficiency. Every time you need to solve a problem, write a program, design a technique, you need to understand your problem, as well as how to solve it. Once you (think that you) have a solution, you need to be able to show without a doubt that it solves a problem, and solves it well. In this class we cover more of how to do all of this. We will look at general techniques for solving algorithmic problems, then learn how to design our own.

This is a crucial course for any computer scientist (as our MS and PhD requirements demonstrate), and is quite mathematical. You will not do major/complicated programming here. It is also rumored to help with interview questions when you're looking for a job. But, most importantly, in a world where computer programs do so much for us, you will learn how to solve computational problems. By the time you get out, you should be ready to analyze most algorithms that come your way, and look at any theoretical problem, understand its requirements, and design a correct (and hopefully efficient) solution for it.

At the end of this course, you should be able to:

What You Need to Know for This Course

This is a theoretical, graduate course; thus, we expect you to come with a certain amount of discrete math/data structures/algorithms knowledge from your undergrad studies. These include a comfortable level of basic arithmetics and algebra (are you super fluent with logs and exponents?), a good intuition about proof techniques (induction, contradiction, proof by counterexample, etc), discrete math/logic (sums, pigeonhole principle, sets, and so on), graph algorithms (DFS, BFS fluency, how do MST or SP algorithms work?), basic data structures (how good are you with balancing heaps?), big Oh and big Theta, basic algorithm design (types of recursion, how to get rid of recursion), and so on. For an idea about what IU undergrads are expected to have mastered by the time they start grad school, check out the curricula for 343 and 403.

Grading

Grade distribution: one midterm, around 5 homeworks, one project, final. Percentages 25, 25, 15, 35 per cent respectively. No collaboration allowed unless otherwise noted.

Late penalties: 10 points each late calendar day. Talk to me if you have a valid excuse for submitting your work late and the penalty might be waived.

The project The project will involve several stages involving a proposal, an intermediate submission, and a final submission. The stages before the final submission will not be graded, but not turning them in will cost you project points. The project will involve some coding (and hopefully some thinking!) -- other assignments will be (mostly) theoretical.


Tentative List of Topics

I will add stuff here about how we went about things as we cover the topics to jog your memory when you want to go back and study this stuff for the exams:

Warmin up to mathematical and algorithmic background. What is an algorithm, analyzing algorithms.

Growth of functions, asymptotic complexity. Big Oh, Theta, Omega. Little oh, omega.

A brief review of sorting/searching. Worst and average case complexity, deterministic vs randomized. Proof of lower bound on comparison sorting.

Recurrences, Master Theorem. Where do recurrences come from? How do we solve them using a recursion tree? Master theorem.

Greedy algorithms. Optimal substructure. Activity selection, Huffman tree, quick look at MST.

Dynamic programming. Relationship to recursive algorithms. Rod-cutting, matrix chain multiplication.

Graph algorithms: Prim's MST, Dijkstra's shortest paths, max flow.

NP-Completeness. Big one. What is it? Why does it matter? How do we prove a problem is NP-complete?

Advanced topics as time permits: Randomized algorithms, approximation algorithms.


Homeworks, etc.

All homeworks are due in class. You can write by hand, type using a tool such as latex (or word if you're brave :-) You are allowed to consult the book and/or your notes, but please don't work in groups or look in another book, or consult the Internet... If you have any questions, please email me or ask in class.

Resources: Here you find various resources for this course. I will add to these as I find new ones; you can email me any suggestions.

Puzzles: This is where you can find our puzzles. Don't be just a consumer; send me any puzzles you might have.