Scribd
Upload
10 views

Algorithms 1 - Introduction To Module

This document provides an overview of the Algorithms and Data Structures 1 module. It introduces the lecturer, Nima Jamalian, and outlines the module structure, topics, assessments, and goals. Over ten weeks, students will learn about analysis of algorithms, recursion, sorting algorithms, hashing, and algorithm design. Assessment includes topic quizzes, programming lab submissions, and a final exam. The goal is for students to analyze algorithm time/space complexity, implement standard algorithms, and understand recursive/iterative solutions.

Uploaded by

Hassan Madani
Copyright
© © All Rights Reserved
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
10 views

Algorithms 1 - Introduction To Module

This document provides an overview of the Algorithms and Data Structures 1 module. It introduces the lecturer, Nima Jamalian, and outlines the module structure, topics, assessments, and goals. Over ten weeks, students will learn about analysis of algorithms, recursion, sorting algorithms, hashing, and algorithm design. Assessment includes topic quizzes, programming lab submissions, and a final exam. The goal is for students to analyze algorithm time/space complexity, implement standard algorithms, and understand recursive/iterative solutions.

Uploaded by

Hassan Madani
Copyright
© © All Rights Reserved
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 21

Algorithms and Data Structures 1

By Nima Jamalian
Introduction To
Module
About Me
• Lecturer in Games Programming & Computing
• Researcher in Games, VR, AR and Gamification

• Previously
• VR and AR Consultant (South Bank Innovation)
• Software Engineer (Nokia Bell Labs)
Module Structure
• Lectures
• Monday 16:00 - 18:00 (RHB 342)
• Lab Session
• Group 1 - Friday 9:00 - 11:00 (RHB 306a)
• Group 2 - Friday 14:00 - 16:00 (RHB 117)
• Only attend to lab group you have been assigned to, check your timetable to see
which group you are in.
Module Syllabus

THE MODULE CONSISTS OF 2 WEEKS PER TOPIC 2 WEEKS PER TOPIC


5/4 TOPICS OVER TEN WEEKS.
Module Description

• How do you estimate how much memory an • The course focuses on Algorithms:
algorithm is going to consume?
• How to analyse and algorithm
• How fast is an algorithm when it has to process big
data? • Recursive Algorithms

• What are the main algorithms to solve classical • Slow and fast approaches for sorting data
computer science problems?
• A new fast way of searching for data.
• How do you select the best algorithm to solve a
given problem?

• These are the main question you will be able to


answer after successfully finishing this course.
Textbook and Readings
• The guide book for this course is the following
• Cormen, T.H., C.E. Leiserson, R.L. Rivest and C.
Stein Introduction to algorithms. (MIT Press, 2009)
3rd edition [ISBN 9780262533058]
• Link Reading Materials on Goldsmiths Online Library:
• https://learn.gold.ac.uk/mod/aspirelists/view.php?id=1
377565
Topic 1 - Week 1 and Week 2
Analysis of algorithms

• Theoretical vs. empirical algorithm analysis


Key concepts: • Memory and time requirements from pseudocode
• Growth function and asymptotic notation

• Determine time and memory consumption of an algorithm described using pseudocode


• Determine the growth function of the running time or memory consumption of an algorithm
Learning Outcomes:
• Use Big-O, Ω and Θ notations to describe the running time or memory consumption of an
algorithm
Topic 2 - Week 3 and Week 4
Recursion

• Algorithmic recursion
• The structure of recursive algorithms
Key concepts:
• Recurrence equations
• Master Theorem

• Trace and write recursive algorithms


• Write the recursive version of an iterative algorithm using pseudocode
Learning Outcomes:
• Calculate the time complexity of recursive algorithms
consumption of an algorithm
Topic 3 - Week 5 and Week 6
Comparison sorting algorithms

• Comparison vs. non comparison sorts


Key concepts: • Bubble, Insertion and Selection sort
• Recursive sorts: Mergesort and Quicksort

• Identify the different approaches of different comparison sorting algorithms


Learning Outcomes: • Implement different comparison sorting algorithms
• Calculate the time complexity of different comparison sorting algorithms
Topic 4 - Week 7 and Week 8
Non-comparison sorting algorithms

• The limits of comparison sorts


Key concepts:
• Counting, radix and bucket sort

• Identify the different approaches of different non-comparison sorting algorithms


Learning Outcomes: • Implement different non-comparison sorting algorithms
• Calculate the time complexity of different non-comparison sorting algorithms
Topic 5 - Week 9 and Week 10
Hashing

• The problem of searching


Key concepts: • Hash tables, hash functions
• Collision resolution techniques

• Describe the different methods used to search for data


Learning Outcomes: • Describe different collision resolution methods
• Implement a hash table with linear probing collision resolution
Module Topics

Analysis of Recursion Sorting


algorithms Algorithms

Design of
Hashing
Algorithms
Assessments
• Coursework (50%)
• Topic Quizzes (20%) Exam Lab Submissions Lab Quizzes

• Lab Submissions (30%)


• Exam (50%)
20%

50%
30%
Assessments -Quizzes
• Lab Quizzes (30%)
• Lab Quizzes give you a taste of final exam Exam Lab Submissions Lab Quizzes
and test your knowledge about on topic
learned during class.

20%

50%
30%
Assessments - Lab Submissions
• Lab Submissions (30%)
• Lab submission is programming exercise Exam Lab Submissions Lab Quizzes
about topic covered in class.

20%

50%
30%
Assessments - Exam
• Final Exam (50%)
• This is a written 2 hour exam with unseen Exam Lab Submissions Lab Quizzes
questions.
• The exam covers the 5 topics in this module:
• Analysis of Algorithms
20%
• Recursion
50%
• Sorting
30%
• Hashing
• Design of Algorithms
Extenuation Circumstances
• If you miss deadline due to extenuation circumstances you need to apply online for
late submission.
• Link:
https://www.gold.ac.uk/students/processes/mitigating-and-extenuating-circumstances/
help/
Extenuation Circumstances
• Remember no need to email your lecturer.
• EC are not processed by the department
• EC are processed by the registry office.
• If your EC request for extension is accepted
• An extension will granted to you
• Normal 2 weeks after the deadline extension
• If you apply late (2 weeks after the submission deadline)
• No extension will be given but the only option is to defer to late summer.
Module Goals and Objectives
• Upon successful completion of this module, you will be able to:
• Express time and space complexities of specific algorithms using big-O notation
• Implement standard searching, sorting and path finding algorithms
• Compare and contrast recursive and iterative expression of solutions to problems
Any questions
so far?

You might also like