Course F28DA: Data Structures and Algorithms
This page collects material for my part of the course F28DA: Data Structures and Algorithms. The Module Outline will be handed out to you in the first lecture. This course is delivered by HansWolfgang Loidl, Lilia Georgieva.
Purpose and Learning Objectives
To introduce core algorithms used in a wide range of applications in computer science; to further develop skills in algorithm and data structure design and the development of medium sized programs. On completion you should be able to: Choose a suitable algorithm for a given problem, and discuss advantages of different methods; design and implement a range of useful algorithms, e.g., compression, encryption, hashing and graph manipulation; design and implement mediumsize programming projects involving a number of different abstract data types, reusing and extending existing class libraries.
Learning Objectives:
 Ability to analyse and hence choose suitable algorithms and data structures for a given problem
 To design and implement medium sized programs based on a range of standard algorithms and data structures and making appropriate use of libraries
 Understanding the distinction between abstract Algebraic Data Type (ADT) properties and concrete ADT realisations
 Appreciation of need for integration of multiple ADTs in substantial programs
 Appreciation of efficiencies/reassurances from ADT reuse
Skills imparted:
 To be able to critically analyse and hence choose suitable algorithms and data structures for a given problem
 To be able to convey the advantages and disadvantages of alternative data structures and algorithms
 To develop practical problemsolving skills in the context of programming
 To be able to plan & execute a substantial software project
Prerequisites:
 Basic Java programming skills.
 Knowledge of basic data structures such as arrays, bags, lists, stacks, queues, linked lists
 The concept of abstract data types
 Basic object oriented design concepts: abstraction, encapsulation, modularity
Course Structure
 3 lectures per week
 Mon 12:15 EM 1.82
 Tue 13:15 EM 1.82
 Fri 9:15 EM 1.82
 2 lab hours per week

Fri 13:15 EM 2.50 (Linux lab)
Below is the planned structure of the course, subject to changes. Check the News section on the right hand side and the Vision pages about any changes.
Week 1:  Introduction 1, Introduction 2, Analysis of Algorithms  
Week 2:  Compression  Compression Tutorial, Compression Solution 
Week 3:  Cryptography: Basics , Overview , Ciphers , Queues & Stacks revision  Cryptography Tutorial, Cryptography Solution 
Week 4:  Introducing Graphs  Graph representation tutorial, Graph representation solution 
Week 5:  Graph Search Algorithms , Weighted Graphs and Algorithms  Graph Search Tutorial, Graph Search Solution 
Week 6:  Topological Order and Task Networks , Algorithm Design  Topological Order Tutorial, Topological Order Solution 
Week 7:  Reading Week  
Week 8:  Analysis of Algorithms & Asymptotic notation (Vision)  
Week 9:  Sorting Algorithms (Vision)  
Week 10:  Dictionaries (Vision)  
Week 11:  Hash Tables (Vision)  
Week 12:  Revision  
Assessment consist of two parts
 40% Coursework
 60% Exam (2 hours, written exam; topics from across the course; during exam period: 415th December)
Tutorial Information
Tutorials will take place in the first 40 minutes of the lab sessions in weeks 2 to 11. You will attempt a sheet of pencil & paper exercises with tutor assistance.
Coursework
Coursework will be handed out in Week 4 (due Week 7) and Week 8 (due Week 11) of the course.
Coursework 1 has been handed out.
Coursework resources:
Electronic Submission of Coursework
Please note that the coursework will not be marked unless you also follow these electronic submission procedures. Also note that the electronic submission applies to program source files only.
Instructions:
 Go to the directory where your source code is located.
 Type in the following command to access the submission script.
/u1/cs2/public/F28DA1/submit filename.java All data except that in italics must be keyed in as shown (this submission script works for multiple assignment numbers). The only thing you change is to put your file name in the place shown, e.g. to submit a file called mainProg.java for the first piece of coursework you would type in:
/u1/cs2/public/F28DA1/submit mainProg.java
 You can submit multiple files, but each file needs to be submitted separately i.e.
/u1/cs2/public/F28DA1/submit mainProg.java
/u1/cs2/public/F28DA1/submit file2.java
/u1/cs2/public/F28DA1/submit file3.java
 The submission should be of *.java files only  no *.zip or *.class files
 If the submission is okay, you will get a confirmation message displayed to the screen that
indicates the submission was sucessful.
 You can resubmit files  if you do so the script will prompt if you want to overwrite the
previous file you submitted. You can resubmit any number of times  up until the cut off date and
time that I give you.
 Report difficulties with submission problem@macs.hw.ac.uk, giving as clear information as you can what you are trying to do, where from and what the error message is.
Related Courses and Acknowledgements
Reading List
The module identifies sections of text books. During the course you are expected to read sections of the text, attempt exercises, and examine solutions.
There are numerous other books and websites with tutorials that cover the material in the course, e.g. USASK CS Tutorials Site. Enjoy exploring but be aware that these often cover slightly different material, or the materials in a slightly different way.
See also this Course's section on Blackwell's /www.readinglists.co.uk site.
The material presented in the lectures is largely selfcontained. However, to deepen your understanding you are encouraged to look up the following textbooks and papers. The main resources for this course are:
 Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, John Wiley & Sons; 5th Edition, 2010. ISBN: 0470398809.
Other good textbooks in this area are:

Data Structures, Algorithms, and Applications in Java, by Sartaj Sahni,
Silicon Printing, 2nd edition, 2004. ISBN: 0929306333.
Web page.
(Another good, but slightly dated, textbook on datastructures and algorithms) 
T. Cormen, C. Leiserson, R. Rivest, C. Stein,
Introduction to Algorithms,
MIT Press, 3rd edition, 2009, ISBN 9780262533058.
(one of the most comprehensive coverages of the area) 
"Data Structures and Algorithm Analysis", by Clifford A. Shaffer
(A good, more gentle introduction into the domain is given in this online textbook) 
"Data Structures and Algorithms with Python",
by Kent D. Lee, Steve Hubbard, Springer 2014.
ISBN: 9783319130712 (Print) 9783319130729 (Online)
(A good textbook teaching Data Structures and Algorithms from scratch in Python) 
"Structure and Interpretation of Computer Programs", H. Abelson, G.J. Sussman. MIT Press, Aug 1996. ISBN13: 9780262510875
(One of the The Classic textbooks on programming, with a strong focus on developing abstractions)  "Graph Theory", by Reinhard Diestel (a more theoretical treatment of graph structures)
News :
The 2012/13 course has finished.
Lecturers:
 HansWolfgang Loidl (HWL)
 Lilia Georgieva (LG)
Links:
 Vision page
 Course Descriptor
 Past exam papers
 HaWo's Linux Introduction
 Java on the commandline
 Dictionary of Algorithms and Data Structures
 Blackwell's reading list for F28DA
Related Courses: