DATA STRUCTURES AND ALGORITHMS
2018/2019, Semester 1
School of Computing (Computer Science)
Modular Credits: 4
This module introduces students to the design and implementation of fundamental data structures and algorithms. The module covers basic data structures (linked lists, stacks, queues, hash tables, binary heaps, trees, and graphs), searching and sorting algorithms, and basic analysis of algorithms. After completing the module, students should be able to:
Apply algorithmic thinking and techniques (e.g., divide and conquer, problem decomposition) for solving computational problems.
Describe the structure and operation of different data structures and algorithms under the standard computational model.
Assess the suitability of different data-structures and algorithms for a specific computational problem.
Adapt existing data-structures and algorithms to solve specific computational problems.
CS1010 or its equivalent, i.e., you should be familiar with standard programming concepts (e.g., functional programming) and basic algorithms (e.g., Bubble Sort).
You should be familiar with Java programming
should be taking CS2030 in parallel to this course.
In this course, you'll learn one of the core skills of a computer scientist: the ability to pick apart problems, design algorithmic solutions, and understand their properties (such as expected run time). We'll start with the basics:
Concepts such as Data Structures (DSes) and Abstract Data Types (ADTs)
Standard (linear) structures: Arrays, Linked Lists
Standard ADTs: Stacks, Queues
Analysis of algorithms via order of growth analysis, i.e. O(n) analysis
move on to intermediate topics:
Sorting algorithms: Mergesort, Quicksort
Searching ala Binary Search and Binary Search Trees
Balanced Trees, e.g., AVL
Hashing and the Table/Map ADT
Graphs and all the fun things you can do with graphs, e.g., searching, topological sorting, finding shortest paths.
and if time permits, we'll end with some special topics*. Some tentative topics:
PageRank or "How Google Works"
Backpropagation or "How Deep Nets Learn"
Linear Programming or "How to Optimize"
*Special topics are outside the normal curriculum but are
and will expose you to some of the cool things you can expect along your undergraduate journey at NUS.
These may or may not be covered depending on how we get on with time during the semester.
Your final grade will depend on:
CS1020, CS1020E, CS2020, CS2010
Each week, you will be expected to spend:
3 hours in lectures
1 hour in tutorials
2 hours in labs
2 hours doing assignments
2 hours doing prepatory work