[go: up one dir, main page]
Scribd
Upload
39 views12 pages

_1.Introduction

The document outlines a course on Data Structures and Algorithms, covering topics such as abstract data types, algorithm design, and various data structures including lists, trees, and graphs. It emphasizes the importance of understanding trade-offs in data structure choices and includes a focus on algorithm efficiency. Evaluation will be based on assignments, quizzes, a mid-term, a final exam, and a project, with C++ used as the programming language for demonstrations.

Uploaded by

15pwcse1348
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
39 views12 pages

_1.Introduction

The document outlines a course on Data Structures and Algorithms, covering topics such as abstract data types, algorithm design, and various data structures including lists, trees, and graphs. It emphasizes the importance of understanding trade-offs in data structure choices and includes a focus on algorithm efficiency. Evaluation will be based on assignments, quizzes, a mid-term, a final exam, and a project, with C++ used as the programming language for demonstrations.

Uploaded by

15pwcse1348
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Introduction

Welcome to
Data Structures and Algorithms
Introduction
2

Course description

• Algorithms and data structures emphasizes the following topics:


data structures, abstract data types, recursive algorithms, algorithm
analysis, sorting and searching, and problem-solving strategies.
Labs alternate weeks.
Introduction
3

Course objectives

• Introduce the student to the concept of data structures through


abstract data structures including lists, sorted lists, stacks, queues,
deques, sets/maps, directed acyclic graphs, and graphs; and
implementations including the use of linked lists, arrays, binary
search trees, M-way search trees, hash tables, complete trees, and
adjacency matrices and lists.
• Introduce the student to algorithms design including greedy, divide-
and-conquer, random and backtracking algorithms and dynamic
programming; and specific algorithms including, for example,
resizing arrays, balancing search trees, shortest path, and spanning
trees.
Introduction
4

Suggested texts and readings

• Cormen, Leiserson, Rivest, and Stein (CLRS), Introduction to


Algorithms, 2nd Ed., MIT Press, 2001.

• Algorithm Design Book by Jon Kleinberg and Éva Tardos March 16,
2005Algorithm Design Book by Jon Kleinberg and Éva Tardos
March 16, 2005
Introduction
5

General overview of the topics

• Review of Mathematics and C++


• Asymptotic and Algorithm Analysis
– Properties of data
– Asymptotic Analysis
– Algorithm Analysis
• Abstract Lists and Implementations
– Linked lists and arrays
– Stacks
– Queues
– Deques
• Abstract Sorted Lists and Implementations
– General trees, binary (including binary and complete trees), N-ary trees, and tree traversals
– Abstract Sorted Lists
– Binary search trees
– Balanced search trees
– AVL trees
– B-Trees
• Abstract Priority Queues
– Heaps
Introduction
6

General overview of the topics

• Abstract Sets/Maps
– Chained Hash Tables
– Linear Probing
– Double Hashing
• Sorting Algorithms
– Insertion and bubble sort
– Heap, merge, and quick sort
– Bucket and radix sort
• Graph and Direct Acyclic Graph Algorithms
– Topological sort
– Minimum spanning trees
– Shortest path
• Algorithm Design
– Greedy algorithms
– Divide-and-conquer algorithms
– Dynamic programming
– Randomized algorithms
– Backtracking algorithms
– NP Completeness, Turing machines, and the halting problem
• Example of an advanced data structure
Introduction
7

Data Structures and Algorithms

In this course, we will look at:


– Algorithms for solving problems efficiently
– Data structures for efficiently storing, accessing, and modifying data
We will see that all data structures have trade-offs
– There is no ultimate data structure...
– The choice depends on our requirements
Introduction
8

Data Structures and Algorithms

‫‫‬ Consider accessing the kth entry in an array or linked list


– In an array, we can access it using an index array[k]
• there is a single machine instruction for this
– We must step through the first k – 1 nodes in a linked list

‫‫‬ Consider searching for an entry in a sorted array or linked list


– In a sorted array, we use a fast binary search
• Very fast
– We‫‫‬must‫‫‬step‫‫‬through‫‫‬all‫‫‬entries‫‫‬less‫‫‬than‫‫‬the‫‫‬entry‫‫‬we’re‫‫‬looking‫‫‬for
• Slow
Introduction
9

Data Structures and Algorithms

‫‫‬ However, consider inserting a new entry to the start of an array or a


linked list
– An array requires that you copy all the elements in the array over
• Slow for large arrays

– A linked list allows you to make the insertion very quickly


• Very fast regardless of size
Introduction
10

C++

‫‫‬ You will be using the C++ programming language in this course
Introduction
11

C++

‫‫‬ This course does not teach C++ programming


– You will use C++ to demonstrate your knowledge in this course

‫‫‬ One lecture may be covered:


– About the Features of C++
Introduction
12

Evaluation

‫‫‬ Your evaluation in this course is based on three components:


– Assignments
– Quizzes (Mostly Announced)
– One mid-term examination
– One final examination
– Project

You might also like