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 1101-1102 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 object-oriented 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 - Object-oriented
programming: Object-oriented 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; divide-and-conquer 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: Brute-force algorithms;
greedy algorithms; divide-and-conquer; backtracking; branch-and-bound;
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; object-oriented 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 non-Engineering 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, ISBN-13:9781292018249, Addison-Wesley, 2015.
Recommended: Students who have Java as a programming language and are entering this course are strongly encouraged to make use of the simple on-line resource that will be made available on the course website, closer to the start of term.
Schedule
The weekly pattern is three one-hour lectures and a two-hour 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 re-use and maintenance, recursion
-
Week 6
Ethics, polymorphism, using ADTs to produce usable structures
-
Week 7
Introduction to complexity analysis, upper and lower complexity bounds, best-case and worst-case, 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
-
Object-oriented Programming
-
Fundamental Computing Algorithms
-
Recursion
-
Basic Algorithmic Analysis
-
Algorithmic Strategies
-
Overview of programming languages
-
Software Engineering
-
Software Evolution
-
Professional Skills Development
Course Offerings
|
