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 Hans-Wolfgang 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 medium-size 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 problem-solving skills in the context of programming
- To be able to plan & execute a substantial software project
Pre-requisites:
- 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
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: 4-15th 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 self-contained. 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 data-structures and algorithms) -
T. Cormen, C. Leiserson, R. Rivest, C. Stein,
Introduction to Algorithms,
MIT Press, 3rd edition, 2009, ISBN 978-0-262-53305-8.
(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: 978-3-319-13071-2 (Print) 978-3-319-13072-9 (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. ISBN-13: 978-0262510875
(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:
- Hans-Wolfgang 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: