ITCS-6114/8114: Algorithms
and Data Structures
Fall 2010
Srinivas Akella
Department of Computer Science
University of North Carolina, Charlotte
Acknowledgments: Richard Souvenir
Algorithms & Data Structures
ITCS 6114 / 8114
• Instructor: Srinivas Akella
– Office: 410E Woodward
– Email:
[email protected] – Office hours: Wed 2:30-3:30 or by appointment
• TA: Ning Zhou
– Office: 401 Woodward
– Email:
[email protected] – Office hours: Monday 1:00-3:00pm
• Course website: www.cs.uncc.edu/~sakella/courses/ads/
• Course information via Moodle
Welcome and Administrivia
• This is a course about data
structures and algorithms
• What does that mean?
What is a data structure?
• A data structure is a representation of a
dynamic set of data items.
– Dynamic sets can grow, shrink, and otherwise
change over time.
What is an algorithm?
• An algorithm is a sequence of unambiguous
instructions for solving a problem, i.e., for
obtaining a required output for any legitimate
input in a finite amount of time.
problem
algorithm
input “computer” output
Algorithm
• Word derived from Al Khwarzimi (~780-850 AD),
Persian mathematician in Baghdad
• Books: “On the Calculation with Hindu Numerals” (Latin:
Algoritmi de numero Indorum) and
“Kitab al-Jabr wa-l-Muqabala” (Latin: Liber algebrae et
almucabala)
• His book described methods to compute: add, multiply,
divide, find square roots, compute pi
• Methods were precise, unambiguous, correct, efficient
• Techniques were popularized by Leonardo Fibonacci
(1170-1250 AD) in his book “Liber abaci”
Source: Wikipedia
Greatest Common Divisor
• Euclid’s GCD algorithm (~300 BC)
• Possibly oldest algorithm
• GCD (a, b)
if b==0
return a
else return GCD (b, a mod b)
Some Well-known Computational
Problems
• Sorting* • Traveling salesman
• Searching* problem*
• Shortest paths in a • Knapsack problem*
graph* • Chess
• Minimum spanning tree* • Towers of Hanoi
• Primality testing • Program termination
• * will cover in this course
8
Two main issues related to
algorithms
• How to design algorithms
• How to analyze algorithm efficiency
9
Design of Algorithms
• Many design strategies
– We will cover the most popular strategies
used in CS.
• The idea is to determine best strategy
given a problem (type)
– A mix of art & science
10
Analysis of Algorithms
• How good is the algorithm?
– Correctness
– Time efficiency
– Space efficiency
• Does there exist a better algorithm?
– Lower bounds
– Optimality
11
Example: Fibonacci numbers
• F_0 = 0
• F_1 = 1
• F_n = F_(n-1) + F_(n-2), for n >= 2
• Write a function to compute the n-th
Fibonacci number
Fibonacci Algorithms
• Recursive version
• Complexity: ~O(1.618^n)
• Memoized version: Stores state (using an
array, or even just two variables) to
reduce time complexity
• Complexity: O(n)
Does Algorithm Efficiency Really
Matter?
Source: Programming Pearls, 2nd ed., Bentley
Why study algorithms?
• Theoretical importance
– the core of computer science
• Practical importance
– A practitioner’s toolkit of known algorithms
– Framework for designing and analyzing
algorithms for new problems
15
Data Structures & Algorithms?
• Data structures & • Data Structures
algorithms are related – array
– Algorithms need data – linked list
structures – Stack / queue
– Hashtable*
– Data Structures need
algorithms – Priority queue*
– Graph*
– Trees (BST, Red-Black)*
16
Course Information
• Syllabus can be found on course web page
and Moodle
• We will cover the highlights now
Course Philosophy
• This course will introduce topics that are at
the core of computer science
– Help you think and talk like a Computer Scientist
• Auxiliary Goals
– critical thinking
– problem solving
– creativity
18
Attendance Policy
• Attendance is not mandatory, but strongly
recommended.
• Most of the material that is presented in class can
be found in the course textbook
• You are responsible for all the material and
administrative announcements presented during
class.
19
Textbook
• The required
textbook is:
Introduction to
Algorithms, 3rd
edition, Thomas H.
Cormen, Charles E.
Leiserson, Ronald L.
Rivest, Clifford Stein,
MIT Press, 2009.
20
Homework & Exams
• Homeworks (4)
– Written answers to material covered in class
• Programming Projects (2)
– Use one of C++, Java, Python
– Must be able to read/write files
– Must write commented and documented code
• Exams (2)
Academic Integrity Policy
• All submitted solutions to homeworks and
programming projects must be your own
work.
• See syllabus for policy on discussion of
homeworks and projects
• Report any assistance you receive.
• Violations of any of the academic
integrity rules will be dealt with
harshly!
22
Ok, let’s get started…
• You own a large space telescope
• Lots of astronomers want to use it
• Each astronomer’s project pi requires use of
the telescope starting at a fixed time si (when
their grant starts) and running for li days.
• Only one project can use a telescope at a
time.
• Your goal: Justify yourself to NASA by
scheduling as many projects as possible
Formally…
• Given a set P of projects pi, each occupying
the half-open interval [si, si + li) …
• Choose a subset ¦ µ P of project for which
– No two projects intervals overlap
– The number of projects in ¦ is maximized
• This is one of many variants of scheduling or
activity selection
Suggestion #1
Suggestion #2
Suggestion #3
Common Plan
• Common themes:
– Repeatedly pick an element until no more
feasible choices remain
– Among all feasible choices, we always pick
the one that minimizes (or maximizes) some
property (job length, start time, # conflicts)
– Such algorithms are called greedy
Greedy Algorithms
• So far, greedy algorithms don’t look so
good.
• Perhaps, we’ve been using the wrong
property
Another Approach
• Intuition
– For each project pi,
define its finishing
time fi to be si + li
– Sort the projects in
increasing order of
finishing time
– Repeatedly pick
nonconflicting,
unscheduled job with
earliest finishing time
How did we do?
• Is this correct?
• Is this fast?
• Can we do better?
• By the end of the semester, we’ll be able
to answer these questions.
Quiz
• Yes, I have a short quiz for you now.
Reading
• CLRS
• Background reading: Appendices A to D,
Chapter 10
• Today’s class: Chapter 1
• Next class: Chapters 2 and 3
