Syllabus, CS320 Algorithms - Theory and Practice, Spring 2020, McConnell   

Policies  ·  Schedule  ·  Syllabus




Instructor: Graduate Teaching Assistant:

Textbook:

Prerequisites:

Lectures


Course Goals

The course is about learning principles for organizing your thinking when solving programming problems, and not about memorizing details and facts. You must practice ways of establishing that an algorithm is correct, analyzing its worst-case big-O time bound, and being able to fill in the assumed details needed to turn it into a program. You must practice creative ways of identifying which algorithm design technique is appropriate to a problem and being sure your solution is correct.

Getting good at these skills will allow you to come up with correct and efficient algorithms on your own. You will learn to identify bottlenecks in a program that determine the time bound, and get ideas about how the problem might be solved more efficiently.

We will study big-O analysis at a more advanced level than in CS200. We will study examples of graph algorithms, greedy algorithms and greedy proofs, the divide-and-conquer strategy and how to derive time bounds for it, dynamic programming, and, if time allows, randomized algorithms and NP-completeness.

Success at these techniques relies on practice and experience. It is similar to learning to play an instrument or to play chess: you get vastly better at it with a whole lot of practice. Be patient and have faith that you will get good at it if you stick with it conistently over time.

Another focus of the course will be on developing your ability to make sense of the literature of our field. Much of what you learn in your degree program will be out of date in the future. A goal of college should be to teach you how to teach yourself. Reading the literature in our field is a completely different type of "literacy" from what you learn from a class on English literature. I will have you practice on the assigned course readings, I will lecture on how to make sense out of them, and I will use clicker quizzes to reward those who practice these skills.

Much more important than how much time you put into the course is how you organize your time. If you skim the readings before the corresponding lecture, you will get more out of the lecture. You will also be in a position to identify anything that the lecture hasn't clarified for you and to ask about it. That's less time you have to spend later finding someone who can explain it to you. If you do these things, you will have to spend less time figuring out homework solutions. If you start working on a homework when it is assigned, you can ask questions in class or in office hours about problems that are taking you too long to figure out. This will save you a lot of time in the course that you could otherwise waste on the night before it is due. Revisit the same material many times over many days, refining and simplifying your understanding of it each time, asking yourself questions about it. If you approach it in this way, the class will take significantly fewer hours out of your week and it will be more interesting.

Cultivate your own curiosity and your pride in your work to stay motivated, organized, and thinking creatively.