Algorithms and Data Structures 2 Overview

Course Introduction

• Course title: Algorithms and Data Structures 2
• Lecturer: Dr. Michele Sevegnani
• Department: School of Computing Science, University of Glasgow
• Contact email: [email protected]
• Course year: ADS 2, 2024

Course Structure

• 11 lectures, two per week
• Lecture 1: Tuesdays at 11:00 AM in Main Building 255 Humanity LT
• Lecture 2: Thursdays at 11:00 AM in Main Building 220AB Hunter Halls
• 1-hour weekly lab sessions
• Lab sessions start in week 2 (beginning January 15th)
• Labs will be held in BO 706 or Kelvin Building Lab 320 (locations may be subject to change)
• Attendance at lectures and labs will be monitored

Course Materials

• Lecture slides available on Moodle at the start of each week.
• Video lectures available on Moodle.
• Lab sheets available via Moodle.
• Textbook recommendations:
  • Goodrich, M.T., Roberto Tamassia, and Michael H. Goldwasser. Data structures and algorithms in Java. John Wiley & Sons, 2014.
  • Cormen, T.H., et al. Introduction to algorithms. MIT press, 2009.
  • Sedgewick, R. Algorithms in Java, Parts 1-4 (Fundamental Algorithms, Data Structures, Sorting, Searching). Addison Wesley, 2002.

Course Content

• The course content is divided into weeks with various topics.
• A table of topics is provided, listing the topics covered each week. Details below: Week 1 : Introduction, Analysis techniques, Recursive algorithms Week 2: Sorting algorithms, Analysis of recursive algorithms Week 3: Analysis of recursive algorithms, Introduction Week 4: Linked lists Week 5: Abstract Data Types Week 6: Trees Week 7: Binary search trees, Balanced trees Week 9: Maps Week 10: Hash tables Week 11: Dynamic programming, Greedy algorithms

Assessment

• Final exam (80%)
• Past exams will be reviewed during revision classes.
• Two coursework assignments (20%, 10% each)
• Coursework will be built upon work developed during tutorial sessions.

Course Context

• First course in Algorithms and Data structures specifically for students with Java programming experience.
• Covers new concepts, including data structures, ADTs (abstract data types), algorithms, pseudocode, and complexity analysis.
  • Prerequisites include basic knowledge of Java and calculus.
• Explains the use of data structures and algorithms is fundamental to other key courses such as Object-Oriented Software Engineering.
• Projects work will be undertaken in levels 3 or 4.
• Basic algorithms and data structures will be used in other key courses such as operating systems scheduling, networking routing protocols, and information retrieval.

Foundations

• Introduction to Algorithms
  • Definition: A step-by-step procedure to solve a problem in a finite amount of time.
  • Examples: Sorting, string matching, finding the greatest common divisor (Euclid's algorithm).
• Introduction to Data Structures
  • Definition: A method for organizing data to facilitate access and modification.
  • Examples: Arrays, linked lists, stack, binary trees.

Algorithm Analysis

• Correctness: An algorithm is correct if it produces the correct output for every input instance.
• Algorithm Efficiency: The running time of an algorithm (which is related to the input size) is important.
• Development of effective methods to manage time and space is vital.
• Algorithm analysis will be studied in later lessons. This analysis allows for the ability to predict the resources necessary to execute the algorithm.

Summary

• The course covers algorithms and data structures, with an emphasis practical application to real-world problems using Java. Key topics include algorithm analysis, data structures, and their implementation. Practical examples will be given throughout the content.