University Of New South Wales

Data Structures and Algorithms


Iowa State Course Substitution

Introduction to Data Structures

COM S 228

Course Info
International Credits:
Converted Credits:
Course Description:
COMP2521 Data Structures and Algorithms School of Computer Science and Engineering, UNSW Overview Code/Title COMP2521 Data Structures and Algorithms Abbreviations DSA, 2521 Units of Credit 6 Pre-requisites COMP1511 Excluded COMP1927 Equivalent COMP1927 Offered In S1, S2 (commencing 17s2) Classes 3 hours lectures/week, 3 hours tute-lab/week Assessment Exam (theory+prac), Labs, Assignments, Quizzes Technologies C, gcc, make, git, gdb Introduction The goal of this course is to deepen students' understanding of data structures and algorithms and how these can be employed effectively in the design of software systems. We anticipate that it will generally be taken in the second year of a program (and it was originally assigned a level-2 course code), but since its only pre-requisite is ITP, is it possible to take it in first year. It is an important course in covering a range of core data structures and algorithms that will be used in context in later courses. Assumed Knowledge On entry to the course, we assume that students can: implement software in the procedural paradigm up to several 1000's LoC employ a range of fundamental data types in developing software solutions (e.g. arrays, structs, matrices, sets, lists, ...) can design and implement simple abstract data types reason about the behaviour (correctness and efficiency) of programs (e.g. defining pre- and post-conditions, efficiency of sorting algorithms) explain how programs work at the machine level (stack, heap, ...) work effectively in teams, following a systematic development process develop and use test suites for functions and programs work with a range of tools for program develoment (editors, compilers, debuggers, profilers, version control systems) effectively use structures from discrete mathematics (e.g. sets/relations/functions, basic logic, proof techniques from MATH1081) Learning Outcomes On successful completion of this course, students should be able to ... implement software in the procedural paradigm up to several 10,000's LoC use a range of algorithmic strategies in problem-solving reason about a wide range of data structures and their algorithms analyse the performance characteristics of algorithms measure the performance behaviour of programs reason about the correctness of programs choose/justify/implement an appropriate data structure for a given problem choose/analyse/implement appropriate algorithms to manipulate this data structure describe a range of fundamental concepts in parallelism Topics fundamental data structures: lists, trees, graphs algorithm and program analysis techniques for sorting, searching, traversing Schedule Week Lectures Labs Week 1 Introduction; Revision of data structures + ADTs + O(n) Linked-list revision Week 2 Sorting Review, Parallel Sorting External merge-sort Week 3 Algorithmic Strategies: recursion, divide-and-conquer, brute-force Sorting Detective Week 4 Graphs: Representation, Traversal, Paths, Tours Debugging with gdb Week 5 Graph Algorithms: Shortest Path, MSTs Web crawling and directed graphs Week 6 Fundamentals of Tree Structures Minimum Cost Paths Week 7 Searching (trees): Balanced Trees Tree Construction and Traversal Week 8 Searching (tables): Hashing Balanced Trees Week 9 Searching (files): Files, B-Trees, Linear Hashing Hashing Performance Experiment Week 10 Searching (text): substring, regular expressions, LCS B-Tree Performance Analysis


Evaluation Date:
November 8, 2017