Constructing Software Systems
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 programming 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 libraries.
- Explain how fundamental algorithms and 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-conquer, dynamic programming, backtracking.
Prerequisites
Students should have knowledge of either an object-oriented or procedural language. Knowledge of basic programming language features, including primitive data types, operators, control structures, functions (methods), and input/output is assumed.
Textbook
Mark Allen Weiss,
Data Structures & Problem Solving Using Java.
Pearson, 4th edition, 2010.Teacher
Keld Helsgaun, associate professor
Additional information
Resources
Software
- IntelliJ IDEA (Java IDE)
- NetBeans (Java IDE)
- Eclipse (Java IDE)
- Source code of the textbook
- StdDraw (Java class for creating drawings)
Supplements
- API Specification for Java SE7
- Java Tutorials
- Threads (Chapter 9 of Learning Java by P. Niemeyer and D. Leuck)
- Dictionary of Algorithms and Data Structures
- The Stony Brook Algorithm Repository
- Algorithm Tutorials
- Using Induction to Design Algorithms (by Udi Manber)
- Om afprøvning (by Mads Rosendahl)
