Introduction to Data Structures and Algorithms
CS 250 Data Structures and Algorithms
Prof. Dr. Faisal Shafait
1 / 18
Introduction
Course overview
What is this course?
Intermediate-level course.
Concerns programming and problem solving techniques.
To develop efficient programs and applications.
2 / 18
Introduction
Course overview
What is this course?
Intermediate-level course.
Concerns programming and problem solving techniques.
To develop efficient programs and applications.
Algorithm: method for solving a problem.
Data structure: method to store information.
“Algorithms + Data Structures = Programs.” — Niklaus Wirth
3 / 18
Introduction
Course overview
In this course, we will explore:
Algorithms for efficiently solving problems.
Data structures for efficiently storing, accessing, and modifying
data.
4 / 18
Introduction
Course overview
In this course, we will explore:
Algorithms for efficiently solving problems.
Data structures for efficiently storing, accessing, and modifying
data.
Every data structure will have trade-offs.
There is no ultimate data structure.
The choice depends on our requirements.
5 / 18
Introduction
Why study algorithms
Where do you see the impact of data structures
and algorithms?
6 / 18
Introduction
Why study algorithms
Important for all branches of computer science and electrical
engineering.
For example,
To determine the shortest route between multiple points
Define an efficient electricity supply (load-shedding) procedure
Establish cellular (mobile phone) communication network
7 / 18
Introduction
Why study algorithms
All around us.
Computer Science. Search, packet routing, distributed file sharing,
video games, virtual reality, recommendations, news feeds,
advertisements, ...
Electrical Engineering. Circuit layout, communication systems,
network planning, power generation, power distribution, voting
machines, ...
...
Biology. Human genome project, protein folding, ...
Physics. N-body simulation, particle collision simulation, ...
8 / 18
Introduction
Why study algorithms
9 / 18
Introduction
Why study algorithms
Old roots, new opportunities.
Study of algorithms dates at least to Euclid around 300 BC.
Formalized by Church and Turing in 1930s.
Plays a key role in modern innovation.
10 / 18
Introduction
Why study algorithms
They are challenging—a good brain activity.
“For me, great algorithms are the poetry of computation. Just like verse,
they can be terse, allusive, dense, and even mysterious. But once
unlocked, they cast a brilliant new light on some aspect of computing."
— Francis Sullivan
11 / 18
Introduction
Why study data structures
To become a proficient programmer.
“I will, in fact, claim that the difference between a bad programmer and
a good one is whether he considers his code or his data structures
more important. Bad programmers worry about the code. Good
programmers worry about data structures and their relationships." —
Linus Torvalds (creator of Linux)
12 / 18
Introduction
Why study data structures
Provide novel “lens" on processes outside computer science.
Quantum mechanics, economic markets, evolution, ...
Computational models are replacing math models in scientific inquiry.
They may unlock the secrets of life and of the universe.
13 / 18
Introduction
Why study algorithms
Their impact is broad and far-reaching.
Old roots, new opportunities.
To solve problems that could not otherwise be addressed.
They may unlock the secrets of life and of the universe.
For intellectual stimulation.
To become a proficient programmer.
For fun and profit.
14 / 18
Introduction
Course contents
What are the basic topics?
short review of C++.
gist of algorithm analysis.
key data structures.
elementary and classic algorithms for sorting and searching.
elementary graph search algorithms.
concepts about algorithm design.
15 / 18
Introduction
Resources
All course-related material on the course web site,
[Link]
This includes:
The course outline
Lecture material
Various tutorials
Projects
Labs
Assignments
Grading policy
16 / 18
Introduction
Prerequisites
Prerequisites
Programming: loops, arrays, functions, objects, recursion.
C++: we use as expository language.
Mathematics: high-school algebra.
Useful reading material.
Quick: Introduction to Algorithms, 3/e (2009) by Cormen et al.
Data Structures and Algorithms in C++, 3/e (2005) by Adam
Drozdek.
The Algorithm Design Manual, 2/e (2008) by Steven S Skiena.
Programming environment: Visual Studio, gcc/g++ with Cygwin.
17 / 18
Introduction
Question
What top ten companies do you think made big
money from data structures and algorithms?
18 / 18
