COMP SCI 1103/1103BR Algorithm Design and Data Structures
COMP SCI 2103/2103BR Algorithm Design and Data Structures for Engineers
Synopsis
Builds on the foundation provided by the COMP SCI 11011102 sequence to
introduce the fundamental concepts of data structures and the algorithms that
proceed from them, and aspects of software engineering. Topics include
recursion, the underlying philosophy of objectoriented programming, fundamental
data structures (including stacks, queues, linked lists, hash tables, and
trees), the basics of algorithmic analysis, and an introduction to the
principles of language translation.  Review of elementary programming concepts
 Fundamental data structures: Stacks; queues; linked lists  Objectoriented
programming: Objectoriented design; encapsulation and information hiding;
classes; separation of behaviour and implementation; class hierarchies;
inheritance; polymorphism  Fundamental computing algorithms: O(N log N) sorting
algorithms;  Recursion: The concept of recursion; recursive mathematical
functions; simple recursive procedures; divideandconquer strategies; recursive
backtracking; implementation of recursion  Basic algorithmic analysis:
Asymptotic analysis of upper and average complexity bounds; identifying
differences among best, average, and worst case behaviours; big "O," little "o,"
omega, and theta notation;  Algorithmic strategies: Bruteforce algorithms;
greedy algorithms; divideandconquer; backtracking; branchandbound;
heuristics; pattern matching and string/text algorithms; numerical approximation
algorithms  Overview of programming languages: Programming paradigms  Software
engineering: Software validation; testing fundamentals, including test plan
creation and test case generation; objectoriented testing  Software evolution:
Software maintenance; characteristics of maintainable software; reengineering;
legacy systems; software reuse.
Course Details
 Coordinating Unit: School of Computer Science
 Course Coordinator: Dr. Mingyu Guo
 Term: Semester 1
 Level: Undergraduate
 Location/s: North Terrace Campus
 Units: 3
 Contact: Up to 6 hours per week
 Available for Study Abroad and Exchange: Y
 Prerequisites: COMP SCI 1009, COMP SCI 1102 or COMP SCI 1202
 Incompatible: COMP SCI 1203
 Restrictions: Available to B Eng (Software Engineering) and other nonEngineering degree students only
Course Learning Outcomes
At the end of this course, students will:

be able to competently program in C/C++ in the OO paradigm,

be able to manage memory usage in C/C++ programs,

be able to explain fundamental computing algorithms,

be able to analyse algorithms and identify key algorithmic strategies,

be familiar with fundamental software engineering practices,

have an overview of programming language design issues,

have developed their professional writing skills,

have developed their problem solving skills,

have worked in small group and team environments,

have an overview of ethics in computer science,

understand what abstract data types are, and

be able to apply elementary abstract data types to solve programming problems.
Resources
Recommended: The textbook for this course is: "Problem Solving with C++", 9e Global Edition, Walter Savitch, ISBN13:9781292018249, AddisonWesley, 2015.
Recommended: Students who have Java as a programming language and are entering this course are strongly encouraged to make use of the simple online resource that will be made available on the course website, closer to the start of term.
Schedule
The weekly pattern is three onehour lectures and a twohour practical session, with a tutorial every fortnight. The outline course content is:

Week 1
Review of fundamental C/C++ programming techniques, pointer arithmetic and function pointers, memory errors and core dumps

Week 2
Abstract data types and class hierarchies

Week 3
Inheritance, friends, and overloading

Week 4
Using classes, OO Design principles, testing and design

Week 5
Principles of software reuse and maintenance, recursion

Week 6
Ethics, polymorphism, using ADTs to produce usable structures

Week 7
Introduction to complexity analysis, upper and lower complexity bounds, bestcase and worstcase, big O, little o, omega and theta

Week 8
Complexity analysis, searching and sorting Algorithms

Week 9
Recursive complexity, linked lists and stacks

Week 10
Queues, other linked list based data structures

Week 11
Trees, algorithmic strategies

Week 12
Problem solving, programming paradigms, introduction to type systems
The course is structured to take you from an introductory knowledge of C++ to a higher level, as well as addressing some key areas of computer programming and algorithm design.
The summary of the areas covered in this course are:

Review and development of previous knowledge of C++

Fundamental data structures

Objectoriented Programming

Fundamental Computing Algorithms

Recursion

Basic Algorithmic Analysis

Algorithmic Strategies

Overview of programming languages

Software Engineering

Software Evolution

Professional Skills Development
Course Offerings
