Table of contents
- Algorithms and Data Structures I
Algorithms and Data Structures I
This module will help you to develop your analytical and problem-solving skills. It will encourage you to think about how to use computers to solve problems. You’ll develop skills in thinking algorithmically and learn the central concepts of algorithms and data structures. You will learn about linear data structures such as arrays, vectors and lists and a unifying framework for considering such data structures as collections. You’ll study how algorithms can be expressed as flowcharts and pseudocode and how to convert these into programs. You’ll learn specific algorithms used for sorting and searching, and how to express repetition as iteration and recursion. You will learn a simple model for execution of computation, and how to describe computational problems and their solutions. The model will allow you to compare algorithms regarding their correctness and regarding their efficiency.
Professor(s)
- Dr. Matty Hoban
Topics covered
- Introduction to algorithms, flowcharts and pseudocode
- Computations using flowcharts and pseudocode
- Pairs, vectors and dynamic arrays
- Basic searching
- Linked lists
- Basic sorting
- Advanced searching and introduction to complexity
- Recursive algorithms
- Advanced sorting
- Linear collections
Assessment
One two hour unseen written examination and coursework (Type I)
Module specification
Past exams
Syllabus
Resources
Complementary learning
- Algorithmic Design and Techniques - edX platform, by UC San Diego
- Data Structures Fundamentals - edX platform, by UC San Diego
- Easy Theory - “This is a channel about making Computer Science theory as easy as possible.” Relevant for this course as well as Fundamentals of Computer Science.
Visualizations
-
Data Structures Visualization - Visualizations of a lot of data structures and related algorithms.
-
Animated DSA Visualization - Sorting algorithms, searching algorithms and many data structures beautifully visualized.
Algorithms
- Comparison of Algorithms - See time complexity at a glance for various popular algorithms.
- Data Structure & Algorithms Introduction - Sorting algorithms, data structures, tree data structure and more.
- Data Structures and Algorithms Tutorial - Step by Step Tutorial on DSA for beginners.
mergeSort algorithm
- 2.7.2. Merge Sort Algorithm - Abdul Bari
- Algorithm lecture 8 – Merge sort algorithm, analysis and problems - Gate Lectures by Ravindrababu Ravula
quickSort algorithm
- Algorithms lecture 9 – Quick sort algorithm - Gate Lectures by Ravindrababu Ravula
- 2.8.1 QuickSort Algorithm - Abdul Bari
quickSort & mergeSort algorithms MIT
- 3. Insertion Sort, Merge Sort - MIT 6.006 Introduction to Algorithms, Fall 2011
Computational complexity & P vs NP
- Big-O Cheat Sheet - bigocheatsheet.com
- Computational Complexity - MIT OpenCourseWare
- P vs. NP and the Computational Complexity Zoo - hackerdashery
Essential reading
“Specific essential readings for this course will be taken from the following text book:
- Cormen, T.H., C.E. Leierson, R.L. Rivest and C. Stein Introduction to Algorithms. (Cambridge, MA: MIT Press, 2009) 3rd edition.
The specific pages for the reading activities will be given in the platform, and there is no need to read beyond to recommended pages.
In addition to the text book, there are additional reading activities written by the course author, some of which involve coding exercises.
There will also be discussion prompts asking you to do some independent research using online sources.”
Examples of past and current written exams
- 2014, 2015, 2016, 2018, 2020: Visit this page.
- ADS1 September 2020 online exam
Kinks to be aware of
Notes
On REPL
Solutions to the textbook Introduction to Algorithms
- CLRS Solutions - Michelle Bodnar, Andrew Lohr