Algorithms and Data CS 4800,
Spring 2012.
Instructor: Karl Lieberherr.
Textbook: Algorithm Design by Jon Kleinberg and Eva Tardos, Pearson and Addison Wesley. 2006, ISBN 0-321-29535-8.
Your first task is to sign up for Piazza by the second class
meeting.
Final Exam 1:00 pm - 3:00 pm F Shillman Hall 420 Apr 20, 2012
Piazza for Algorithm Students
|
Piazza Interface for Algorithmic Problem_Solving
|
Course Directories
|
Syllabus
|
WolframAlpha
|
Blackboard .
Homeworks
Information about Logic and Games
General Information
Properties of the Quantifier Game
Engagement and Cooperation with Peers In
the playground you play, you get engaged to keep your reputation
high. To keep a high reputation you must learn the skills of the domain
and apply them in the playground in cooperation with your peers.
Learning by doing
You oppose claims made by others and you defend your own claims.
This tests your skills in the playground.
The quality of your attacks and defences determines your reputation.
The quantifier game is fun. It is hard fun.
Even if you play against yourself.
Playing the quantifier game
is different than getting together with other students and solving problems.
You follow a structured protocol to guide your thinking in the right direction
to solve the problem.
Once the problem is solved, the quantifier game becomes
uninteresting and you stop playing.
The quantifier Game in Action
Recipe to teach constructive topic D:
Define a playground for D
and have the students play.
The winning students are teachers and help the
other students learn the material through
skill demonstrations.
The winning students demonstrate superior knowledge
in domain D in the context of the given playground.
It is important to notice that in order to win
in the game you only need clever algorithms.
You don't need a proof that they are correct.
The text book and lectures will show you how
to reason about correctness.
Course Description
We will study algorithmic problems from conception to implementation, following the text book.
The text book says in the Preface:
"Algorithmic problems form the heart of computer science
but they rarely arrive as cleanly packaged,
mathematically precise questions.
Rather, they tend to come bundled together
with lots of messy, application-specific detail,
some of it essential, some of it extraneous.
As a result, the algorithmic enterprise consists
of two fundamental components:
the task of getting to the mathematically clean
core of a problem and then the task of
identifying the appropriate algorithm design
techniques."
In this 2012 edition of the course we will
practice both components.
Knowledge about algorithm design turns out to be pivotal to your career as some interesting and desirable companies
first screen students with algorithm questions before they advance to later
stages in the interview process.
What are algorithms about?
We produce an artifact that can
solve problems for us and we make predictions about this artifact.
The most important prediction is that the algorithm is correct.
Often we make predictions about the resource consumption of the algorithm.
The time consumed by the algorithm is an important concern, but space and
energy could be other resources of interest.
The prediction is made over a set of instances, such as all instances of
size n.
We make other predictions about algorithms: how well they solve problems relative to some standard, like the maximum solution.
Lectures
|
Office Hours
.
The Quantifier Game
The Essence of the Quantifier Game: Rules
Syllabus
We will basically follow the syllabus sketched on page xx of the text book.
Week 1
Chapter 1,
Preparation for hw 1,
working with claims,
Gale-Shapley Algorithm,
1.2 Five Representative Problems.
Week 2
Chapter 2,
Basics of Algorithm Analysis,
Preparation for the Jar Stress Testing Homework hw2: Chapter 2, exercise 8.
Week 3
Chapter 3: Graphs,
hw3: Jar Stress Testing continued,
Topological sorting implementation and systematic optimization.
Week 4
Chapter 4:
Greedy Algorithms.
Week 5
Chapter 5:
Divide and Conquer, Midterm.
Week 6
Divide and Conquer.
Week 7
Dynamic Programming
Week 8
Dynamic Programming
Week 9
Network Flow
Week 10
Network Flow
Week 11
NP and Computational Intractability
Week 12
Linear Programming, Approximation Algorithms.
Grading
The grade will be based on a
open-book midterm (20%),
open-book final (30%),
homework solutions (30%) and class participation.
This term we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com.
Find our class page at: http://www.piazza.com/northeastern/winter2012/cs4800.
You should actively participate in class
with questions and answers. Make active use of Piazza:
when you know a good answer please enter it on Piazza.
Computational Patterns
This website makes a good attempt to capture algorithmic knowledge in the form of patterns (e.g.,
Dynamic Programming).
Dictionary of Algorithms and Data Structures (NIST)