Fall 2011

by

Keld Helsgaun

Contents

The course provides knowledge about fundamental algorithms and data structures in computer science. The main objective of this course is to provide students with means to design and reason about algorithms, understand the strengths and weaknesses of known algorithms, and their suitability in particular contexts. The topics covered include data abstraction, generic components, algorithm analysis, recursion, algorithm design, searching, sorting, randomization, simulation, and graphs. In more detail, the contents of the course may be described as follows:

• Data structures: Stacks, queues, linked lists, trees, hash tables, priority queues.
• Algorithms: Analysis, verification, searching, sorting.
• Problem solving techniques: Divide-and-conquer, dynamic programming, backtracking.
• Applications: Games, parsing, file compression, simulation, graphs.

The programming language Java is used in this course.

Purpose

The purpose of this course is to provide a practical introduction to algorithms and data structures from the viewpoint of abstract thinking and problem solving. The primary focus is on problem-solving techniques that allow the construction of sophisticated time-efficient programs.

Aim

On successful completion of the course, the student will be able to:

• Design, implement and test small to medium sized applications in a mainstream program­ming language.
• Understand and clearly explain the mechanics of algorithms and data structures involving manipulation of references, nested loops and recursion.
• Choose among and make use of the most important algorithms and data structures in librar­ies.
• Explain how fundamental algorithms for data structures for searching and sorting may be implemented.
• Analyze time and space usage of algorithms and data structures.
• Reason about the correctness of an algorithm.
• Apply the following algorithmic techniques when solving a problem: Divide-and-con­quer, dynamic programming, backtracking.

Textbook

Mark Allen Weiss, Data Structures & Problem Solving Using Java. Pearson, 4th edition, 2010.

Teacher

Keld Helsgaun, associate professor


Additional information

• Schedule of lectures
• Slides
• Weekly work plans
• Exercises
• Assignment
• Exam

Resources

Software

• IntelliJ IDEA (Java IDE)
• NetBeans (Java IDE)
• Eclipse (Java IDE)
• Souce code of the textbook
• StdDraw (Java class for creating drawings)

Supplements

• API specification for Java SE7
• Java Tutorials
• Dictionary of Algorithms and Data Structures
• The Stony Brook Algorithm Repository
• Algorithm Tutorials
• Using Induction to Design Algorithms (Udi Manber)

• Sorting algorithm animations
• Game visualization
• Huffman encoding & decoding animation
• Binary seach tree animation
• Hashing animation tool